Si hay 2 algoritmos que calculan el mismo resultado con diferentes complejidades, ¿O (log n) siempre será más rápido? Si es así, por favor explique. Por cierto, esta no es una pregunta de asignación.¿Es O (log n) siempre más rápido que O (n)
No. Si un algoritmo se ejecuta en N/100 y el otro en (log N)*100, el segundo será más lento para tamaños de entrada más pequeños. Las complejidades asintóticas se refieren al comportamiento del tiempo de ejecución ya que los tamaños de entrada van al infinito.
entonces O (n) puede ser más rápido que O (log n) para una entrada extremadamente pequeña? – Varkolyn
1 * n es O (n). 10000000000000000000000000000000 * (log n) es O (log n). En tal caso, O (n) no solo será más rápido en una entrada extremadamente pequeña. Pero a medida que "n" crece hacia el infinito, * eventualmente * O (log n) será más rápido. –
@Varkolyn: No necesariamente * extremadamente *. Dependiendo del algoritmo, ¡el punto de cruce puede ser muy grande en * n *! – kkm
No, no siempre será más rápido. PERO, a medida que el tamaño del problema crece cada vez más, eventualmente siempre alcanzará un punto donde el algoritmo O (log n) es más rápido que el O (n).
En situaciones del mundo real, generalmente el punto donde el algoritmo O (log n) superaría al algoritmo O (n) vendría muy rápido. Hay una gran diferencia entre O (log n) y O (n), al igual que hay una gran diferencia entre O (n) y O (n^2).
Si alguna vez tiene la oportunidad de leer Perlas de programación por Jon Bentley, hay un capítulo increíble allí donde se enfrenta a un algoritmo O (n) contra un O (n^2) uno, haciendo todo lo posible da a O (n^2) la ventaja. (Codifica el algoritmo O (n^2) en C en un Alfa, y el algoritmo O (n) en BASIC interpretado en un viejo Z80 o algo así, corriendo a aproximadamente 1MHz.) Es sorprendente cuán rápido el O (n) el algoritmo supera al O (n^2) uno.
Ocasionalmente, sin embargo, puede encontrar un algoritmo muy complejo que tiene una complejidad ligeramente mejor que una más simple. En tal caso, no elija ciegamente el algoritmo con una gran O-mejor, puede encontrar que solo es más rápido en problemas extremadamente grandes.
Siempre será más rápido para lo suficientemente grande * n *. – Phonon