7 votos

Cómo es$O(\log(\log(n)))$$O( \log n)$?

Cómo es$O(\log(\log(n)))$$O( \log n)$?

He visto este resultado en algún lugar de esto, pero yo todavía no entiendo muy bien cómo esto es cierto. Esto también me ayudan a calcular los Grandes de Omega de la misma función.

5voto

NP-hard Puntos 1872

Supongamos $f(n) = O(\log\log n)$, y queremos demostrar que $f(n) = O(\log n)$.

Suponga $f(n)$ es una función positiva. Por la definición de la gran $O$ notación, $f(n) = O(\log\log n)$ implica que existe un $N_0$ y una constante positiva $k$ tal que $$ f(n) \leq k\cdot \log\log n, \ \forall n \geq N_0 $$

Desde $\log\log n \leq \log n$ para suficientemente grande $n$, debe existir una $N_1$ tal que $$ f(n) \leq k \cdot \log n, \ \forall n \geq N_1 $$ por lo tanto $f(n) = O(\log n)$.

3voto

Bernard Puntos 34415

Esto es debido a que ,si $n$ es lo suficientemente grande, $\lvert f\rvert\le K\log(\log n)$ para algunas constantes $K$ $\log x \le x$ todos los $x$.

Más generalmente, si $f=O(g)$ $g=O(h)$ $f=O(h)\,$ $\,(O(O(h))=O(h)$).

2voto

kodlu Puntos 1178

En primer lugar, asumimos que todas las funciones son no negativos. $f(n)$ $O(g(n))$ si $$\lim_{n\rightarrow \infty} \sup \frac{f(n)}{g(n)} \leq K<\infty\quad(1)$$ where the finite constant $K$ is independent of $n.$ Thus if $f(n)=O(g(n))$ and $h(n)\leq f(n)$ for $n$ large enough, then $h(n)=O(g(n)).$

Si $K=0$, entonces decimos que $f(n)=o(g(n))$, pero todavía mantiene ese $f(n)=O(g(n)).$

Si $f(n)=O(g(n))$ $g(n)=O(f(n))$ $f(n)=\Theta(g(n))$ es decir, son el mismo orden hasta finita y constante, para $n$ lo suficientemente grande.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X