algorithm - oficial - weka ejemplos
¿Qué algoritmo es más rápido O(N) u O(2N)? (4)
Depende de las constantes ocultas por la notación asintótica.
Por ejemplo, un algoritmo que toma
3n + 5
pasos está en la clase
O(n)
.
Entonces, es un algoritmo que toma
2 + n/1000
pasos.
Pero
2n
es menos de
3n + 5
y más de
2 + n/1000
...
Es un poco como preguntar si
5
es menor que un número no especificado entre 1 y 10. Depende del número no especificado.
Solo saber que un algoritmo se ejecuta en
O(n)
pasos no es suficiente información para decidir si un algoritmo que toma
2n
pasos se completará más rápido o no.
En realidad, es aún peor que eso: estás preguntando si algún número no especificado entre 1 y 10 es mayor que otro número no especificado entre 1 y 10. Los conjuntos que eliges no son los mismos que eliges. será 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.
Hablando de notaciones Big O, si la complejidad del tiempo de un algoritmo es O (N) y la del otro es O (2N), ¿cuál es más rápido?
La answer 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 gran término para aplicar aquí.
El artículo de Wikipedia sobre "Big O notation" usa el término "crecimiento más lento" donde podría haber usado "más rápido", que es una mejor práctica. Estos algoritmos se definen por cómo crecen a medida que n aumenta.
Uno podría imaginar fácilmente una función O (n ^ 2) que es 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, uno puede esperar que la función O (n ^ 2) tome aproximadamente 4 veces más tiempo que antes, donde la función O (n) tomaría aproximadamente el doble de tiempo que antes .
La definición de O grande es:
O (f (n)) = {g | existen N y c> 0 de modo 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 que la de f.
Entonces O (n) = O (2n). Ninguno de los dos 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 yc> 0 de modo que g (n) <c * n para todos n> N. Entonces g (n) <(c / 2) * 2n para todos n> N. Así, g está en O (2n )
O (2n) es un subconjunto de O (n): Sea g una función en O (2n). Luego hay N y c> 0 de modo que g (n) <c * 2n para todos n> N. Entonces g (n) <2c * n para todos n> N. Así, g está en O (n).
Por lo general, cuando las personas se refieren a una complejidad asintótica ("gran O"), se refieren a las formas canónicas. Por ejemplo:
- logarítmico: O (log n)
- lineal: O (n)
- linealitmico: O (n log n)
- cuadrático: O (n 2 )
- exponencial: O (c n ) para algunos c> 1 fijo
(Aquí hay una lista más completa: Tabla de complejidades de tiempo comunes )
Por lo tanto, normalmente escribirías O (n), no O (2n); O (n log n), no O (3 n log n + 15 n + 5 log n).
Teóricamente, O (N) y O (2N) son iguales.
Pero prácticamente, 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.