I denne vejledning lærer du, hvad asymptotiske notationer er. Du vil også lære om Big-O notation, Theta notation og Omega notation.
Effektiviteten af en algoritme afhænger af den tid, lagring og andre ressourcer, der kræves for at udføre algoritmen. Effektiviteten måles ved hjælp af asymptotiske notationer.
En algoritme har muligvis ikke den samme ydeevne for forskellige typer input. Med stigningen i inputstørrelsen ændres ydeevnen.
Undersøgelsen af ændring i algoritmens ydeevne med ændringen i rækkefølgen af inputstørrelsen er defineret som asymptotisk analyse.
Asymptotiske notationer
Asymptotiske notationer er de matematiske notationer, der bruges til at beskrive en algoritmes kørselstid, når input tendens til en bestemt værdi eller en begrænsende værdi.
For eksempel: Når boble sorteres, når input-arrayet allerede er sorteret, er den tid, det tager af algoritmen, lineær, dvs. det bedste tilfælde.
Men når input-arrayet er i omvendt tilstand, tager algoritmen den maksimale tid (kvadratisk) til at sortere elementerne, dvs. i værste fald.
Når inputmatrixen hverken er sorteret eller i omvendt rækkefølge, tager det gennemsnitlig tid. Disse varigheder er angivet ved hjælp af asymptotiske notationer.
Der er hovedsageligt tre asymptotiske notationer:
- Big-O notation
- Omega-notation
- Theta notation
Big-O Notation (O-notation)
Big-O-notation repræsenterer den øvre grænse for en algoritmes driftstid. Således giver det en worst-case kompleksitet af en algoritme.
Big-O giver den øvre grænse for en funktion
O (g (n)) = (f (n): der findes positive konstanter c og n 0 således at 0 ≦ f (n) ≦ cg (n) for alle n ≧ n 0 )
Ovenstående udtryk kan beskrives som en funktion, der f(n)hører til sættet, O(g(n))hvis der findes en positiv konstant, csåledes at den ligger mellem 0og cg(n)for tilstrækkelig stor n.
For en hvilken som helst værdi af nkrydser en algoritmes tid ikke den tid, der leveres af O(g(n)).
Da det giver worst-case driftstid for en algoritme, bruges den i vid udstrækning til at analysere en algoritme, da vi altid er interesserede i worst-case scenariet.
Omega-notation (Ω-notation)
Omega-notation repræsenterer den nedre grænse for en algoritmes driftstid. Således giver det den bedste case kompleksitet af en algoritme.
Omega giver den nedre grænse for en funktion
Ω (g (n)) = (f (n): der findes positive konstanter c og n 0 således at 0 ≦ cg (n) ≦ f (n) for alle n ≧ n 0 )
Ovenstående udtryk kan beskrives som en funktion, der f(n)hører til sættet, Ω(g(n))hvis der findes en positiv konstant, csåledes at den ligger over cg(n), for tilstrækkelig stor n.
For enhver værdi af ner den minimale tid, der kræves af algoritmen, givet af Omega Ω(g(n)).
Theta Notation (Θ-notation)
Theta notation omslutter funktionen ovenfra og nedenfra. Da det repræsenterer den øvre og nedre grænse for en algoritmes driftstid, bruges den til at analysere den gennemsnitlige sags kompleksitet af en algoritme.
Theta afgrænser funktionen inden for konstante faktorer
For en funktion g(n), Θ(g(n))er givet ved relationen:
Θ (g (n)) = (f (n): der findes positive konstanter c 1 , c 2 og n 0 således at 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) for alle n ≧ n 0 )
Ovenstående udtryk kan beskrives som en funktion, der f(n)hører til sættet, Θ(g(n))hvis der findes positive konstanter og sådan, at det kan klemmes mellem og i tilstrækkelig stor n.c1c2c1g(n)c2g(n)
Hvis en funktion f(n)ligger hvor som helst imellem og for alle , siges det at være asymptotisk tæt bundet.c1g(n)c2g(n)n ≧ n0f(n)
