algorithm
Algoritme Complexiteit

Opmerkingen

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

Big-Theta-notatie

In tegenstelling tot de Big-O-notatie, die voor sommige algoritmen alleen de bovengrens van de looptijd vertegenwoordigt, is Big-Theta een strakke grens; zowel boven- als ondergrens. Strak gebonden is nauwkeuriger, maar ook moeilijker te berekenen.

De Big-Theta-notatie is symmetrisch: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))

Een intuïtieve manier om het te begrijpen, is dat f(x) = Ө(g(x)) betekent dat de grafieken van f (x) en g (x) in dezelfde snelheid groeien, of dat de grafieken zich 'even groot' gedragen voldoende waarden van x.

De volledige wiskundige uitdrukking van de Big-Theta-notatie is als volgt:
Ө (f (x)) = {g: N ₀ -> R en c ₁ , c ₂ , n ₀ > 0, waarbij c ₁ <abs (g (n) / f (n)), voor elke n> n ₀ en abs is de absolute waarde}

Een voorbeeld

Als het algoritme voor de invoer n 42n^2 + 25n + 4 bewerkingen nodig heeft om te eindigen, zeggen we dat dit O(n^2) , maar ook O(n^3) en O(n^100) . Het is echter Ө(n^2) en het is niet Ө(n^3) , Ө(n^4) enz. Algoritme dat Ө(f(n)) is, is ook O(f(n)) , maar niet vice versa!

Formele wiskundige definitie

Ө(g(x)) is een set functies.

Ө(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}

Omdat Ө(g(x)) een set is, kunnen we f(x) ∈ Ө(g(x)) om aan te geven dat f(x) lid is van Ө(g(x)) . In plaats daarvan schrijven we meestal f(x) = Ө(g(x)) om hetzelfde idee uit te drukken - dat is de gebruikelijke manier.

Telkens wanneer Ө(g(x)) in een formule voorkomt, interpreteren we het als een anonieme functie die we niet graag noemen. De vergelijking T(n) = T(n/2) + Ө(n) betekent bijvoorbeeld T(n) = T(n/2) + f(n) waarbij f(n) een functie is in de verzameling Ө(n) .

Laat f en g twee functies zijn die zijn gedefinieerd op een subset van de reële getallen. We schrijven f(x) = Ө(g(x)) als x->infinity als en alleen als er positieve constanten K en L en een reëel getal x0 zodanig dat geldt:

K|g(x)| <= f(x) <= L|g(x)| voor alle x >= x0 .

De definitie is gelijk aan:

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

Een methode die limieten gebruikt

als limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) dwz dat de limiet bestaat en positief is, dan is f(x) = Ө(g(x))

Gemeenschappelijke complexiteitsklassen

Big-Omega-notatie

Ω-notatie wordt gebruikt voor asymptotische ondergrens.

Formele definitie

Laat f(n) en g(n) twee functies zijn die zijn gedefinieerd op de set van de positieve reële getallen. We schrijven f(n) = Ω(g(n)) als er positieve constanten c en n0 zodat:

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

Notes

f(n) = Ω(g(n)) betekent dat f(n) asymptotisch groeit niet langzamer dan g(n) . We kunnen ook zeggen over Ω(g(n)) wanneer algoritmeanalyse niet genoeg is voor een uitspraak over Θ(g(n)) of / en O(g(n)) .

Uit de definities van notaties volgt de stelling:

Voor twee functies f(n) en g(n) hebben we f(n) = Ө(g(n)) als en alleen als f(n) = O(g(n)) and f(n) = Ω(g(n)) .

Grafische Ω-notatie kan als volgt worden weergegeven:

Laten we bijvoorbeeld f(n) = 3n^2 + 5n - 4 . Dan f(n) = Ω(n^2) . Het is ook correct f(n) = Ω(n) , of zelfs f(n) = Ω(1) .

Een ander voorbeeld om een perfect matching-algoritme op te lossen: als het aantal vertices oneven is, voer dan "No Perfect Matching" uit, probeer anders alle mogelijke overeenkomsten.

We zouden willen zeggen dat het algoritme exponentiële tijd vereist, maar in feite kunt u geen Ω(n^2) ondergrens bewijzen met de gebruikelijke definitie van Ω omdat het algoritme in oneven tijd in lineaire tijd loopt. We moeten in plaats daarvan f(n)=Ω(g(n)) definiëren door te zeggen voor een constante c>0 , f(n)≥ cg(n) voor oneindig veel n . Dit geeft een mooie overeenkomst tussen de boven- en ondergrenzen: f(n)=Ω(g(n)) iff f(n) != o(g(n)) .

Referenties

Formele definitie en stelling zijn ontleend aan het boek "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Inleiding tot algoritmen".

Vergelijking van de asymptotische notaties

Laten f(n) en g(n) twee functies zijn die zijn gedefinieerd op de set van de positieve reële getallen, c, c1, c2, n0 zijn positieve reële constanten.

schrijfwijze	f (n) = O (g (n))	f (n) = Ω (g (n))	f (n) = Θ (g (n))	f (n) = o (g (n))	f (n) = ω (g (n))
Formele definitie	∃ 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)
Analogie tussen de asymptotische vergelijking van f, g en reële getallen a, b	a ≤ b	a ≥ b	a = b	a < b	a > b
Voorbeeld	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)
Grafische interpretatie

De asymptotische notaties kunnen als volgt in een Venn-diagram worden weergegeven:

Links

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Inleiding tot algoritmen.