Woher weiß man, welche Notation der Zeitkomplexitätsanalyse zu verwenden ist?

90

In den meisten einführenden Algorithmusklassen werden Notationen wie (Big O) und Θ verwendetOΘ eingeführt, und ein Schüler lernt normalerweise, die Zeitkomplexität mit einer dieser Methoden zu bestimmen.

Es gibt jedoch auch andere Bezeichnungen wie , Ω und ω . Gibt es spezielle Szenarien, in denen eine Notation einer anderen vorzuziehen wäre?oΩω

Jack H
quelle
2
Es ist nicht so sehr vorzuziehen, wie zutreffend ...
vzn

Antworten:

76

Sie beziehen sich auf die Landau-Notation . Sie sind keine unterschiedlichen Symbole für dasselbe Ding, sondern haben ganz unterschiedliche Bedeutungen. Welches "vorzuziehen" ist, hängt ganz von der gewünschten Aussage ab.

bedeutet, dass f höchstens so schnell wächst wie g , asymptotisch und bis zu einem konstanten Faktor; Betrachten Sie es als . f o ( g ) ist die strengere Form, dh < .fO(g)fgfo(g)<

hat die symmetrische Bedeutung: f wächst mindestens so schnell wie g . ω ist sein strengerer Cousin. Sie können sehen, dass f Ω ( g ) äquivalent zu g O ( f ) ist .fΩ(g)fgωfΩ(g)gO(f)

bedeutet, dass f ungefähr so ​​schnell wächst wie g ; formal f O ( g ) Ω ( g ) . f g (asymptotische Gleichheit) ist die stärkere Form. Wir meinen oft Θ, wenn wir O verwenden .fΘ(g)fgfO(g)Ω(g)fgΘO

Beachten Sie, wie und seine Geschwister Funktionsklassen sind . Es ist wichtig, sich dessen und ihrer genauen Definitionen - die je nach Gesprächspartner unterschiedlich sein können - bewusst zu sein, wenn mit ihnen "arithmetisch" gearbeitet wird.O(g)

Achten Sie beim Beweisen darauf, mit Ihrer genauen Definition zu arbeiten. Es gibt viele Definitionen für Landau-Symbole (alle mit derselben grundlegenden Intuition), von denen einige für einige Mengen von Funktionen, für andere jedoch nicht gleichwertig sind.

Vorgeschlagene Literatur:

Wenn Sie daran interessiert sind, die Landau-Notation rigoros und solide anzuwenden, interessieren Sie sich möglicherweise für aktuelle Arbeiten von Rutanen et al. [1] Sie formulieren notwendige und ausreichende Kriterien für die asymptotische Notation, wie wir sie in der Algorithmik verwenden, zeigen, dass die gemeinsame Definition sie nicht erfüllt, und liefern eine (tatsächlich) praktikable Definition.


  1. Eine allgemeine Definition der O-Notation für die Algorithmusanalyse von K. Rutanen et al. (2015)
Raphael
quelle
5
Ich möchte nur darauf hinweisen, dass, obwohl wie und Ω wie wirkt , es Unterschiede gibt; Es ist nicht schwer, die Funktionen g und f so zu finden, dass f O ( g ) und f Ω ( g ) . OΩgffO(g)fΩ(g)
Zach Langley
1
+1 für die Erwähnung der Funktionsklassen. Dinge wie und Ω ( 2 n ) erscheinen überall in Zeitungen und Büchern, was für Menschen, die sich zum ersten Mal mit diesen Notationen auseinandersetzen, verwirrend sein kann. o(1)Ω(2n)
Janoma
7
@ ZachLangley Was Sie sagen, ist sehr wahr. Es gibt hier keine Gesamtbestellung. Es ist wahrscheinlich gefährlich, überhaupt aufzuziehen , aber ich denke, es dient dem Zweck der Intuitionsbildung.
Raphael
42

Big O: Obergrenze

"Big O" ( ) ist bei weitem das häufigste. Wenn Sie die Komplexität eines Algorithmus analysieren, müssen Sie in den meisten Fällen eine Obergrenze dafür festlegen, wie schnell die Laufzeit¹ ansteigt, wenn die Größe der Eingabe zunimmt. Grundsätzlich möchten wir wissen, dass das Ausführen des Algorithmus nicht zu lange dauern wird. Wir können dies nicht in tatsächlichen Zeiteinheiten (Sekunden) ausdrücken, da dies von der genauen Implementierung abhängen würde (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, dh wie lange es dauert, den Algorithmus auszuführen, wenn wir größere Eingaben vornehmen. Und es ist uns vor allem wichtig, wenn wir sicher sein können, dass das Programm fertig ist, und wir normalerweise wissen möchten, dass es so oder so viel Zeit oder weniger in Anspruch nimmt.O

Zu sagen, dass ein Algorithmus eine Laufzeit von für eine Eingabegröße n hat, bedeutet, dass eine Konstante K existiert, so dass der Algorithmus in höchstens K abgeschlossen istO(f(n))nK Schritte, dh die Laufzeit des Algorithmus wächst höchstens so schnell wie f (bis zu einem Skalierungsfaktor). Die Angabe von T ( n ) als Laufzeit des Algorithmus für die Eingangsgröße n , O ( n ) bedeutet informell, dass T ( n ) f ( n ) bis zu einem gewissen Skalierungsfaktor ist.Kf(n)fT(n)nO(n)T(n)f(n)

Untergrenze

Manchmal ist es nützlich, mehr Informationen als eine Obergrenze zu haben. ist die Umkehrung von O : Sie drückt aus, dass eine Funktion mindestens so schnell wächst wie eine andere. T ( n ) = Ω ( g ( n )ΩOT(n)=Ω(g(n))T(N)Kg(n)KT(n)g(n)

ΘOΩT(n)=Θ(h(n))Kh(n)T(n)Kh(n)KKT(n)h(n)

Weitere Überlegungen

oωoOOoω

Ich war in der obigen Diskussion etwas informell. Wikipedia hat formelle Definitionen und einen mathematischeren Ansatz.

T(n)=O(f(n))O(f(n))nTO(f)

Beispiel: Einige Sortieralgorithmen

nO(n2)O(n2)knkn(n1)/2n(n1)/2n2Θ(n2)

O(n2)O(nlg(n))nlg(n)Θ(nlg(n))

O(n2)Θ(n2)Ω(n)Θ(nlg(n))

xyx>yΩ(n)nn1Ω(nlg(n))KnKnlg(n)n!n!Θ(lg(n!))=Θ(nlg(n))Ω(nlg(n))

¹ Oder anderer Ressourcenverbrauch wie Speicherplatz. In dieser Antwort berücksichtige ich nur die Laufzeit.

Gilles
quelle
1
"Der beste Fall von Quicksort (wenn die Eingabe bereits sortiert ist) ist jedoch linear" dies ist der schlechteste Fall !!
user5507
@ user5507: Eigentlich kommt es auf die Pivot-Strategie an. Wenn das erste (oder letzte) Element als Drehpunkt ausgewählt ist, haben Sie Recht. Wenn Sie jedoch das mittlere Element oder den Median von erstem, mittlerem und letztem auswählen, ist die sortierte Eingabe der beste Fall.
Chirlu
"Das kleine o und ω werden in der Komplexitätsanalyse weitaus seltener verwendet." Dies gilt nicht für die Raumkomplexitätsanalyse. In der Zeitkomplexitätsanalyse verwenden Sie normalerweise o und ω, wenn Sie bestimmte Vorgänge zählen (Vergleiche, Festplattensuchen, Cache-Fehler, was haben Sie?). Aber da Sie immer warten und einen schnelleren Computer kaufen können, ist "Wandzeit" immer "bis zu einem konstanten Faktor", so dass Big-O weitaus häufiger vorkommt. In der Raumanalyse gibt es aufgrund der Informationstheorie oft harte Untergrenzen. Daher wird die Größe häufig als "f (n) + o (f (n)) Bits" angegeben, wobei f (n) die Untergrenze ist.
Pseudonym
Während ich daran denke: Wenn f (n) eine theoretische Untergrenze für die Größe einer Datenstruktur ist, wird eine, die f (n) + O (1) (konstanten Overhead) verwendet, als "implizit" bezeichnet, eine, die verwendet f (n) + O (f (n)) (konstanter relativer Overhead) wird "kompakt" genannt, und einer, der f (n) + o (f (n)) verwendet (relativer Overhead wird schließlich unbedeutend), wird "knapp" genannt ". Gute Bedingungen, um zu wissen, ob Sie jemals in diesem Bereich arbeiten müssen.
Pseudonym
17

OΩΘΘ

Kaveh
quelle
3
"Typisch"? Sie können für etwas anderes verwendet werden?
Svick
1
P=DTime(nO(1))f=O(g)f
4
P=DTime(nO(1))P=DTime(nΘ(1))
@JeffE, ich betrachte es als eine Gleichheit zwischen Mengen von Funktionen, aber Sie haben Recht, man kann es auch als eine Obergrenze in einem allgemeineren Sinne betrachten.
Kaveh
PDTIME(nΘ(1))DTIME(Θ(nlogn))PDTIME(Θ(nlogn))DTIME(nΘ(1))=