algorithm - relativamente - ¿Cuándo falla la notación Big-O?
grafica n log n (18)
- Pequeña N: y para las computadoras de hoy, es probable que 100 sea demasiado pequeño para preocuparse.
- Multiplicadores ocultos - IE fusionar vs ordenación rápida.
- Casos patológicos - De nuevo, fusionar vs rápido
¿Cuáles son algunos ejemplos donde la notación Big-O [1] falla en la práctica?
Es decir, ¿cuándo el tiempo de ejecución Big-O de los algoritmos predice que el algoritmo A sea más rápido que el algoritmo B, pero en la práctica el algoritmo B es más rápido cuando lo ejecutas?
Ligeramente más amplio: ¿cuándo las predicciones teóricas sobre el rendimiento del algoritmo no coinciden con los tiempos de ejecución? Una predicción que no sea de Big-O podría basarse en el número promedio / esperado de rotaciones en un árbol de búsqueda, o el número de comparaciones en un algoritmo de clasificación, expresado como un factor multiplicado por el número de elementos.
Aclaración :
A pesar de lo que dicen algunas de las respuestas, la notación Big-O pretende predecir el rendimiento del algoritmo. Dicho esto, es una herramienta defectuosa : solo habla sobre el rendimiento asintótico y difumina los factores constantes. Hace esto por una razón: pretende predecir el rendimiento algorítmico independientemente de la computadora en la que ejecutes el algoritmo.
Lo que quiero saber es esto : ¿cuándo se muestran las fallas de esta herramienta? He encontrado que la notación Big-O es razonablemente útil, pero está lejos de ser perfecta. ¿Cuáles son las trampas, los casos extremos, las trampas?
Un ejemplo de lo que estoy buscando: ejecutar el algoritmo de ruta más corto de Dijkstra con un montón Fibonacci en lugar de un montón binario, obtiene O (m + n log n) tiempo frente a O ((m + n) log n), para n Vértices y m aristas. Usted esperaría un aumento de velocidad del montón de Fibonacci tarde o temprano, pero dicho aumento de velocidad nunca se materializó en mis experimentos.
(La evidencia experimental, sin pruebas, sugiere que los montones binarios que operan con pesas de borde uniformemente aleatorias gastan O (1) tiempo en lugar de O (log n) tiempo; ese es un gran problema para los experimentos. número de llamadas a DecreaseKey).
[1] Realmente no es la notación la que falla, sino los conceptos de la notación y el enfoque teórico para predecir el rendimiento del algoritmo. </anti-pedantry>
En la respuesta aceptada :
He aceptado una respuesta para resaltar el tipo de respuestas que esperaba. Existen muchas respuestas diferentes que son igual de buenas :) Lo que me gusta de la respuesta es que sugiere una regla general para cuando la notación Big-O "falla" (cuando la memoria caché falla domina el tiempo de ejecución), lo que también puede aumentar la comprensión (en cierto sentido) No estoy seguro de cómo expresar mejor ATM).
Para la mayoría de los algoritmos hay un "caso promedio" y un "caso más desfavorable". Si sus datos caen rutinariamente en el "peor de los casos", es posible que otro algoritmo, aunque teóricamente menos eficiente en el caso promedio, sea más eficiente para sus datos.
Algunos algoritmos también tienen los mejores casos que sus datos pueden aprovechar. Por ejemplo, algunos algoritmos de clasificación tienen una eficacia teórica terrible, pero en realidad son muy rápidos si los datos ya están ordenados (o casi). Otro algoritmo, aunque teóricamente más rápido en el caso general, puede no aprovechar el hecho de que los datos ya están ordenados y en la práctica tienen un peor desempeño.
Para conjuntos de datos muy pequeños, a veces un algoritmo que tiene una mejor eficiencia teórica puede ser en realidad menos eficiente debido a un gran valor de "k".
Big O no dice, por ejemplo, que el algoritmo A se ejecute más rápido que el algoritmo B. Puede decir que el tiempo o el espacio utilizado por el algoritmo A crece a una velocidad diferente a la del algoritmo B, cuando la entrada aumenta. Sin embargo, para cualquier tamaño de entrada específico, la notación O grande no dice nada sobre el rendimiento de un algoritmo en relación con otro.
Por ejemplo, A puede ser más lento por operación, pero tiene una mejor O mayor que B. B es más eficaz para una entrada más pequeña, pero si el tamaño de los datos aumenta, habrá un punto de corte donde A se vuelve más rápido. Big-O en sí mismo no dice nada sobre dónde está ese punto de corte.
Big-O describe la eficiencia / complejidad del algoritmo y no necesariamente el tiempo de ejecución de la implementación de un bloque de código dado. Esto no significa que Big-O falle. Simplemente significa que no está destinado a predecir el tiempo de ejecución.
Echa un vistazo a la respuesta a esta pregunta para una gran definición de Big-O.
Cuando N es pequeño, el factor constante domina. Buscar un elemento en una matriz de cinco elementos es probablemente más rápido que buscarlo en una tabla hash.
Esta pregunta es como preguntar: "¿Cuándo falla el IQ de una persona en la práctica?" Está claro que tener un alto coeficiente intelectual no significa que tendrá éxito en la vida y tener un bajo coeficiente intelectual no significa que perecerá. Sin embargo, medimos el coeficiente intelectual como un medio para evaluar el potencial, incluso si no es un absoluto.
En los algoritmos, la notación Big-Oh le da el coeficiente intelectual del algoritmo. No significa necesariamente que el algoritmo se desempeñará mejor para su situación particular, pero hay alguna base matemática que dice que este algoritmo tiene un buen potencial. Si la notación Big-Oh fuera suficiente para medir el rendimiento, vería mucho más y menos pruebas de tiempo de ejecución.
Piense en Big-Oh como un rango en lugar de una medida específica de mejor o peor. Hay mejores escenarios de casos y peores casos y un gran conjunto de escenarios intermedios. Elija sus algoritmos por lo bien que encajan dentro del rango Big-Oh, pero no confíe en la notación como un absoluto para medir el rendimiento.
Esto depende en cierta medida de lo que esté midiendo el Big-O: cuando se trata de los peores escenarios, por lo general "fallará" en que el rendimiento en tiempo de ejecución será mucho mejor de lo que sugiere el Big-O. Si es un caso promedio, entonces puede ser mucho peor.
La notación Big-O normalmente "falla" si los datos de entrada al algoritmo tienen alguna información previa. A menudo, la notación Big-O se refiere a la complejidad del peor de los casos, que a menudo ocurrirá si los datos son completamente aleatorios o no aleatorios.
Como ejemplo, si alimenta datos a un algoritmo que se perfila y el big-o se basa en datos aleatorios, pero sus datos tienen una estructura muy bien definida, sus tiempos de resultados pueden ser mucho más rápidos de lo esperado. De la misma manera, si está midiendo la complejidad promedio, y alimenta datos que son horriblemente aleatorios, el algoritmo puede tener un rendimiento mucho peor de lo esperado.
Falla en exactamente un caso: cuando las personas intentan usarlo para algo, no es para eso.
Te dice cómo se escala un algoritmo. No te dice qué tan rápido es.
La notación Big-O no le dice qué algoritmo será más rápido en ningún caso específico. Solo te dice que para una entrada suficientemente grande, una será más rápida que la otra.
He visto algunos casos en los que, a medida que el conjunto de datos creció, la complejidad algorítmica se volvió menos importante que el patrón de acceso a la memoria. Navegar por una estructura de datos grande con un algoritmo inteligente puede, en algunos casos, causar muchas fallas de página o fallos de caché, que un algoritmo con una O mayor grande.
Para n pequeña, dos algoritmos pueden ser comparables. A medida que n aumenta, el algoritmo más inteligente supera. Pero, en algún momento, n crece lo suficiente como para que el sistema sucumba a la presión de la memoria, en cuyo caso el algoritmo "peor" puede funcionar mejor porque las constantes se restablecen esencialmente.
Sin embargo, esto no es particularmente interesante. Para cuando llega a este punto de inversión, el rendimiento de ambos algoritmos suele ser inaceptable, y tiene que encontrar un nuevo algoritmo que tenga un patrón de acceso a la memoria más amigable Y una mejor complejidad de O grande.
La respuesta corta: siempre en el hardware moderno cuando empiece a usar mucha memoria. Los libros de texto asumen que el acceso a la memoria es uniforme, y ya no lo es. Por supuesto, puede hacer un análisis de Big O para un modelo de acceso no uniforme, pero eso es algo más complejo.
Los pequeños n casos son obvios pero no interesantes: lo suficientemente rápido es lo suficientemente rápido.
En la práctica, he tenido problemas al utilizar las colecciones estándar en Delphi, Java, C # y Smalltalk con unos pocos millones de objetos. Y con los más pequeños, donde el factor dominante resultó ser la función hash o la comparación
La respuesta general es que Big-O te permite ser realmente descuidado ocultando los factores constantes. Como se mencionó en la pregunta, el uso de Fibonacci Heaps es un ejemplo. Los montones de Fibonacci tienen grandes tiempos de ejecución asintóticos, pero en la práctica los factores constantes son demasiado grandes para ser útiles para los tamaños de conjuntos de datos encontrados en la vida real.
Los montones de Fibonacci se utilizan a menudo para demostrar un buen límite inferior para la complejidad asintótica de los algoritmos relacionados con gráficos.
Otro ejemplo similar es el algoritmo Coppersmith-Winograd para la multiplicación de matrices. Actualmente es el algoritmo con el tiempo de ejecución asintótico más rápido conocido para la multiplicación de matrices, O (n 2.376 ). Sin embargo, su factor constante es demasiado grande para ser útil en la práctica. Al igual que Fibonacci Heaps, se usa frecuentemente como un bloque de construcción en otros algoritmos para probar los límites de tiempo teóricos.
Respuesta corta: cuando n es pequeña. El problema del vendedor viajero se resuelve rápidamente cuando solo tiene tres destinos (sin embargo, encontrar el número más pequeño en una lista de un billón de elementos puede durar un tiempo, aunque esto es O (n)).
Robert Sedgewick habla sobre las deficiencias de la notación big O en su curso de Coursera sobre Análisis de Algoritmos. Llama a ejemplos particularmente notorios algoritmos galácticos porque, si bien pueden tener una clase de complejidad mejor que sus predecesores, tomaría insumos de tamaños astronómicos para que se muestren en la práctica.
Un área amplia donde falla la notación Big-Oh es cuando la cantidad de datos excede la cantidad disponible de RAM.
Al usar la clasificación como ejemplo, la cantidad de tiempo que lleva ordenar no está dominada por el número de comparaciones o swaps (de los cuales hay O (n log n) y O (n), respectivamente, en el caso óptimo). La cantidad de tiempo está dominada por la cantidad de operaciones de disco: escrituras de bloque y lecturas de bloque.
Para analizar mejor los algoritmos que manejan datos que superan la RAM disponible, nació el modelo de E / S, donde se cuenta el número de lecturas de disco. En eso, consideras tres parámetros:
- El número de elementos, N;
- La cantidad de memoria (RAM), M (la cantidad de elementos que pueden estar en la memoria); y
- El tamaño de un bloque de disco, B (el número de elementos por bloque).
Notablemente ausente es la cantidad de espacio en disco; Esto se trata como si fuera infinito. Una suposición adicional típica es que M> B 2 .
Continuando con el ejemplo de clasificación, normalmente favorece la ordenación por fusión en el caso de E / S: divida los elementos en trozos de tamaño θ (M) y ordénelos en la memoria (con, por ejemplo, quicksort). Luego, fusione θ (M / B) de ellos leyendo el primer bloque de cada fragmento en la memoria, rellene todos los elementos en un montón, y elija repetidamente el elemento más pequeño hasta que haya elegido B de ellos. Escribe este nuevo bloque de fusión y continúa. Si alguna vez agota uno de los bloques que lee en la memoria, lea un bloque nuevo del mismo fragmento y colóquelo en el montón.
(Todas las expresiones deben leerse como grandes θ). Usted forma trozos ordenados N / M que luego fusiona. Usted fusiona el registro (base M / B) de N / M veces; cada vez que lee y escribe todos los bloques N / B, por lo que le lleva N / B * (base de registro M / B de N / M) tiempo.
Puede analizar los algoritmos de clasificación en memoria (modificados adecuadamente para incluir lecturas de bloque y escrituras de bloque) y ver que son mucho menos eficientes que el tipo de combinación que he presentado.
Este conocimiento es cortesía de mi curso de algoritmos de E / S, por Arge y Brodal ( http://daimi.au.dk/~large/ioS08/ ); También realicé experimentos que validan la teoría: la ordenación de pilas lleva un tiempo "casi infinito" una vez que superas la memoria. La ordenación rápida se vuelve insoportablemente lenta, la ordenación por fusión es ligeramente más soportable, la ordenación por fusión eficiente en E / S funciona bien (la mejor de todas).
Un área donde falla Big O es patrones de acceso a la memoria. Big O solo cuenta las operaciones que deben realizarse; no puede realizar un seguimiento si un algoritmo produce más fallas en la memoria caché o datos que necesitan ser pagados desde el disco. Para la N pequeña, estos efectos típicamente dominarán. Por ejemplo, una búsqueda lineal a través de una matriz de 100 enteros probablemente superará una búsqueda a través de un árbol binario de 100 enteros debido a los accesos a la memoria, aunque el árbol binario probablemente requerirá menos operaciones. Cada nodo de árbol daría lugar a una falla de caché, mientras que la búsqueda lineal se aplicaría principalmente a la caché para cada búsqueda.
Un ejemplo (en el que no soy un experto) es que los algoritmos símplex para programación lineal tienen una complejidad exponencial en el peor de los casos en entradas arbitrarias, aunque se desempeñen bien en la práctica. Una solución interesante para esto es considerar la "complejidad suavizada", que combina el peor de los casos y el rendimiento promedio de los casos al observar pequeñas perturbaciones aleatorias de entradas arbitrarias.
Spielman y Teng (2004) pudieron demostrar que el algoritmo simplex de vértice de la sombra tiene una complejidad suavizada de polinomios.
el ejemplo canónico es Quicksort, que tiene un peor momento de O (n ^ 2), mientras que Heapsort es O (n logn). Sin embargo, en la práctica, Quicksort suele ser más rápido que Heapsort. ¿por qué? dos razones:
Cada iteración en Quicksort es mucho más simple que Heapsort. Aún más, es fácilmente optimizado por estrategias de caché simples.
El peor de los casos es muy difícil de golpear.
Pero en mi humilde opinión, esto no significa que "la gran O falla" de ninguna manera. el primer factor (tiempo de iteración) es fácil de incorporar en sus estimaciones. después de todo, los grandes números O deben multiplicarse por este hecho casi constante.
el segundo factor se derrite si obtiene las cifras amortizadas en lugar del promedio. Pueden ser más difíciles de estimar, pero cuentan una historia más completa.
Cuando sus datos no se ajustan al modelo , la notación big-o seguirá funcionando, pero verá una superposición de los mejores y peores escenarios.
Además, algunas operaciones están sintonizadas para el acceso a datos lineales frente al acceso a datos aleatorios , por lo que un algoritmo, aunque es superior en términos de ciclos, podría ser lento si el método de llamarlo cambia del diseño. De manera similar, si un algoritmo provoca que la página / caché se pierda debido a la forma en que accede a la memoria, Big-O no proporcionará una estimación precisa del costo de ejecutar un proceso.
Aparentemente, como he olvidado, también cuando N es pequeña :)