Como se mencionó en la respuesta a la pregunta vinculada, una forma común para que un algoritmo tenga una complejidad de tiempo O(log n) es que ese algoritmo trabaje recortando repetidamente el tamaño de la entrada por algún factor constante en cada iteración.
¿Cuál es el significado de log n?
O(log N) básicamente significa el tiempo aumenta linealmente mientras que n aumenta exponencialmente. Por tanto, si tarda 1 segundo en calcular 10 elementos, tardará 2 segundos en calcular 100 elementos, 3 segundos en calcular 1000 elementos, y así sucesivamente. Es O(log n) cuando dividimos y conquistamos tipos de algoritmos, por ejemplo, búsqueda binaria.
¿Qué es O y log n?
Para la entrada de tamaño n, un algoritmo de O(n) realizará pasos proporcionales a n, mientras que otro algoritmo de O(log(n)) realizará pasos aproximadamente log(n). Claramente, log(n) es más pequeño que n, por lo que el algoritmo de complejidad O(log(n)) es mejor.
¿Cómo se calcula log n?
La idea es que un algoritmo es O(log n) si en lugar de desplazarse por una estructura 1 por 1, divide la estructura por la mitad una y otra vez y realiza un número constante de operaciones para cada división. Los algoritmos de búsqueda en los que el espacio de respuesta sigue dividiéndose son O(log n).
¿Qué es log n Square?
Registro ^2 (
) significa que es proporcional al log del log para un problema de tamaño
. Registro(
)^ 2 significa que esproporcional al cuadrado del log.
