Unendliche Kette von großen

Lassen Sie mich zunächst die Definition von Big schreiben , um die Dinge deutlich zu machen. $O$

$f(n)\in O(g(n))\iff \exists c, n_0\gt 0$ so dass $0\le f(n)\le cg(n), \forall n\ge n_0$

Lassen Sie uns sagen , dass wir eine endliche Anzahl von Funktionen: satisftying: $f_1,f_2,\dots f_n$

$O(f_1)\subseteq O(f_2)\dots \subseteq O(f_n)$

Durch die Transitivität von $O$ haben wir das: $O(f_1)\subseteq O(f_n)$

Gilt das, wenn wir eine unendliche Kette von $O's$ ? Mit anderen Worten, ist $O(f_1) \subseteq O(f_\infty)$ ?

Ich habe Probleme, mir vorzustellen, was los ist.

asymptotics landau-notation Saadtaame
quelle

Antworten:

Wir müssen zunächst klären, was wir unter "Gilt das, wenn wir eine unendliche Kette haben?" Wir interpretieren es als eine unendliche Folge von Funktionen so dass wir für alle . Eine solche Sequenz hat möglicherweise keine letzte Funktion. $\{f_i:\mathbb{N}\to\mathbb{N} \mid 1\leq i\}$ $i$ $f_i(n) = O(f_{i+1}(n))$

Wir können die Grenze der Funktionen in der Folge betrachten, dh . Es ist jedoch möglich, dass das Limit nicht existiert. Und selbst in dem Fall, dass es existiert, haben wir möglicherweise nicht . Betrachten Sie zum Beispiel die Folge von Funktionen . Für jedes ist und daher . Jedoch so . $f_\infty(n) = \lim_{i\to \infty} f_i(n)$ $f_1(n) = O(f_\infty(n))$ $f_i(n) = \frac{n}{i}$ $i$ $f_i(n)=\Theta(n)$ $f_i(n) = O(f_{i+1}(n))$ $f_\infty(n)=\lim_{i\to\infty}f_i(n)=0=\Theta(1)$ $f_1(n) \neq O(f_\infty(n))$

Auf der anderen Seite können wir die Grenze der Reihenfolge der Klassen betrachten, die nicht gleich der Klasse der Grenze der Funktionen sein muss . Wir haben , also und für alle . Der limit superior enthält alle Elemente (in diesem Fall Funktionen), die unendlich oft vorkommen, und der limit inferior enthält alle Elemente, die in all für einige vorkommen $f_i \in \mathcal O(f_{i+1})$ $\mathcal O(f_i) \subseteq \mathcal O(f_{i+1})$ $f_j \in \lim_{i\rightarrow\infty} \mathcal O(f_i) = \limsup_{i\rightarrow\infty} \mathcal O(f_i) = \liminf_{i\rightarrow\infty} \mathcal O(f_i) = \bigcup_{n \in \mathbb{N}}\bigcap_{k>n}\mathcal O(f_k)$ $j$ $\mathcal O(f_i), i \ge n_0$ $n_0$ (was vom Element abhängen kann). Da die Reihenfolge der Klassen monoton zunimmt, existieren beide und sie sind gleich. Dies rechtfertigt die Verwendung von . $\lim$

frafl
quelle

Es gibt zwei Reihen: eine von Funktionen (die konvergieren können oder nicht) und eine von Mengen (wobei jede Menge eine übergeordnete Menge der vorhergehenden ist; deshalb konvergiert diese Reihe - siehe Definition von lim inf und lim sup für Mengen). . Der erste Teil beantwortet die Frage ohne den Teil , der zweite Teil beantwortet den Teil negativ (wenn eine Art Limes ist).

f_{\infty}

$f_\infty$

f_{\infty}

$f_\infty$

f_{\infty}

$f_\infty$

Freitag,

Was ist, wenn die Anzahl der Begriffe unzählig ist? :)

SamM

Mit etwas Ordnung oder möchten Sie die Serie durch etwas Kontinuierlicheres ersetzen? :)

Freitag

@Kaveh Vielen Dank, es macht jetzt sehr viel Sinn. Wenn Sie die Verwendung von Grenzen rechtfertigen könnten und die Bedeutung dieser Grenze, dann würde dies mein Verständnis vervollständigen.

Saadtaame

