¿Qué algoritmo es más rápido O (N) u O (2N)?

Hablando de notaciones de Big O, si una complejidad de tiempo de un algoritmo es O (N) y la de otro es O (2N), ¿cuál es más rápido?

La definición de gran O es:

O (f (n)) = {g | existen N y c> 0 tales que g (n) N}

En inglés, O (f (n)) es el conjunto de todas las funciones que tienen una tasa de crecimiento final 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, a saber, 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 tales que g (n) N. Entonces g (n) <(c / 2) * 2n para todo n> N. Entonces 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) N. Entonces g (n) <2c * n para todo n> N. Entonces g está en O (n).

Típicamente, cuando las personas se refieren a una complejidad asintótica (“O grande”), se refieren a las formas canónicas. Por ejemplo:

  • logarítmico: O (log n)
  • lineal: O (n)
  • linearitmico: 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 general, escribiría 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 uno no es “más rápido” que el otro. 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 de Big O” usa el término “crecimiento lento” en el que 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 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 que antes, donde la función O (n) tomaría aproximadamente el doble de tiempo que antes. .

Teóricamente O (N) y O (2N) son lo mismo.

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.

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 menor que 3n + 5 y más de 2 + n/1000

Es un poco como preguntar si 5 es menor que algún número no especificado entre 1 y 10. Depende del número no especificado. El solo hecho de saber que un algoritmo se ejecuta en O(n) pasos no es suficiente información para decidir si un algoritmo que toma 2n pasos completará más rápido o no.

En realidad, es incluso peor que eso: está preguntando si un número no especificado entre 1 y 10 es más grande que otro número no especificado entre 1 y 10. Los conjuntos que elige no son los mismos que usted elige. 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.