Estoy aprendiendo sobre los tiempos de ejecución en notación Big O y los tiempos amortizados. Entiendo la noción de O(n) tiempo lineal, lo que significa que el tamaño de la entrada afecta al crecimiento del algoritmo proporcionalmente...y lo mismo ocurre, por ejemplo, con el tiempo cuadrático O(n2) etc..incluso algoritmos, como los generadores de permutaciones, con tiempos O(n!), que crecen por factoriales.
Por ejemplo, la siguiente función es O(n) porque el algoritmo crece en proporción a su entrada n:
f(int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", i);
}
Del mismo modo, si hubiera un bucle anidado, el tiempo sería O(n2).
Pero, ¿qué es exactamente O(log n)? Por ejemplo, ¿qué significa decir que la altura de un árbol binario completo es O(log n)?
Sé (quizá no con mucho detalle) lo que es el logaritmo, en el sentido de que: log10 100 = 2, pero no puedo entender cómo identificar una función con un tiempo logarítmico.
El tiempo de ejecución logarítmico (O(log n)
) significa esencialmente que el tiempo de ejecución crece en proporción al logaritmo del tamaño de la entrada - como ejemplo, si 10 elementos tardan como máximo una cantidad de tiempo x
, y 100 elementos tardan como máximo, digamos, 2x
, y 10.000 elementos tardan como máximo 4x
, entonces parece una complejidad de tiempo O(log n)
.
Simplemente significa que el tiempo necesario para esta tarea crece con log(n) (ejemplo: 2s para n = 10, 4s para n = 100, ...). Lea los artículos de Wikipedia sobre Algoritmo de búsqueda binaria y Notación Big O para obtener más precisiones.