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

In den meisten einführenden Algorithmusklassen werden Notationen wie (Big O) und $O$$\Theta$ 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$$\Omega$$\omega$

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 < .$f \in \cal{O}(g)$$f$$g$$\leq$$f \in o(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 \in \Omega(g)$$f$$g$$\omega$$f \in \Omega(g)$$g \in \cal{O}(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 \in \Theta(g)$$f$$g$$f \in \cal{O}(g) \cap \Omega(g)$$f \sim g$$\Theta$$\cal{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.$\cal{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:

• Was sind die Regeln für Gleichheitszeichen mit Big-O und Little-O?
• Sortierfunktionen nach asymptotischem Wachstum
• Wie verhalten sich O und Ω zum schlechtesten und besten Fall?
• Geschachtelte Big O-Notation
• Definition von für negative Funktionen$\Theta$
• Was bedeutet ? $O(m+n)$
  Wird O (mn) als "lineares" oder "quadratisches" Wachstum betrachtet?
• Summen von Landau-Begriffen überarbeitet
• Was bedeutet Big O als Begriff für ein Näherungsverhältnis?
• Jede andere Frage zu Asymptotik und Landau-Notation als Übung.

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)

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 $O(f(n))$$n$$K$ 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.$K \, f(n)$$f$$T(n)$$n$$O(n)$$T(n) \le 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 $\Omega$$O$$T(n) = \Omega(g(n))$$T(N) \ge K' g(n)$$K'$$T(n) \ge g(n)$

$\Theta$$O$$\Omega$$T(n) = \Theta(h(n))$$K h(n) \ge T(n) \ge K' h(n)$$K$$K'$$T(n) \approx h(n)$

Weitere Überlegungen

$o$$\omega$$o$$O$$O$$o$$\omega$

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

$T(n) = O(f(n))$$O(f(n))$$n$$T \in O(f)$

Beispiel: Einige Sortieralgorithmen

$n$$O(n^2)$$O(n^2)$$k$$n-k$$n(n-1)/2$$n(n-1)/2$$n^2$$\Theta(n^2)$

$O(n^2)$$O(n \: \mathrm{lg}(n))$$n \: \mathrm{lg}(n)$$\Theta(n \: \mathrm{lg}(n))$

$O(n^2)$$\Theta(n^2)$$\Omega(n)$$\Theta(n \: \mathrm{lg}(n))$

$x \le y$$x > y$$\Omega(n)$$n$$n-1$$\Omega(n \: \mathrm{lg}(n))$$K$$n$$K n \mathrm{lg}(n)$$n!$$n!$$\Theta(\mathrm{lg}(n!)) = \Theta(n\:\mathrm{lg}(n))$$\Omega(n \: \mathrm{lg}(n))$

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

$O$$\Omega$$\Theta$$\Theta$