Asymptotisk notationOrdo-notationNä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: 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:
Att T(n) = O(f(n)) innebär alltså att funktionen T(n) inte växer snabbare än funktionen f(n). Några typiska tillämpningar av ordo-notationKonstant tidVi 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 tidI 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 tidAlgoritmen 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 notationEftersom 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 Θ-notationOmega-notationen är mycket lik ordo-notationen: 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)). ExempelVisa 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 algoritmanalysAsymptotisk 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: log21,000 är cirka 10, log21,000,000 cirka 20 och log21,000,000,000 cirka 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. |