Wie weiß man, welche notation Zeit Komplexität der Analyse zu verwenden?

https://cs.stackexchange.com/questions/57

16-10-2019
|

Frage

In den meisten einführenden Algorithmus Klassen, Notationen wie $O$ (Big O) und $ heta$ ist, eingeführt werden, und würde ein student in der Regel lernen, verwenden Sie eine der folgenden, die Zeit zu finden Komplexität.

Es gibt jedoch auch andere Schreibweisen wie " $o$, $\Omega$ und $\omega$.Gibt es bestimmte Szenarien, in denen eine notation wäre vorzuziehen, eine andere?

Lösung

Sie beziehen sich auf die Landau-notation.Sie sind nicht verschiedene Symbole, die für die gleiche Sache, haben aber völlig unterschiedliche Bedeutungen.Die eine ist "bevorzugt" ist, hängt ganz von der gewünschten Aussage.

$f \in \cal{O}(g)$ bedeutet, dass $f$ wächst höchstens so schnell wie $g$, und asymptotisch bis auf einen Konstanten Faktor;betrachten Sie es als $\leq$.$f \in o(g)$ ist die strengere form, D. H.$<$.

$f \in \Omega(g)$ ist die symmetrische Bedeutung:$f$ wächst mindestens so schnell wie $g$.$\omega$ ist sein strenger Vetter.Sie können sehen, dass $f \in \Omega(g)$ ist äquivalent zu $g \in \cal{O}(f)$.

$f \in heta(g)$ bedeutet, dass $f$ wächst in etwa so schnell wie $g$;formal $f \in \cal{O}(g) \cap \Omega(g)$.$f \sim g$ (asymptotische Gleichheit) ist die stärkere form.Wir oft bedeuten, dass $ heta$, wenn wir $\cal{O}$.

Beachten Sie, dass $\cal{O}(g)$ und seine Geschwister sind funktionsklassen.Es ist wichtig, sehr bewusst und deren genaue Definitionen -- das kann unterscheiden sich je nachdem, wer spricht,--, wenn dabei die "Arithmetik" mit Ihnen.

Wenn Beweise von Dingen, kümmern uns um die Arbeit mit Ihrer genauen definition.Es gibt viele Definitionen für die Landau-Symbole um (alle mit den gleichen grundlegenden intuition), von denen einige sind gleichwertig, auf ein paar Sätze auf Funktionen, aber nicht auf andere.

Empfohlene Lektüre:

Wenn Sie Interesse an der Nutzung der Landau-notation in eine strenge und sound-Art, die Sie interessieren können in der kürzlich erschienenen Arbeit von Rutanen et al.[1].Formulieren Sie notwendige und hinreichende Kriterien für die asymptotische notation, wie wir Sie verwenden bei der Algorithmik, zeigen, dass die gemeinsame definition nicht erfüllen, Sie und liefern ein (die, in der Tat) brauchbare definition.

Eine Allgemeine definition der O-notation für Analyse-Algorithmus von K.Rutanen et al.(2015)

Andere Tipps

Big O: Obergrenze

"Big O" ($ O $) ist bei weitem die häufigste. Wenn Sie die Komplexität eines Algorithmus analysieren, ist die meisten zählt, wie schnell die Laufzeit wächst, wenn die Größe des Eingangs wächst. Grundsätzlich möchten wir wissen, dass das Ausführen des Algorithmus nicht "zu lang" dauern wird. Wir können dies nicht in tatsächlichen Zeiteinheiten (Sekunden) ausdrücken, da dies von der genauen Implementierung abhängt (wie das Programm geschrieben ist, wie gut der Compiler ist, wie schnell der Prozessor der Maschine ist,…). Wir bewerten also, was nicht von solchen Details abhängt. So lange dauert es, bis wir den Algorithmus ausgeführt haben, wenn wir ihn größere Eingaben füttern. Und wir kümmern uns hauptsächlich darum, wenn wir sicher sein können, dass das Programm fertig ist. Daher möchten wir normalerweise wissen, dass es so viel Zeit oder weniger dauert.

