Chaîne infinie de grands

Tout d'abord, permettez-moi d'écrire la définition du grand juste pour rendre les choses explicites. $O$

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

Disons que nous avons un nombre fini de fonctions: satisftying: $f_1,f_2,\dots f_n$

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

Par transitivité de , on a que: $O$ $O(f_1)\subseteq O(f_n)$

Cela vaut-il si nous avons une chaîne infinie de ? En d'autres termes, ? $O's$ $O(f_1) \subseteq O(f_\infty)$

J'ai du mal à imaginer ce qui se passe.

asymptotics landau-notation saadtaame
la source

Réponses:

Nous devons d'abord clarifier ce que nous entendons par "est-ce valable si nous avons une chaîne infinie?". Nous l'interprétons comme une séquence infinie de fonctions telles que pour tout nous avons . Une telle séquence pourrait ne pas avoir de dernière fonction. $\{f_i:\mathbb{N}\to\mathbb{N} \mid 1\leq i\}$ $i$ $f_i(n) = O(f_{i+1}(n))$

Nous pouvons regarder la limite des fonctions dans la séquence, c'est-à-dire . Cependant il est possible que la limite n'existe pas. Et même dans le cas où il existe, nous pourrions ne pas avoir . Par exemple, considérons la séquence de fonctions . Pour chaque , et donc . Cependant donc . $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))$

D'autre part, nous pouvons regarder la limite de la séquence des classes qui n'a pas besoin d'être égale à la classe de la limite des fonctions . Nous avons , donc et pour tout . La limite supérieure contient tous les éléments (fonctions dans ce cas) qui se produisent infiniment souvent et la limite inférieure contient tous les éléments qui se produisent dans tous les pour certains $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$ (qui peut dépendre de l'élément). Étant donné que la séquence des classes augmente de façon monotone, les deux existent et sont égales. Cela justifie l'utilisation de . $\lim$

frafl
la source

Il existe deux séries: une des fonctions (qui peuvent converger ou non) et une des ensembles (où chaque ensemble est un super ensemble de la précédente; c'est pourquoi cette série converge - voir la définition de lim inf et lim sup pour les ensembles) . La première partie répond à la question sans la partie , la seconde partie répond négativement à la partie (si est une sorte de limes).

f_{\infty}

$f_\infty$

f_{\infty}

$f_\infty$

f_{\infty}

$f_\infty$

frafl

Et si le nombre de termes est indénombrable? :)

SamM

En utilisant un bon ordre ou voulez-vous remplacer la série par quelque chose de plus continu? :)

frafl

@Kaveh Merci beaucoup, cela a beaucoup de sens maintenant. Si vous pouviez justifier l'utilisation des limites et ce que signifie cette chose lim inf, cela compléterait ma compréhension.

saadtaame

@saadtaame: C'est peut-être parce que la question ci-dessus ne demande toujours pas ce que vous voulez savoir? Si je me souviens bien, vous avez ajouté le cause d'un commentaire suggéré. Si vous fournissez un certain contexte, peut-être que quelqu'un pourrait reformuler la question à nouveau.

f_{\infty}

$f_\infty$

frafl

Oui, il est possible d'avoir une chaîne infinie.

Je suis sûr que vous connaissez déjà quelques exemples: Vous avez ici une chaîne infinie: polynômes de degré croissant. Peux-tu aller plus loin? Sûr! Une exponentielle croît plus rapidement (asymptotiquement) que n'importe quel polynôme. Et bien sûr, vous pouvez continuer:

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$

Vous pouvez également créer une chaîne infinie dans l'autre sens. Si alors (s'en tenir aux fonctions positives, car ici nous discutons l'asymptotique des fonctions de complexité). Nous avons donc par exemple: $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)$

En fait, étant donné n'importe quelle chaîne de fonctions , vous pouvez créer une fonction qui croît plus rapidement que toutes. (Je suppose que les sont des fonctions de à .) Commençons d'abord par l'idée . Cela peut ne pas fonctionner car l'ensemble peut être illimité. Mais comme nous ne sommes intéressés que par une croissance asymptotique, il suffit de commencer petit et de croître progressivement. Prenez le maximum sur un nombre fini de fonctions. $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$}$ Alors pour tout , , puisque . Si vous voulez une fonction qui croît strictement plus vite ( ), prenez .

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- arrête d'être méchant'
la source

Toutes ces réponses (la vôtre et l'autre) sont basées sur l'hypothèse que nous savons ce qui se passe à l'infini, elles ne sont pas satisfaisantes pour moi, je ne sais pas pour l'OP (pourquoi nous ne devrions pas avoir de groupe fermé de taille infinie) ?)

@SaeedAmiri Je suis désolé, je ne comprends pas votre commentaire: que voulez-vous dire par «nous savons ce qui se passe à l'infini, ils ne sont pas satisfaisants pour moi»?

Gilles 'SO- arrête d'être méchant'