algorithm
Algoritmkomplexitet
Sök…
Anmärkningar
Alla algoritmer är en lista med steg för att lösa ett problem. Varje steg har beroenden på någon uppsättning tidigare steg, eller början av algoritmen. Ett litet problem kan se ut enligt följande:
Denna struktur kallas en riktad acyklisk graf, eller DAG för kort. Länkarna mellan varje nod i diagrammet representerar beroenden i arbetsordningens ordning, och det finns inga cykler i grafen.
Hur sker beroenden? Ta till exempel följande kod:
total = 0
for(i = 1; i < 10; i++)
total = total + i
I denna psuedocode är varje iteration av for-loop beroende av resultatet från föregående iteration eftersom vi använder det värde som beräknades i den föregående iterationen i den här nästa iterationen. DAG för denna kod kan se ut så här:
Om du förstår denna representation av algoritmer kan du använda den för att förstå algoritmens komplexitet när det gäller arbete och spännvidd.
Arbete
Arbete är det faktiska antalet operationer som behöver utföras för att uppnå målet för algoritmen för en given ingångsstorlek n .
Spänna
Span kallas ibland som den kritiska vägen, och är det minsta antalet steg en algoritm måste göra för att uppnå algoritmens mål.
Följande bild belyser grafen för att visa skillnaderna mellan arbete och spännvidd på vårt prov DAG.
Arbetet är antalet noder i diagrammet som helhet. Detta representeras av diagrammet till vänster ovan. Spännvidden är den kritiska vägen eller den längsta vägen från början till slut. När arbete kan utföras parallellt representerar de gula markerade noderna till höger span, det minsta antalet steg som krävs. När arbetet måste utföras seriellt är spannet detsamma som arbetet.
Både arbete och span kan utvärderas oberoende i termer av analys. En algoritms hastighet bestäms av spännvidden. Mängden beräknad effekt som krävs bestäms av arbetet.
Big-Theta notation
Till skillnad från Big-O-notation, som endast representerar övre gränsen för drifttiden för någon algoritm, är Big-Theta en snäv gräns; både övre och nedre gräns. Tätt bundet är mer exakt, men också svårare att beräkna.
Big-Theta-notationen är symmetrisk: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))
Ett intuitivt sätt att förstå det är att f(x) = Ө(g(x)) betyder att graferna för f (x) och g (x) växer i samma takt, eller att graferna "uppför sig" på samma sätt för stora tillräckligt med värden på x.
Det fullständiga matematiska uttrycket för Big-Theta-notationen är som följer:
Ө (f (x)) = {g: N 0 -> R och c 1, c 2, n 0> 0, där c 1 <abs (g (n) / f (n)), för varje n> n 0 och abs är det absoluta värdet}
Ett exempel
Om algoritmen för ingången n tar 42n^2 + 25n + 4 operationer att avsluta, säger vi att det är O(n^2) , men är också O(n^3) och O(n^100) . Men det är Ө(n^2) och det är inte Ө(n^3) , Ө(n^4) etc. Algoritm som är Ө(f(n)) är också O(f(n)) , men inte vice versa!
Formell matematisk definition
Ө(g(x)) är en uppsättning funktioner.
Ө(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}
Eftersom Ө(g(x)) är en uppsättning, kan vi skriva f(x) ∈ Ө(g(x)) att indikera att f(x) är medlem i Ө(g(x)) . Istället kommer vi vanligtvis att skriva f(x) = Ө(g(x)) att uttrycka samma uppfattning - det är det vanliga sättet.
När Ө(g(x)) visas i en formel, tolkar vi den som står för någon anonym funktion som vi inte bryr oss att namnge. Exempelvis betyder ekvationen T(n) = T(n/2) + Ө(n) , T(n) = T(n/2) + f(n) där f(n) är en funktion i uppsättningen Ө(n) .
Låt f och g vara två funktioner definierade på någon delmängd av de verkliga siffrorna. Vi skriver f(x) = Ө(g(x)) som x->infinity om och bara om det finns positiva konstanter K och L och ett reellt tal x0 så att det gäller:
K|g(x)| <= f(x) <= L|g(x)| för alla x >= x0 .
Definitionen är lika med:
f(x) = O(g(x)) and f(x) = Ω(g(x))
En metod som använder gränser
om limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) dvs gränsen finns och den är positiv, då är f(x) = Ө(g(x))
Vanliga komplexitetsklasser
| namn | Notation | n = 10 | n = 100 |
|---|---|---|---|
| Konstant | Ө (1) | 1 | 1 |
| Logaritmisk | Ө (log (n)) | 3 | 7 |
| Linjär | Ө (n) | 10 | 100 |
| Linearithmic | Ө (n * log (n)) | 30 | 700 |
| Kvadratisk | Ө (n ^ 2) | 100 | 10 000 |
| Exponentiell | Ө (2 ^ n) | 1 024 | 1.267650e + 30 |
| Fakultet | Ө (n!) | 3 628 800 | 9.332622e + 157 |
Big-Omega Notation
Ω-notation används för asymptotisk nedre gräns.
Formell definition
Låt f(n) och g(n) vara två funktioner definierade i uppsättningen av de positiva verkliga siffrorna. Vi skriver f(n) = Ω(g(n)) om det finns positiva konstanter c och n0 så att:
0 ≤ cg(n) ≤ f(n) for all n ≥ n0 .
anteckningar
f(n) = Ω(g(n)) betyder att f(n) växer asymptotiskt inte långsammare än g(n) . Vi kan också säga om Ω(g(n)) när algoritmanalys inte är tillräckligt för uttalande om Θ(g(n)) eller / och O(g(n)) .
Från definitionerna av notationer följer teorem:
För två funktioner f(n) och g(n) vi f(n) = Ө(g(n)) om och bara om f(n) = O(g(n)) and f(n) = Ω(g(n)) .
Grafiskt Ω-notation kan representeras enligt följande:
Till exempel kan vi ha f(n) = 3n^2 + 5n - 4 . Sedan f(n) = Ω(n^2) . Det är också korrekt f(n) = Ω(n) , eller till och med f(n) = Ω(1) .
Ett annat exempel för att lösa perfekt matchande algoritm: Om antalet vertikaler är udda, mata ut "No Perfect Matching" annars prova alla möjliga matchningar.
Vi skulle vilja säga att algoritmen kräver exponentiell tid men i själva verket kan du inte bevisa en Ω(n^2) nedre gräns med den vanliga definitionen av Ω eftersom algoritmen går i linjär tid för o udda. Vi bör istället definiera f(n)=Ω(g(n)) genom att säga för någon konstant c>0 , f(n)≥ cg(n) för oändligt många n . Detta ger en fin korrespondens mellan övre och nedre gränser: f(n)=Ω(g(n)) iff f(n) != o(g(n)) .
referenser
Formell definition och teorem är hämtade från boken "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduktion till algoritmer".
Jämförelse av de asymptotiska notationerna
Låt f(n) och g(n) vara två funktioner definierade på uppsättningen av de positiva reella siffrorna, c, c1, c2, n0 är positiva reella konstanter.
| Notation | f (n) = O (g (n)) | f (n) = Ω (g (n)) | f (n) = Θ (g (n)) | f (n) = o (g (n)) | f (n) = ω (g (n)) |
|---|---|---|---|---|---|
| Formell definition | ∃ 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) |
Analog mellan den asymptotiska jämförelsen av f, g och reella tal a, b | a ≤ b | a ≥ b | a = b | a < b | a > b |
| Exempel | 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) |
| Grafisk tolkning |  | |  |
De asymptotiska notationerna kan representeras på ett Venn-diagram enligt följande: 
länkar
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduktion till algoritmer.
