Verschachtelte große O-Notation

8

Angenommen, ich habe ein Diagrammmit Kanten. Ich möchte BFS auf ausführen, das eine Laufzeit von . $|G|$ $|E|=O(V^2)$ $G$ $O(V+E)$

Es fühlt sich natürlich an zu schreiben, dass die Laufzeit in diesem Diagramm und dann zu vereinfacht wird . $O(O(V^2)+V)$ $O(V^2)$

Gibt es Fallstricke bei der Verwendung einer solchen Verknüpfung zum Entfernen des verschachtelten O (nicht nur in diesem Fall, sondern allgemeiner)?

terminology asymptotics landau-notation Die Unfun Cat
quelle

4

Wenn Sie die Definition von Big-O durcharbeiten, werden Sie feststellen, dass verschachtelte Os sowohl natürlich als auch redundant sind und dass die Regel zum Löschen des inneren O korrekt ist.

Dave Clarke

Da V in O (V ^ 2) ist, könnten Sie O (V ^ 2) durch V ersetzen, wenn Sie nicht wüssten, was Sie tun?

Die Unfun Cat

3

Wenn Sie nicht wissen, was Sie tun, können Sie willkürlich falsche Dinge tun.

Dave Clarke

4

Tatsächlich. = ist nicht = im Big-O-Land.

Dave Clarke

3

Siehe auch diese ausgezeichnete Frage zu math.SE about = in Landau-Notation.

Raphael

14

Lassen Sie mich mit einer Empfehlung beginnen: Behandeln Sie die Landau-Notation so, wie Sie die Rundung behandeln sollten: Runde selten, Runde spät. Wenn Sie etwas genaueres als Wissen , verwenden Sie es, bis Sie mit allen Berechnungen fertig sind, und Landauify am Ende. $O(.)$

Lassen Sie uns diesen Missbrauch der Notation durchgehen¹. Wie würden wir so etwas wie interpretieren ? Wir sollten durch seine Definition von innen nach außen ersetzen . Also bekommen wir $h \in O(f + O(g))$ $O$

$\qquad \displaystyle \exists g' \in O(g).\, h \in O(f + g')$

und dann

$\qquad \displaystyle \exists g' \in O(g).\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + g'(n))$

das ist äquivalent zu

$\qquad \displaystyle \exists c > 0.\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + cg(n))$ .

Als sicher² wir, dass dies äquivalent zu ; Der Genauigkeitsverlust wird von ohnehin ignoriert . $d(f(n) + cg(n)) \leq cd(f(n) + g(n))$ $h \in O(f + g)$ $O$

Was ist mit anderen Kombinationen, sagen wir ? Wenn wir hier dasselbe versuchen, bekommen wir $h \in O(f + \Omega(g))$

$\qquad \displaystyle \exists g' \in \Omega(g).\, h \in O(f + g')$ .

Aber das ist eine Tautologie: ist sicherlich oben durch etwas willkürlich Großes begrenzt. Daher ist es nicht sinnvoll, Ober- und Untergrenzen auf diese Weise zu kombinieren. $h$

$O(.)$ Und die anderen Landau-Symbole ordnen Funktionen Funktionsklassen zu. Das Füttern einer Funktionsklasse ist nicht sofort sinnvoll.
Zumindest wenn wir nur positive Funktionen berücksichtigen, die wir sicher annehmen können, wenn wir über Laufzeiten sprechen. Ich bin mir nicht sicher, ob das im Allgemeinen funktioniert.

Raphael
quelle

2

Ich wollte dies nur hinzufügen, weil ich es kürzlich angetroffen habe. Während diese Verknüpfung mit Addition und Multiplikation in Ordnung ist (wenn mit gemischt wird ; siehe die akzeptierte Antwort), muss bei der Verwendung von Exponenten vorsichtig vorgegangen werden. Zum Beispiel: In diesem Beispiel gehört zur ersten Klasse, aber nicht zur zweiten. $O$ $\Omega$

O (n^{O (m)}) \neq O (n^{m}) .

$O(n^{O(m)}) \not= O(n^m).$

n^{2 m}

$n^{2m}$

Jadhachem
quelle

1

Per Definition ist eine Menge, und wenn Sie diese verschachtelte Notation verwenden, hätten Sie eine Menge in einer Menge, was falsch wäre. $O(g)$

Die Definition der O-Notation

Der Fehler

Sie haben Begriffe wie wobei k und n Funktionen sind und eine Menge ist. Aber was ist das Ergebnis einer Funktion, die einer Menge hinzugefügt wurde? Es ist nicht definiert! $O(O(n)+k)$ $O(n)$

Korrekte Version

Anstatt die verschachtelten Landau-Symbole zu verwenden, können Sie Folgendes tun: $O(m+k),m \in O(n)$

Odin
quelle

2

Ja, aber die Landau-Notation wird häufig aus Gründen der (angeblichen) Benutzerfreundlichkeit missbraucht. Deshalb sollten wir besser sicherstellen, dass alle das Gleiche verstehen. Siehe hier für eine strukturierte Vorgehensweise.

Raphael

0

In Abschnitt 9.3 " Manipulation" das Buch Concrete Mathematics (Second Edition), Knuth einige aufführt Regeln der Manipulation auf dem -Notation (Im Folgenden gehe ich davon aus, dass sowohl und ist positiv; Beachten Sie, dass die Reihenfolge der Regeln geändert wurde. $O$ $O$ $f(n)$ $g(n)$

\begin{matrix} (1) . n^{m} = O (n^{m^{'}}), m \leq m^{'} \\ (3) . f (n) = O (f (n)) \\ (5) . O (O (f (n))) = O (f (n)) \\ (4) . c \cdot O (f (n)) = O (f (n)) \\ (2) . O (f (n)) + O (g (n)) = O (f (n) + g (n)) \\ (6) . O (f (n)) O (g (n)) = O (f (n) g (n)) = f (n) O (g (n)) \end{matrix}

$\begin{gather} (1). \quad n^m = O(n^{m'}), \quad m \le m' \\ (3). \quad f(n) = O(f(n)) \\ (5). \quad O(O(f(n))) = O(f(n)) \\ (4). \quad c \cdot O(f(n)) = O(f(n)) \\ (2). \quad O(f(n)) + O(g(n)) = O(f(n) + g(n)) \\ (6). \quad O(f(n)) O(g(n)) = O(f(n) g(n)) = f(n) O(g(n))\\ \end{gather}$

Mit (3) können Sie eine Funktion mit einer O-Notation umbrechen / entpacken . Dann können Sie mit (5) tatsächlich beliebig endliche Zeiten ein- und auspacken (oder aufrufen, verschachteln ). Mit (4) können Sie auch konstante Multiplikationsfaktoren zu / von hinzufügen / entfernen . $f(n)$ $O$

Mit (2) und (6) können Sie dann verschachtelte Notationen so bearbeiten, dass sie mit und kompatibel sind . $O$ $+$ $\times$

Hengxin
quelle

Verschachtelte große O-Notation

Antworten:

Die Definition der O-Notation

Der Fehler

Korrekte Version