I den här handledningen lär du dig vad asymptotiska notationer är. Du kommer också att lära dig om Big-O-notation, Theta-notation och Omega-notation.
Effektiviteten för en algoritm beror på hur mycket tid, lagring och andra resurser som krävs för att köra algoritmen. Effektiviteten mäts med hjälp av asymptotiska notationer.
En algoritm kanske inte har samma prestanda för olika typer av ingångar. Med ökningen av inmatningsstorleken kommer prestandan att förändras.
Studien av förändring av algoritmens prestanda med förändringen i ingångsstorleksordningen definieras som asymptotisk analys.
Asymptotiska noteringar
Asymptotiska notationer är de matematiska notationerna som används för att beskriva en algoritms gångtid när ingången tenderar mot ett visst värde eller ett begränsande värde.
Till exempel: Vid bubblasortering, när inmatningsmatrisen redan är sorterad, är algoritmens tid linjär, dvs. i bästa fall.
Men när ingångsarrangemanget är i omvänd tillstånd tar algoritmen maximal tid (kvadratisk) för att sortera elementen, dvs. i värsta fall.
När ingångsmatrisen varken är sorterad eller i omvänd ordning tar det genomsnittlig tid. Dessa varaktigheter betecknas med asymptotiska beteckningar.
Det finns huvudsakligen tre asymptotiska notationer:
- Big-O-notation
- Omega-notation
- Theta notation
Big-O Notation (O-notation)
Big-O-notering representerar den övre gränsen för en algoritmes körtid. Således ger det den värsta fallet av en algoritm.
Big-O ger den övre gränsen för en funktion
O (g (n)) = (f (n): det finns positiva konstanter c och n 0 så att 0 ≦ f (n) ≦ cg (n) för alla n ≧ n 0 )
Ovanstående uttryck kan beskrivas som en funktion f(n)tillhör uppsättningen O(g(n))om det finns en positiv konstant cså att den ligger mellan 0och cg(n), för tillräckligt stor n.
För något värde növerstiger inte algoritmens gångtid den tid som tillhandahålls O(g(n)).
Eftersom det ger den sämsta körtiden för en algoritm används den ofta för att analysera en algoritm eftersom vi alltid är intresserade av det värsta fallet.
Omega-notation (Ω-notation)
Omega-notation representerar den nedre gränsen för en algoritmes körtid. Således ger det bästa möjliga komplexiteten hos en algoritm.
Omega ger den nedre gränsen för en funktion
Ω (g (n)) = (f (n): det finns positiva konstanter c och n 0 så att 0 ≦ cg (n) ≦ f (n) för alla n ≧ n 0 )
Ovanstående uttryck kan beskrivas som en funktion f(n)tillhör uppsättningen Ω(g(n))om det finns en positiv konstant cså att den ligger ovanför cg(n), för tillräckligt stor n.
För varje värde av nges den minsta tid som krävs av algoritmen av Omega Ω(g(n)).
Theta Notation (Θ-notation)
Theta-notationen omsluter funktionen ovanifrån och ner. Eftersom den representerar den övre och nedre gränsen för en algoritms körtid används den för analys av en algoritms genomsnittliga fallkomplexitet.
Theta begränsar funktionen inom konstantfaktorer
För en funktion g(n), Θ(g(n))ges av relationen:
Θ (g (n)) = (f (n): det finns positiva konstanter c 1 , c 2 och n 0 så att 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) för alla n ≧ n 0 )
Ovanstående uttryck kan beskrivas som en funktion f(n)tillhör uppsättningen Θ(g(n))om det finns positiva konstanter och sådana att det kan klämmas mellan och för tillräckligt stor n.c1c2c1g(n)c2g(n)
Om en funktion f(n)ligger någonstans däremellan och för alla , så sägs den vara asymptotiskt bunden.c1g(n)c2g(n)n ≧ n0f(n)