Zu sagen, dass ein Algorithmus eine Laufzeit von $ O (f (n)) $ für eine Eingangsgröße $ n $ hat, bedeutet, dass es einige konstante $ k $ gibt, so dass der Algorithmus höchstens $ k , f (n ) $ Schritte, dh die Laufzeit des Algorithmus wächst höchstens so schnell wie $ F $ (bis zu einem Skalierungsfaktor). $ T (n) $ Die Laufzeit des Algorithmus für die Eingabegröße $ n $, $ O (n) $ $ informell bedeutet, dass $ t (n) le f (n) $ bis zu einem Skalierungsfaktor bis zu einem Skalierungsfaktor.

Untergrenze

Manchmal ist es nützlich, mehr Informationen als eine Obergrenze zu haben. $ Omega $ ist das Gegenteil von $ o $: Es drückt aus, dass eine Funktion mindestens so schnell wächst wie eine andere. $ T (n) = omega (g (n)) $ bedeutet, dass $ t (n) ge k 'g (n) $ für einige konstante $ k' $ oder informell ausdrücken, $ t (n) Ge G (n) $ bis zu einem Skalierungsfaktor.

Wenn die Laufzeit des Algorithmus genau bestimmt werden kann, kombiniert $ theta $ $ o $ und $ Omega $: Es drückt aus, dass die Wachstumsrate einer Funktion bis zu einem Skalierungsfaktor bekannt ist. $ T (n) = theta (h (n)) $ bedeutet, dass $ k h (n) ge t (n) ge k 'h (n) $ für einige Konstanten $ k $ und $ k' $. Informell gesehen, $ T (n) ca. (n) $ bis zu einem Skalierungsfaktor.

Weitere Überlegungen

Die „kleinen“ $ O $ und $ Omega $ werden in der Komplexitätsanalyse weitaus weniger verwendet. Little $ o $ ist stärker als Big $ o $; Wenn $ o $ ein Wachstum angibt, das nicht schneller ist, zeigt $ o $, dass das Wachstum streng langsamer ist. Umgekehrt weist $ omega $ ein streng schnelleres Wachstum an.

Ich war in der obigen Diskussion etwas informell. Wikipedia Hat Formalldefinitionen und einen mathematischen Ansatz.

Denken Sie daran, dass die Verwendung des gleichen Zeichens in $ t (n) = o (f (n)) $ und dergleichen eine Fehlbezeichnung ist. Streng genommen ist $ o (f (n)) $ eine Reihe von Funktionen der Variablen $ n $, und wir sollten $ t in o (f) $ schreiben.

Beispiel: Einige Sortieralgorithmen

Lassen Sie mich ein Beispiel geben, da dies eher trocken ist. Die meisten Sortieralgorithmen haben einen quadratischen Worst -Case -Laufzeit, dh für die Eingabe von Größe $ n $, die Laufzeit des Algorithmus beträgt $ o (n^2) $. Zum Beispiel, Auswahlsorten hat eine $ o (n^2) $ Run-Zeit, da die Auswahl des Elements $ k $ th $ nk $ vergleiche für insgesamt $ n (n-1)/2 $ -Ge-Vergleiche erfordert. Tatsächlich ist die Anzahl der Vergleiche immer genau $ n (n-1)/2 $, was als $ N^2 $ wächst. Wir können also genauer in Bezug auf die Zeitkomplexität der Selektionssorte sein: Es ist $ theta (n^2) $.

Jetzt nimm Zusammenführen, sortieren. Zusammenführungsart ist auch quadratisch ($ o (n^2) $). Das ist wahr, aber nicht sehr präzise. Merge -Sortierung hat in der Tat eine Laufzeit von $ o (n : mathrm {lg} (n)) $ im schlimmsten Fall. Wie Selektionssorte ist der Arbeitsfluss von Merge Sort im Wesentlichen unabhängig von der Form des Eingangs, und seine Laufzeit ist immer $ n : mathrm {lg} (n) $ bis zu einem konstanten multiplikativen Faktor, dh es ist $ theta (n : mathhrm {lg} (n)) $.

