algorithm
Złożoność algorytmu

Uwagi

total = 0
for(i = 1; i < 10; i++)
    total = total + i

Notacja Big-Theta

W przeciwieństwie do notacji Big-O, która reprezentuje tylko górną granicę czasu działania dla niektórych algorytmów, Big-Theta jest ściśle związana; zarówno górna, jak i dolna granica. Wąska granica jest bardziej precyzyjna, ale także trudniejsza do obliczenia.

Notacja Big-Theta jest symetryczna: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))

Intuicyjnym sposobem uchwycenia tego jest to, że f(x) = Ө(g(x)) oznacza, że wykresy f (x) ig (x) rosną w tym samym tempie lub że wykresy „zachowują się” podobnie dla dużych wystarczające wartości x.

Pełny matematyczny zapis notacji Big-Theta jest następujący:
Ө (f (x)) = {g: N ₀ -> R i c ₁ , c ₂ , n ₀ > 0, gdzie c ₁ <abs (g (n) / f (n)), dla każdego n> n _0, a abs jest wartością bezwzględną}

Przykład

Jeśli algorytm dla wejścia n zajmuje 42n^2 + 25n + 4 operacji, mówimy, że jest to O(n^2) , ale także O(n^3) i O(n^100) . Jednak jest to Ө(n^2) i nie jest to Ө(n^3) , Ө(n^4) itd. Algorytmem, który jest Ө(f(n)) jest również O(f(n)) , ale nie odwrotnie!

Formalna definicja matematyczna

Ө(g(x)) to zestaw funkcji.

Ө(g(x)) = {f(x) such that there exist positive constants c1, c2, N such that 0 <= c1*g(x) <= f(x) <= c2*g(x) for all x > N}

Ponieważ Ө(g(x)) jest zbiorem, moglibyśmy napisać f(x) ∈ Ө(g(x)) aby wskazać, że f(x) jest członkiem Ө(g(x)) . Zamiast tego zwykle piszemy f(x) = Ө(g(x)) aby wyrazić to samo pojęcie - to jest powszechny sposób.

Ilekroć we wzorze pojawia się Ө(g(x)) , interpretujemy go jako symbol anonimowej funkcji, której nie chcemy nazwać. Na przykład równanie T(n) = T(n/2) + Ө(n) , oznacza T(n) = T(n/2) + f(n) gdzie f(n) jest funkcją w zbiorze Ө(n) .

Niech f i g będą dwiema funkcjami zdefiniowanymi w pewnym podzbiorze liczb rzeczywistych. f(x) = Ө(g(x)) jako x->infinity wtedy i tylko wtedy, gdy istnieją dodatnie stałe K i L oraz liczba rzeczywista x0 taka, która zawiera:

K|g(x)| <= f(x) <= L|g(x)| dla wszystkich x >= x0 .

Definicja jest równa:

f(x) = O(g(x)) and f(x) = Ω(g(x))

Metoda wykorzystująca ograniczenia

jeśli limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) tj. granica istnieje i jest dodatnia, to f(x) = Ө(g(x))

Wspólne klasy złożoności

Notacja Big-Omega

Notacja Ω służy do asymptotycznej dolnej granicy.

Formalna definicja

Niech f(n) g(n) będą dwiema funkcjami zdefiniowanymi na zbiorze dodatnich liczb rzeczywistych. Piszemy f(n) = Ω(g(n)) jeśli istnieją stałe dodatnie c i n0 takie, że:

0 ≤ cg(n) ≤ f(n) for all n ≥ n0 .

Notatki

f(n) = Ω(g(n)) oznacza, że f(n) rośnie asymptotycznie nie wolniej niż g(n) . Możemy również powiedzieć o Ω(g(n)) gdy analiza algorytmu nie wystarczy do stwierdzenia o Θ(g(n)) lub / i O(g(n)) .

Z definicji notacji wynika twierdzenie:

Dla dwóch dowolnych funkcji f(n) g(n) mamy f(n) = Ө(g(n)) wtedy i tylko wtedy, gdy f(n) = O(g(n)) and f(n) = Ω(g(n)) .

Graficzną notację Ω można przedstawić następująco:

Na przykład, niech mamy f(n) = 3n^2 + 5n - 4 . Następnie f(n) = Ω(n^2) . Jest to również poprawne f(n) = Ω(n) , a nawet f(n) = Ω(1) .

Kolejny przykład rozwiązania algorytmu perfekcyjnego dopasowania: Jeśli liczba wierzchołków jest nieparzysta, wypisz „Brak idealnego dopasowania”, w przeciwnym razie wypróbuj wszystkie możliwe dopasowania.

Chcielibyśmy powiedzieć, że algorytm wymaga czasu wykładniczego, ale w rzeczywistości nie można udowodnić dolnej granicy Ω(n^2) przy użyciu zwykłej definicji Ω ponieważ algorytm działa w czasie liniowym dla n nieparzystych. Zamiast tego powinniśmy zdefiniować f(n)=Ω(g(n)) , mówiąc dla jakiejś stałej c>0 , f(n)≥ cg(n) dla nieskończenie wielu n . Daje to dobrą zgodność między górną i dolną granicą: f(n)=Ω(g(n)) iff f(n) != o(g(n)) .

Bibliografia

Formalną definicję i twierdzenie zaczerpnięto z książki „Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Wprowadzenie do algorytmów”.

Porównanie notacji asymptotycznych

Niech f(n) g(n) będą dwiema funkcjami zdefiniowanymi na zbiorze dodatnich liczb rzeczywistych, c, c1, c2, n0 są dodatnimi stałymi rzeczywistymi.

Notacja	f (n) = O (g (n))	f (n) = Ω (g (n))	f (n) = Θ (g (n))	f (n) = o (g (n))	f (n) = ω (g (n))
Formalna definicja	∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) ≤ cg(n)	∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) ≤ f(n)	∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)	∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) < cg(n)	∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) < f(n)
Analogia między asymptotycznym porównaniem f, g a liczbami rzeczywistymi a, b	a ≤ b	a ≥ b	a = b	a < b	a > b
Przykład	7n + 10 = O(n^2 + n - 9)	n^3 - 34 = Ω(10n^2 - 7n + 1)	1/2 n^2 - 7n = Θ(n^2)	5n^2 = o(n^3)	7n^2 = ω(n)
Interpretacja graficzna

Notacje asymptotyczne można przedstawić na diagramie Venna w następujący sposób:

Spinki do mankietów

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Wprowadzenie do algorytmów.