@saadtaame: Vielleicht liegt das daran, dass die obige Frage noch nicht fragt, was du wissen willst? Wenn ich mich richtig erinnere, haben Sie das hinzugefügt, weil ein Kommentar es vorgeschlagen hat. Wenn Sie einen Kontext angeben, könnte möglicherweise jemand die Frage erneut formulieren.

f_{\infty}

$f_\infty$

Freitag,

Ja, es ist möglich, eine unendliche Kette zu haben.

Ich bin sicher, Sie kennen bereits einige Beispiele: Hier haben Sie eine unendliche Kette: Polynome wachsenden Grades. Kannst du noch weiter gehen? Sicher! Ein Exponential wächst asymptotisch schneller als jedes Polynom. Und natürlich kannst du weitermachen:

O (x) \subseteq O (x^{2}) \subseteq \dots \subseteq O (x^{42}) \subseteq \dots

$O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O(x^{42}) \subseteq \ldots$

O (x) \subseteq O (x^{2}) \subseteq \dots \subseteq O (x^{42}) \subseteq \dots O (e^{x})

$O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O(x^{42}) \subseteq \ldots O(e^x)$

O (e^{x}) \subseteq O (x e^{x}) \subseteq O (e^{2 x}) \subseteq O (e^{e^{x}}) \subseteq \dots

$O(\mathrm{e}^x) \subseteq O(x\,\mathrm{e}^x) \subseteq O(\mathrm{e}^{2x}) \subseteq O(\mathrm{e}^{\mathrm{e}^x}) \subseteq \ldots$

Sie können eine unendliche Kette auch in die andere Richtung bauen. Wenn dann (bei positiven Funktionen bleiben, da wir hier die Asymptotik von Komplexitätsfunktionen diskutieren). So haben wir zum Beispiel: $f = O(g)$ $\dfrac{1}{g} = O\left(\dfrac{1}{f}\right)$

O (x) \subseteq O (x^{2}) \subseteq \dots \subseteq O (\frac{e^{x}}{x^{2}}) \subseteq O (\frac{e^{x}}{x}) \subseteq O (e^{x})

$O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O\left(\dfrac{e^x}{x^2}\right) \subseteq O\left(\dfrac{e^x}{x}\right) \subseteq O(e^x)$

Sie eine beliebige Funktionskette angeben , können Sie eine Funktion erstellen , die schneller wächst als alle anderen. (Ich nehme an, die sind Funktionen von bis .) Beginnen Sie zunächst mit der Idee . Dies funktioniert möglicherweise nicht, da die Menge kann. Da wir jedoch nur an asymptotischem Wachstum interessiert sind, reicht es aus, klein anzufangen und progressiv zu wachsen. Nehmen Sie das Maximum über eine endliche Anzahl von Funktionen. $f_1, \ldots, f_n$ $f_\infty$ $f_i$ $\mathbb{N}$ $\mathbb{R}_+$ $f_\infty(x) = \max \{f_n(x) \mid n \in\mathbb{N}\}$ $\{f_n(x) \mid n \in\mathbb{N}\}$

f_{\infty} (x) = max {f_{n} (x) ∣ 1 \leq n \leq N} if N \leq x < N + 1

$f_\infty(x) = \max \{f_n(x) \mid 1 \le n \le N \} \qquad \text{if $N \le x \lt N+1$}$ Dann für jede , , da . Wenn Sie eine Funktion wünschen, die deutlich schneller wächst ( ), nehmen Sie .

N

$N$

f_{N} \in O (f_{\infty})

$f_N \in O(f_\infty)$

\forall x \geq N, f_{\infty} (x) \geq f_{N} (x)

$\forall x \ge N, f_\infty(x) \ge f_N(x)$

f_{\infty} = o (f_{\infty}^{'})

$f_\infty = o(f_\infty')$

f_{\infty}^{'} (x) = x \cdot (1 + f_{\infty} (x))

$f_\infty'(x) = x \cdot (1 + f_\infty(x))$

Gilles 'SO - hör auf böse zu sein'
quelle

Alle diese Antworten (Ihre und andere) basieren auf der Annahme, dass wir wissen, was im Unendlichen passiert, dass sie für mich nicht befriedigend sind, dass ich nichts über das OP weiß (warum wir keine geschlossene Gruppe mit unendlicher Größe haben sollten) ?)

@ SaeedAmiri Es tut mir leid, ich verstehe Ihren Kommentar nicht: Was meinst du mit "wir wissen, was im Unendlichen passiert, sie sind für mich nicht befriedigend"?

Gilles 'SO- hör auf böse zu sein'