algorithm
Algorithmus-Komplexität
Suche…
Bemerkungen
Alle Algorithmen sind eine Liste von Schritten, um ein Problem zu lösen. Jeder Schritt hat Abhängigkeiten von einigen vorherigen Schritten oder vom Start des Algorithmus. Ein kleines Problem könnte wie folgt aussehen:
Diese Struktur wird gerichteter azyklischer Graph oder kurz DAG genannt. Die Verknüpfungen zwischen den einzelnen Knoten in der Grafik stellen Abhängigkeiten in der Reihenfolge der Operationen dar und es gibt keine Zyklen in der Grafik.
Wie passieren Abhängigkeiten? Nehmen Sie zum Beispiel den folgenden Code:
total = 0
for(i = 1; i < 10; i++)
total = total + i
In diesem Pseudocode hängt jede Iteration der for-Schleife vom Ergebnis der vorherigen Iteration ab, da in dieser nächsten Iteration der in der vorherigen Iteration berechnete Wert verwendet wird. Die DAG für diesen Code könnte folgendermaßen aussehen:
Wenn Sie diese Darstellung von Algorithmen verstehen, können Sie sie verwenden, um die Komplexität der Algorithmen in Bezug auf Arbeit und Spannweite zu verstehen.
Arbeit
Arbeit ist die tatsächliche Anzahl von Operationen, die ausgeführt werden müssen, um das Ziel des Algorithmus für eine gegebene Eingabegröße n .
Spanne
Span wird manchmal als kritischer Pfad bezeichnet und ist die geringste Anzahl von Schritten, die ein Algorithmus ausführen muss, um das Ziel des Algorithmus zu erreichen.
Das folgende Bild hebt die Grafik hervor, um die Unterschiede zwischen Arbeit und Spanne unserer Beispiel-DAG zu zeigen.
Die Arbeit ist die Anzahl der Knoten im Graphen insgesamt. Dies wird durch die Grafik oben links dargestellt. Die Spanne ist der kritische Pfad oder der längste Pfad vom Anfang bis zum Ende. Wenn parallel gearbeitet werden kann, repräsentieren die gelb hervorgehobenen Knoten auf der rechten Seite die Spannweite, die geringste Anzahl von Schritten. Wenn seriell gearbeitet werden muss, ist die Spannweite der Arbeit gleich.
Sowohl Arbeit als auch Spannweite können unabhängig von der Analyse ausgewertet werden. Die Geschwindigkeit eines Algorithmus wird durch die Spanne bestimmt. Die benötigte Rechenleistung wird von der Arbeit bestimmt.
Big-Theta-Notation
Im Gegensatz zur Big-O-Notation, die für einige Algorithmen nur die Obergrenze der Laufzeit darstellt, ist Big-Theta eine enge Grenze. sowohl obere als auch untere Grenze. Enge Bindung ist präziser, aber auch schwieriger zu berechnen.
Die Big-Theta-Notation ist symmetrisch: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))
Ein intuitiver Weg, dies zu verstehen, ist, dass f(x) = Ө(g(x)) bedeutet, dass die Graphen von f (x) und g (x) in der gleichen Rate wachsen oder dass sich die Graphen ähnlich verhalten genug Werte von x.
Der vollständige mathematische Ausdruck der Big-Theta-Notation lautet wie folgt:
(F (x)) = {g: N 0 -> R und c 1 , c 2 , n 0 > 0, wobei c 1 <abs (g (n) / f (n)) für jedes n> n ist 0 und abs ist der absolute Wert}
Ein Beispiel
Wenn der Algorithmus für die Eingabe n 42n^2 + 25n + 4 Operationen zum Beenden benötigt, sagen wir, dass dies O(n^2) , aber auch O(n^3) und O(n^100) . Es ist jedoch Ө(n^2) und es ist nicht Ө(n^3) , Ө(n^4) usw. Der Algorithmus Ө(f(n)) ist auch O(f(n)) , aber nicht umgekehrt!
Formale mathematische Definition
Ө(g(x)) ist eine Reihe von Funktionen.
Ө(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}
Da Ө(g(x)) eine Menge ist, könnten wir f(x) ∈ Ө(g(x)) schreiben, um anzuzeigen, dass f(x) ein Ө(g(x)) von Ө(g(x)) . Stattdessen schreiben wir normalerweise f(x) = Ө(g(x)) , um dieselbe Vorstellung auszudrücken - so ist es üblich.
Wann immer Ө(g(x)) in einer Formel vorkommt, interpretieren wir es als für eine anonyme Funktion, die wir nicht nennen möchten. Beispielsweise bedeutet die Gleichung T(n) = T(n/2) + Ө(n) , T(n) = T(n/2) + f(n) wobei f(n) eine Funktion in der Menge Ө(n) .
Sei f und g zwei Funktionen, die in einer Teilmenge der reellen Zahlen definiert sind. Wir schreiben f(x) = Ө(g(x)) genau dann als f(x) = Ө(g(x)) x0 x->infinity wenn positive Konstanten K und L und eine reelle Zahl x0 , die gilt:
K|g(x)| <= f(x) <= L|g(x)| für alle x >= x0 .
Die Definition ist gleich:
f(x) = O(g(x)) and f(x) = Ω(g(x))
Eine Methode, die Grenzen verwendet
wenn limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) dh der Grenzwert existiert und ist positiv, dann ist f(x) = Ө(g(x))
Häufige Komplexitätsklassen
| Name | Notation | n = 10 | n = 100 |
|---|---|---|---|
| Konstante | Ө (1) | 1 | 1 |
| Logarithmisch | Log (log (n)) | 3 | 7 |
| Linear | Ө (n) | 10 | 100 |
| Linearithmisch | Ө (n * log (n)) | 30 | 700 |
| Quadratisch | N (n ^ 2) | 100 | 10 000 |
| Exponentiell | Ө (2 ^ n) | 1 024 | 1,267650e + 30 |
| Fakultät | Ө (n!) | 3 628 800 | 9,332622e + 157 |
Big-Omega-Notation
Die Ω-Notation wird für die asymptotische Untergrenze verwendet.
Formale Definition
Sei f(n) und g(n) zwei Funktionen, die in der Menge der positiven reellen Zahlen definiert sind. Wir schreiben f(n) = Ω(g(n)) wenn es positive Konstanten c und n0 so dass:
0 ≤ cg(n) ≤ f(n) for all n ≥ n0 .
Anmerkungen
f(n) = Ω(g(n)) bedeutet, dass f(n) asymptotisch nicht langsamer wächst als g(n) . Wir können auch über Ω(g(n)) sagen, wenn die Algorithmusanalyse für Aussagen über Θ(g(n)) oder / und O(g(n)) nicht ausreicht.
Aus den Definitionen der Notationen folgt der Satz:
Für zwei beliebige Funktionen f(n) und g(n) gilt f(n) = Ө(g(n)) genau dann, wenn f(n) = O(g(n)) and f(n) = Ω(g(n)) .
Grafisch kann die Ω-Notation wie folgt dargestellt werden:
Zum Beispiel sei f(n) = 3n^2 + 5n - 4 . Dann ist f(n) = Ω(n^2) . Es ist auch korrekt f(n) = Ω(n) oder sogar f(n) = Ω(1) .
Ein weiteres Beispiel für die Lösung eines perfekten Übereinstimmungsalgorithmus: Wenn die Anzahl der Eckpunkte ungerade ist, geben Sie "No Perfect Matching" aus.
Wir möchten sagen, dass der Algorithmus exponentielle Zeit benötigt, tatsächlich können Sie jedoch keine Ω(n^2) -Untergrenze mit der üblichen Definition von Ω da der Algorithmus linear für n odd läuft. Wir sollten stattdessen f(n)=Ω(g(n)) indem wir für eine Konstante c>0 , f(n)≥ cg(n) für unendlich viele n sagen. Dies ergibt eine schöne Entsprechung zwischen oberen und unteren Grenzen: f(n)=Ω(g(n)) iff f(n) != o(g(n)) .
Verweise
Formale Definition und Satz stammen aus dem Buch "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Einführung in Algorithmen".
Vergleich der asymptotischen Notationen
Sei f(n) und g(n) zwei Funktionen, die in der Menge der positiven reellen Zahlen definiert sind, c, c1, c2, n0 sind positive Konstanten.
| Notation | f (n) = O (g (n)) | f (n) = Ω (g (n)) | f (n) = Θ (g (n)) | f (n) = o (g (n)) | f (n) = ω (g (n)) |
|---|---|---|---|---|---|
| Formale 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) |
Analogie zwischen dem asymptotischen Vergleich von f, g und reellen Zahlen a, b | a ≤ b | a ≥ b | a = b | a < b | a > b |
| Beispiel | 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) |
| Grafische Interpretation |  | |  |
Die asymptotischen Notationen können in einem Venn-Diagramm wie folgt dargestellt werden: 
Links
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen.