Variationen von Omega und Omega unendlich

7

Einige Autoren definieren auf eine etwas andere Weise: Verwenden für diese alternative Definition (lesen Sie „Omega Infinity“). Wir sagen, dass wenn es eine positive Konstante so dass für unendlich viele ganze Zahlen , während das übliche erfordert, dass dies für alle ganzen Zahlen gilt, die größer als ein bestimmtes . $\Omega$ $\overset{\infty}{\Omega}$ $f(n) = \overset{\infty}{\Omega}(g(n))$ $c$ $f(n) \geq c\cdot g(n) \geq 0$ $n$ $\Omega$ $n_0$

Zeigen Sie, dass für zwei beliebige Funktionen und , die asymptotisch nicht negativ sind, entweder oder oder beides, während dies nicht zutrifft, wenn wir anstelle von . $f(n)$ $g(n)$ $f(n) = O(g(n))$ $f(n)= \overset{\infty}{\Omega}(g(n))$ $\Omega$ $\overset{\infty}{\Omega}$

Ich versuche Algorithmen zu lernen. Aber ich kann das nicht beweisen. Können mir die Experten helfen?

asymptotics landau-notation gopal
quelle

Versuchen Sie, die Definitionen zu verwenden, und denken Sie daran, dass für jede Eigenschaft entweder für unendlich viele ganze Zahlen gilt oder nicht für fast alle ganzen Zahlen. Beachten Sie, dass die Negation von .

P

$P$

P

$P$

P

$P$

Ω^{\infty}

$\Omega^\infty$

O

$O$

Shaull

Sehen Sie hier oder hier .

Raphael

5

Hinweis: Wenn und asymptotisch nicht negativ ist , dann für alle positiven Konstanten , für groß genug . Dies folgt, indem die Bedingung ignoriert und die Definition von negiert wird . Tatsächlich erhalten Sie auf diese Weise das stärkere Ergebnis, dass entweder oder (aber nicht beide). $f(n) \notin \overset{\infty}{\Omega}(g(n))$ $g(n)$ $c$ $f(n) \leq c \cdot g(n)$ $n$ $c \cdot g(n) \geq 0$ $f(n) \in \overset{\infty}{\Omega}(g(n))$ $f(n) \in \overset{\infty}{\Omega}(g(n))$ $f(n) \in o(g(n))$

Weiterer Hinweis: Sie können damit beginnen, dass die Negation von " für unendlich viele " " für groß genug " ist. $P(n)$ $n$ $\lnot P(n)$ $n$

Yuval Filmus
quelle

Ich kann den Unterschied von unendlich vielen & für groß genug n nicht verstehen . Kennst du eine Quelle, die mir helfen kann?

Fatemeh Karimi

2

Ich schlage eine gute Grundlage in der Mengenlehre und der formalen Logik vor. Etwas gilt für alle groß genug , um , wenn es vorhanden , so dass es für alle hält . Es gilt für unendlich viele wenn die Menge von für die es gilt, unendlich ist.

n

$n$

n_{0}

$n_0$

n \geq n_{0}

$n\geq n_0$

n

$n$

n

$n$

Yuval Filmus

0

Ich kann Ihnen ein Beispiel geben, damit Sie besser verstehen können . Stellen Sie sich einen Binomialhaufen vor. Die Einfügeoperation ist , aber ist es ? $\overset{\infty}{\Omega}(g(n))$ $O(logN)$ ${\Omega}(logN)$

In Fällen, in denen wir Baumränge von 4-3-2-1-0 haben und einen Baum mit Rang 0 einfügen, ist dies eine . Das Einfügen eines Baums mit Rang 0 in den resultierenden Heap aus der vorherigen Operation (Heap mit einem Baumrang von 5) ist jedoch eine -Operation, da nur Zeiger hinzugefügt werden sollten und keine zusätzliche Zusammenführungsarbeit erforderlich ist. ${\Omega}(logN)$ $O(1)$

Dies ist der wesentliche Unterschied zwischen und . Zum Beispiel ist die Binomial-Heap-Einfügeoperation für die Menge von . Es heißt nicht, dass bei die Komplexität , sondern für eine unendliche Menge von n, aber nicht für alle ${\Omega}$ $\overset{\infty}{\Omega}$ $\overset{\infty}{\Omega}(logN)$ $n = \{{1,3,7,...,2^k - 1}\}$ $n \geq n_0$ ${\Omega}(logN)$ $n \geq n_0$

denis631
quelle

@ YuvalFilmus bitte korrigieren Sie mich Wenn ich falsch

liege

Variationen von Omega und Omega unendlich

Antworten: