son - Big-O pequeña aclaración
notación ω(n) (4)
El tiempo consumido por los algoritmos O (log n) depende solo linealmente del número de dígitos de n. Por eso es muy fácil escalarlo.
Digamos que quiere calcular F (100000000), el número 10 ^ 8th F .... ascci. Para un algoritmo O (log n) solo tomará 4 veces el tiempo consumido al calcular F (100).
Los términos O (log log n) pueden aparecer en una variedad de lugares diferentes, pero normalmente hay dos rutas principales que llegarán a este tiempo de ejecución. Enlace de referencia ingrese el código aquí here .
¿Es O(log(log(n))) realidad solo O(log(n)) cuando se trata de complejidad de tiempo?
¿Está de acuerdo en que esta función g() tiene una complejidad de tiempo de O(log(log(n))) ?
int f(int n) {
if (n <= 1)
return 0;
return f(n/2) + 1;
}
int g(int n) {
int m = f(f(n));
int i;
int x = 0;
for (i = 0; i < m; i++) {
x += i * i;
}
return m;
}
Parece que es log(n) + log(log n) + log(log n) .
En orden: la primera recursión de f() , más la segunda recursión de f() y el bucle for, por lo que la complejidad final es O (log n), porque los términos de orden inferior se ignoran.
la función f(n) calcula el logaritmo en la base 2 de n dividiendo repetidamente por 2 . Se itera log 2 (n) veces.
Si lo llama en su propio resultado, de hecho devolverá el registro 2 (registro 2 (n)) para un registro adicional 2 (registro 2 (n)) iteraciones. Hasta el momento, la complejidad es O (log (N)) + O (log (log (N)) . El primer término domina al segundo, la complejidad general es O (log (N)) .
El bucle final itera log 2 (log 2 (n)) veces, la complejidad del tiempo de esta última fase es O (log (log (N)) , insignificante frente a la fase inicial.
Tenga en cuenta que como x no se usa antes del final de la función g , no es necesario computarlo y el compilador puede optimizar este bucle a la nada.
La complejidad global del tiempo sale como O (log (N)) , que no es lo mismo que O (log (log (N))).
int f(int n) {
if (n<=1)
return 0;
return f(n/2) + 1;
}
Tiene complejidad de tiempo de orden O(log2(n)) . Aquí 2 es la base de logrithm.
int g(int n) {
int m = f(f(n)); // O(log2(log2(n))
int i, x=0;
for( i = 0; i < m; i++) {
x += i*i;
}
// This for loop will take O(log2(log2(n))
return m;
}
Por lo tanto, la complejidad global del tiempo de una función dada es: T(n) = t1 + t2 + t3
Pero aquí O(log2(n)) domina sobre O(log2(log2(n)) .
Por lo tanto, la complejidad del tiempo de una función dada es log2(n) .
Por favor, lea ¿Qué es una explicación simple en inglés de la notación "O grande"? una vez.