Als nächstes überlegen schnelle Sorte. Quicksort ist komplexer. Es ist sicherlich $ o (n^2) $. Darüber hinaus ist der schlimmste Fall von Quicksort quadratisch: die schlimmsten Fall ist $ theta (n^2) $. Der beste Fall von QuickSort (wenn die Eingabe bereits sortiert ist) ist jedoch linear: Das Beste, was wir für eine untere Niedrigung an Quicksort im Allgemeinen sagen können, ist $ Omega (n) $. Ich werde den Beweis hier nicht wiederholen, aber der Durchschnitt Komplexität von Quicksort (der durchschnittliche Durchschnitt aller möglichen Permutationen der Eingabe) ist $ theta (n : mathhrm {lg} (n)) $.

Es gibt allgemeine Ergebnisse zur Komplexität der Sortierung von Algorithmen in gemeinsamen Einstellungen. Angenommen, ein Sortieralgorithmus kann jeweils nur zwei Elemente mit einem Ja-or-No-Ergebnis (entweder $ x le y $ oder $ x> y $) vergleichen. Dann ist es offensichtlich, dass die Laufzeit eines Sortieralgorithmus immer $ Omega (n) $ ist (wobei $ n $ die Anzahl der zu sortierenden Elemente ist), da der Algorithmus mindestens einmal vergleichen muss, um zu wissen, wo es passt . Diese untere Grenze kann beispielsweise erfüllt werden, wenn der Eingang bereits sortiert ist und der Algorithmus lediglich jedes Element mit dem nächsten vergleicht und sie in Ordnung hält (das sind $ n-1 $ Vergleiche). Was weniger offensichtlich ist, ist, dass die maximal Die Laufzeit ist notwendigerweise $ omega (n : mathrm {lg} (n)) $. Es ist möglich, dass der Algorithmus manchmal weniger Vergleiche darstellt, aber es muss einige konstante $ k $ geben, so dass für jede Eingabegröße $ n $ mindestens einen Eingang gibt, auf den der Algorithmus mehr als $ k n mathrm {macht { LG} (n) $ Vergleiche. Die Idee des Beweises ist es, den Entscheidungsbaum des Algorithmus zu erstellen, dh die Entscheidung, die der Algorithmus aus dem Ergebnis jedes Vergleichs nimmt. Da jeder Vergleich ein Ja-oder-nicht-Ergebnis zurückgibt, ist der Entscheidungsbaum ein binärer Baum. Es gibt $ n! $ Mögliche Permutationen des Inputs, und der Algorithmus muss zwischen allen unterscheiden, sodass die Größe des Entscheidungsbaums $ n! $ Ist. Da der Baum ein binärer Baum ist, dauert er eine Tiefe von $ theta ( mathrm {lg} (n!)) Die Tiefe ist die maximale Anzahl von Entscheidungen, die der Algorithmus trifft. Daher beinhaltet das Ausführen des Algorithmus mindestens so viele Vergleiche: Die maximale Laufzeit beträgt $ omega (N : mathrm {lg} (n)) $.

¹ _{Oder anderer Ressourcenverbrauch wie Speicherplatz. In dieser Antwort halte ich nur die Laufzeit.}

Typischerweise wird $ o $ für die Angabe von oberen Bounds verwendet (eine Schätzung von oben), während $ Omega $ verwendet wird, um niedrigere Bounds (eine Schätzung von unten) zu sagen, und $ theta $ wird verwendet, wenn sie übereinstimmen, in welcher Fall können Sie (normalerweise) $ theta $ verwenden, um das Ergebnis anzugeben.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit cs.stackexchange