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:

ange bildbeskrivning här

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:

ange bildbeskrivning 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.

ange bildbeskrivning här

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:

Ω-notation

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 O-notation Ω-notation Θ-notation

De asymptotiska notationerna kan representeras på ett Venn-diagram enligt följande: Asymptotiska notationer

länkar

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduktion till algoritmer.



Modified text is an extract of the original Stack Overflow Documentation
Licensierat under CC BY-SA 3.0
Inte anslutet till Stack Overflow