¿Qué algoritmo es más rápido O(N) u O(2N)?
Hablando de notaciones Big O, si la complejidad temporal de un algoritmo es O (N) y la del otro es O (2N), ¿cuál es más rápido?
La definición de O grande es:
O(f(n)) = { gramo | existen N y c > 0 tales que g(n) < c * f(n) para todo n > N }
En inglés, O(f(n)) es el conjunto de todas las funciones que tienen una tasa de crecimiento eventual menor o igual a la de f.
Entonces O(n) = O(2n). Ninguno es "más rápido" que el otro en términos de complejidad asintótica. Representan las mismas tasas de crecimiento, es decir, la tasa de crecimiento " lineal ".
Prueba:
O(n) es un subconjunto de O(2n): Sea g una función en O(n). Entonces hay N y c > 0 tales que g(n) < c * n para todo n > N. Entonces g(n) < (c / 2) * 2n para todo n > N. Por lo tanto, g está en O(2n ).
O(2n) es un subconjunto de O(n): Sea g una función en O(2n). Entonces hay N y c > 0 tales que g(n) < c * 2n para todo n > N. Entonces g(n) < 2c * n para todo n > N. Por tanto, g está en O(n).
Normalmente, cuando la gente se refiere a una complejidad asintótica ("gran O"), se refiere a las formas canónicas. Por ejemplo:
- logarítmico: O(log n)
- lineal: O(n)
- linealítmico: O(n log n)
- cuadrático: O(n 2 )
- exponencial: O(c n ) para algún fijo c > 1
(Aquí hay una lista más completa: Tabla de complejidades temporales comunes )
Por lo general, escribirías O(n), no O(2n); O(n log n), no O(3 n log n + 15 n + 5 log n).
La respuesta de Timothy Shield es absolutamente correcta, que O(n) y O(2n) se refieren al mismo conjunto de funciones, por lo que una no es "más rápida" que la otra. Sin embargo, es importante tener en cuenta que más rápido no es un buen término para aplicar aquí.
El artículo de Wikipedia sobre "notación O grande" utiliza el término "crecimiento más lento" donde podría haber usado "más rápido", lo cual es una mejor práctica. Estos algoritmos se definen por cómo crecen a medida que aumenta n .
Uno podría imaginar fácilmente una función O(n^2) que sea más rápida que O(n) en la práctica, particularmente cuando n es pequeña o si la función O(n) requiere una transformación compleja. La notación indica que para el doble de entrada, se puede esperar que la función O(n^2) tarde aproximadamente 4 veces más que antes, mientras que la función O(n) tardaría aproximadamente el doble que antes. .
Depende de las constantes ocultas por la notación asintótica. Por ejemplo, un algoritmo que toma 3n + 5pasos está en la clase O(n). También lo es un algoritmo que toma 2 + n/1000pasos. Pero 2nes menos que 3n + 5y más que 2 + n/1000...
Es un poco como preguntar si 5es menor que algún número no especificado entre 1 y 10. Depende del número no especificado. El simple hecho de saber que un algoritmo se ejecuta en O(n)pasos no es información suficiente para decidir si un algoritmo que sigue 2npasos se completará más rápido o no.
En realidad, es incluso peor que eso: estás preguntando si algún número no especificado entre 1 y 10 es mayor que algún otro número no especificado entre 1 y 10. Los conjuntos que eliges son iguales no significa que los números que eliges sera igual! O(n)y O(2n)son conjuntos de algoritmos, y debido a que la definición de Big-O cancela los factores multiplicativos, son el mismo conjunto. Los miembros individuales de los conjuntos pueden ser más rápidos o más lentos que otros miembros, pero los conjuntos son los mismos.
Teóricamente O(N) y O(2N) son iguales.
Pero en la práctica, O(N) definitivamente tendrá un tiempo de ejecución más corto, pero no significativo. Cuando N es lo suficientemente grande, el tiempo de ejecución de ambos será idéntico.
