Asymptotisk notation

Ordo-notation

När vi studerar tidskomplexiteten T(n) för en algoritm uttryckt i antalet karakteristiska operationer så är det sällan meningsfullt att räkna ut resultatet exakt. Oftast är vi endast intresserade av hur snabbt T(n) växer som en funktion av problemstorleken n. Ordo-notation är ett bekvämt sätt att beskriva en funktions asymptotiska beteende, det vill säga hur snabbt den växer. Vi börjar med en formell matematisk definition:

Definition: Låt T(n) och f(n) vara två positiva funktioner. Vi skriver T(n) = O(f(n)), vilket utläses T(n) är ordo f(n), om det finns positiva konstanter M och n0 så att T(n) ≤ Mf(n) för alla n ≥ n0.

En bild får hjälpa till att illustrera definitionen:

Ordo-notation

Att T(n) = O(f(n)) innebär att funktionen T(n) inte växer snabbare än f(n).

Några typiska tillämpningar av ordo-notation

Konstant tid

Vi börjar med enklast möjliga exempel: T(n) = O(1). Enligt definitionen betyder detta att det finns konstanter M och n0 så att T(n) ≤ M när n ≥ n0. Att T(n) är O(1) innebär alltså att T(n) är mindre än någon viss fix konstant, vars värde inte anges, för alla tillräckligt stora värden på n. En algoritm för vilken T(n) = O(1) sägs ha konstant tidskomplexitet.

Linjär tid

I föregående avsnitt visade vi att algoritmen max(A) som beräknar det maximala värdet i en vektor har tidskomplexiteten T(n) = n -1. Med ordo-notation kan vi därför skriva T(n) = O(n). (Detta kan man se genom att, till exempel, välja både M = 1 och n0 = 1, ty T(n) = n - 1  ≤ 1n när n ≥ 1.) Vi säger att en sådan algoritmen har linjär tidskomplexitet

Kvadratisk tid

Algoritmen reverse(A) från föregående avsnitt hade tidskomplexiteten T(n) = n2/2 - n/2. Med ordo-notation kan vi skriva T(n) = O(n2) och vi säger att algoritmen har kvadratisk tidskomplexitet.

Släpphänt notation

Eftersom O-notationen är baserad på villkoret att T(n) ≤ M(f(n)) så kan man använda notationen även när f(n) växer mycket snabbare än T(n). Att

T(n) = n -1 = O(n2)

är till exempel sant, men inte särskilt användbart. I nästa avsnitt introducerar vi notation som gör det möjligt att även ange undre gränser för hur snabbt en funktion växer.

Ω- och Θ-notation

Omega-notationen är mycket lik ordo-notationen:

Definition: Låt T(n) och f(n) vara två positiva funktioner. Vi skriver T(n) = Ω(f(n)), vilket utläses T(n) är omega f(n), om det finns fixa positiva konstanter M och n0 så att T(n) ≥ M(f(n)) för alla n ≥ n0.

Den enda skillnaden är att vi har vänt på ett olikhetstecken och det följer därför att T(n) = Ω(f(n)) om och endast om f(n) = O(T(n)).

Slutligen inför vi notationen T(n) = Θ(f(n)) som betyder att T(n) är både O(f(n)) och Ω(f(n)).

Exempel

Vi visar att funktionen T(n) = 3n3 + 2n + 7 = Θ(n3).

Om n ≥ 1 så gäller att T(n) = 3n3 + 2n + 7 ≤ 3n3 + 2n3 + 7n3 = 12n3. Funktionen är alltså O(n3). Å andra sidan är T(n) = 3n3 + 2n + 7 > n3 för alla positiva n. Funktionen är alltså även Ω(n3) och därmed också Θ(n3).

Praktiska konsekvenser av algoritmanalys

Asymptotisk tidskomplexitet och ordo-notation är ett kraftfullt verktyg för att beskriva effektiviteten hos en algoritm. Här kommer två typiska exempel.

O(n log n)

En algoritm vars tidskomplexitet i värstafall är O(n log n) skalar mycket väl. I så fall kan vi nämligen vara säkra på att körtiden är mindre än M n log n, för någon konstant M. Detta uttryck växer mycket långsamt: log2 1,000 ≈ 10, log2 1,000,000 ≈ 20 och log2 1,000,000,000 ≈ 30. Algoritmens tidskomplexitet är alltså nära nog linjär: det tar ungefär dubbelt så lång tid att lösa en dubbelt så stor probleminstans.

Ω(n2)

Algoritmer vars tidskomplexitet är Ω(n2) är bara användbara för mindre probleminstanser: n bör inte vara mer än några tusen. Redan när  n = 10,000 så blir n2 = 100,000,000. En algoritm med kvadratisk tidskomplexitet skalar dåligt: en tio gånger så stor probleminstans tar hundra gånger så lång tid att lösa.

Stefan Nilsson