Cadeia infinita de grande

Primeiro, deixe-me escrever a definição de grande apenas para tornar as coisas explícitas. $O$

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

Digamos que temos um número finito de funções: satisftying: $f_1,f_2,\dots f_n$

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

Pela transitividade de , temos o seguinte: $O$ $O(f_1)\subseteq O(f_n)$

Isso vale se tivermos uma cadeia infinita de ? Em outras palavras, ? $O's$ $O(f_1) \subseteq O(f_\infty)$

Estou tendo problemas para imaginar o que está acontecendo.

asymptotics landau-notation saadtaame
fonte

Respostas:

Primeiro precisamos esclarecer o que queremos dizer com "isso vale se tivermos uma cadeia infinita?". Nós a interpretamos como uma sequência infinita de funções tal forma que, para todos os , temos . Essa sequência pode não ter uma última função. $\{f_i:\mathbb{N}\to\mathbb{N} \mid 1\leq i\}$ $i$ $f_i(n) = O(f_{i+1}(n))$

Podemos observar o limite das funções na sequência, ou seja, . No entanto, é possível que o limite não exista. E mesmo que exista, talvez não tenhamos . Por exemplo, considere a sequência de funções . Para cada , e, portanto, . No entanto, portanto, . $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))$

Por outro lado, podemos observar o limite da sequência das classes que não precisa ser igual à classe do limite das funções . Temos , portanto e para todos os . O limite superior contém todos os elementos (funções neste caso) que ocorrem infinitamente com freqüência e o limite inferior contém todos os elementos que ocorrem em todos para alguns $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$ (que pode depender do elemento). Como a sequência de classes é monotonicamente crescente, ambas existem e são iguais. Isso justifica o uso de . $\lim$

frafl
fonte

Existem duas séries: uma de funções (que pode convergir ou não) e uma de conjuntos (onde cada conjunto é um superconjunto do anterior; é por isso que essa série converge - veja a definição de lim inf e lim sup para conjuntos) . A primeira parte responde à pergunta sem a parte , a segunda parte responde a parte negativamente (se for algum tipo de limão).

f_{\infty}

$f_\infty$

f_{\infty}

$f_\infty$

f_{\infty}

$f_\infty$

frafl

E se o número de termos for incontável? :)

SamM 5/13

Usando algumas instruções bem-ordenadas ou você deseja substituir a série por algo mais contínuo? :)

frafl

@ Kaveh Muito obrigado, faz muito sentido agora. Se você pudesse justificar o uso de limites e o que essa coisa de lim significa, então isso completará meu entendimento.

Saadtaame

@ saadtaame: Talvez seja porque a pergunta acima ainda não pergunta o que você quer saber? Se bem me lembro, você adicionou por causa de um comentário sugerido. Se você fornecer algum contexto, talvez alguém possa reformular a pergunta novamente.

f_{\infty}

$f_\infty$

frafl

Sim, é possível ter uma cadeia infinita.

Tenho certeza de que você já conhece alguns exemplos: Você tem uma cadeia infinita aqui: polinômios de grau crescente. Você pode ir mais longe? Certo! Um exponencial cresce mais rápido (assintoticamente falando) do que qualquer polinômio. E, é claro, você pode continuar:

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$

Você também pode construir uma cadeia infinita na outra direção. Se então (aderindo a funções positivas, pois aqui discutimos as assintóticas das funções de complexidade). Então, temos por exemplo: $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)$

De fato, dada qualquer cadeia de funções , você pode criar uma função que cresça mais rapidamente do que todas elas. (Suponho que são funções de a .) Primeiro, comece com a idéia . Isso pode não funcionar porque o conjunto pode ser ilimitado. Mas, como estamos interessados apenas em crescimento assintótico, basta começar pequeno e crescer progressivamente. Leve o máximo a um número finito de funções. $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$}$ Em seguida, para qualquer , , pois . Se você deseja uma função que cresça estritamente mais rápida ( ), .

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- parar de ser mau'
fonte

Todas essas respostas (a sua e a outra) se baseiam no pressuposto de que sabemos o que acontece no infinito, eles não são satisfatórios para mim, não sei sobre o OP (por que não devemos ter um grupo fechado com tamanho infinito) ?)

@SaeedAmiri Sinto muito, não entendo o seu comentário: o que você quer dizer com “sabemos o que acontece no infinito, eles não são satisfatórios para mim”?

Gilles 'SO- stop be evil'