Uczę się analizy algorytmów. Mam problem ze zrozumieniem różnicy między O, Ω i Θ.

Sposób ich definiowania jest następujący:

f(n) = O(g(n)) znaczyc · g(n) jest górną granicąf(n). Tak więc istnieje jakaś stałac takief(n) jest zawsze ≤c · g(n), wystarczająco dużyn (to znaczy.,n ≥ n0 dla pewnej stałejn0).f(n) = Ω(g(n)) znaczyc · g(n) jest dolną granicąf(n). Tak więc istnieje jakaś stałac takief(n) jest zawsze ≥c · g(n), dla wszystkichn ≥ n0.f(n) = Θ(g(n)) znaczyc1 · g(n) jest górną granicąf(n) ic2 · g(n) jest dolną granicąf(n), dla wszystkichn ≥ n0. Tak więc istnieją stałec1 ic2 takief(n) ≤ c1 ·g(n) if(n) ≥ c2 ·g(n). To znaczy żeg(n) zapewnia miłą, ciasną wiązanief(n).

Sposób, w jaki to zrozumiałem, jest następujący:

O(f(n)) daje najgorszy przypadek złożoności danej funkcji / algorytmu.Ω(f(n)) daje najlepszą złożoność przypadku danej funkcji / algorytmu.Θ(f(n)) podaje średnią złożoność przypadku danej funkcji / algorytmu.

Proszę, popraw mnie jeśli się mylę. Jeśli tak, złożoność czasowa każdego algorytmu musi być wyrażona we wszystkich trzech notacjach. Zauważyłem jednak, że jest wyrażona jako O, Ω lub Θ; dlaczego nie wszystkie trzy?