Was bedeutet Tilde in Big-O-Notation?

Ich lese eine Zeitung und in ihrer Beschreibung der Zeitkomplexität heißt es, dass die Zeitkomplexität . $\tilde{O}(2^{2n})$

Ich habe im Internet und in Wikipedia gesucht, aber ich kann nicht finden, was diese Tilde in der Big-O / Landau-Notation bedeutet. In der Zeitung selbst habe ich auch keine Ahnung davon gefunden. Was bedeutet ? $\tilde{O}(\cdot)$

landau-notation Johannes Schaub - litb
quelle

"Ich habe im Internet gesucht" Wie?!? :-) Normalerweise ist meine erste Reaktion bei Fragen wie diesen, dass Google Ihnen die Antwort sofort mitteilt. Aber für diesen habe ich keine Ahnung, welchen Suchbegriff ich verwenden würde!

David Richerby

Ich suchte nach "landau symbole tilde", aber es zeigte sich nichts schlüssiges. Ich denke, Google braucht eine KI, die weiß, wie eine Tilde visuell aussieht, und sucht danach in gerenderten TeX-Bildern: p

Johannes Schaub - litb

Ein anderer, den Sie manchmal sehen, ist Big Oh Star, das heißt, . Es wird häufig mit exakten exponentiellen Zeitalgorithmen verwendet, und die Notation unterdrückt Faktoren, die in der Eingabegröße polynomiell begrenzt sind.

O^{*}

$O^*$

Juho

Es ist eine Variante des Big-O, die logarithmische Faktoren „ignoriert“:

f (n) \in \tilde{O} (h (n))

$f(n) \in \tilde O(h(n))$

ist äquivalent zu:

\exists k : f (n) \in O (h (n) \log^{k} (h (n)))

$\exists k : f(n) \in O \!\left( h(n)\log^k(h(n)) \right)$

Aus Wikipedia :

Im Wesentlichen handelt es sich um eine Big- Notation, bei der logarithmische Faktoren ignoriert werden, da die Wachstumsrateneffekte einiger anderer superlogarithmischer Funktionen auf eine Wachstumsratenexplosion für große Eingabeparameter hinweisen, die für die Vorhersage einer schlechten Laufzeitleistung wichtiger ist als die Feinpunkteffekte, die durch den logarithmischen Wachstumsfaktor (die logarithmischen Wachstumsfaktoren) verursacht werden. Diese Notation wird oft verwendet, um das "Nitpicking" innerhalb von Wachstumsraten zu vermeiden, die für die vorliegenden Angelegenheiten als zu eng begrenzt angegeben werden (da für jede Konstante und jedes immer ). $O$ $\log^k n$ $o(n^\varepsilon)$ $k$ $\varepsilon > 0$

Manlio
quelle

Bin ich zu Recht zu dem Schluss gekommen, dass

und

unterschiedlich sind? Dies ist verwirrend, da sie austauschbar zu sein scheinen.

O (2^{2 n} + o (n))

$O(2^{2n} + o(n))$

\tilde{O} (2^{2 n})

$\tilde{O}(2^{2n})$

Johannes Schaub - litb

@ JohannesSchaub-litb Ja, es gibt Funktionen, die für jedes

mehr als

und dennoch weniger als

wachsen und daher in der ersten, aber nicht in der zweiten enthalten sind. Wie auch immer: Der Sinn dieser Notation besteht darin, nur den wichtigen Teil der asymptotischen Komplexität zu zeigen, und im Allgemeinen wird

nicht als wichtig angesehen.

\log^{k} n

$\log^k n$

k

$k$

n

$n$

o (n)

$o(n)$

Bakuriu

Folglich ist

dasselbe wie

. @ JohannesSchaub-litb

ist dasselbe wie

. Falls Sie tatsächlich

gemeint haben , ist dies

\tilde{O} (2^{2 n})

$\tilde O(2^{2n})$

O (2^{2 n} p o l y (n))

$O(2^{2n}\mathrm{poly}(n))$

O (2^{2 n} + o (n))

$O(2^{2n}+o(n))$

O (2^{2 n})

$O(2^{2n})$

O (2^{2 n + o (n)})

$O(2^{2n+o(n)})$ enthält

, aber auch einige Funktionen, die etwas schneller wachsen. Menschen verwenden es oft anstelle von

weil es nicht falsch ist,

eine weniger bekannte Notation ist und der Verlust an Präzision oft keine Rolle spielt.

\tilde{O} (2^{2 n})

$\tilde O(2^{2n})$

\tilde{O} (2^{2 n})

$\tilde O(2^{2n})$

\tilde{O}

$\tilde O$

Emil Jeřábek 3.0

Ah, ich verstehe jetzt, danke. Das macht sehr viel Sinn

Johannes Schaub - litb

Was bedeutet Tilde in Big-O-Notation?

Antworten: