¿Hay una lista maestra de la notación Big-O para todo? Las estructuras de datos, algoritmos, las operaciones realizadas en cada una, promedio de los casos, peor de los casos, etc.¿Hay una lista maestra de la notación Big-O para todo?
Dictionary of Algorithms and Data Structures es una lista bastante completa e incluye la complejidad (Big-O) en las descripciones de los algoritmos. Si necesita más información, estará en una de las referencias vinculadas, y siempre hay Wikipedia como una alternativa.
Try "Introduction to Algorithms" por Cormen, Leisersen y Rivest. Si no está allí, probablemente no valga la pena saberlo.
Introduction to Algorithms, Second Edition, también conocido como CLRS (Cormen, Leiserson, Rivest, Stein), es lo más parecido que se me ocurre.
Si eso falla, intente The Art of Computer Programming, por Knuth. Si no está en eso, probablemente necesites hacer una investigación real.
El Cormen book es más sobre cómo enseñarle cómo demostrar Big-O para un algoritmo determinado, en lugar de memorizar algoritmos para su funcionamiento de Big-O. El primero es mucho más valioso que el segundo y requiere una inversión de su parte.
En C++, los estándares STL se definen por las características Big-O de los algoritmos, así como los requisitos de espacio. De esta forma, podría cambiar entre las implementaciones de STL que compiten entre sí y aún así saber que su programa tenía las mismas características de tiempo de ejecución. Implementaciones STL particularmente buenas incluso podrían ser mejores listas especiales de casos de tipos particulares que los requisitos estándar.
Facilitó la selección del tipo de lista o iterador correcto para un problema en particular, ya que podía pesar fácilmente entre el consumo de espacio y la velocidad.
Ofcourse Big-O es solo una línea de guía ya que se eliminan todas las constantes. Si un algoritmo se ejecuta en k * O (n), se clasificaría como O (n), pero si k es suficientemente alto, podría ser peor que O (n^2) para algunos valores de n y m.
Para cualquier persona que tenga esta pregunta de Google.
he descargado todas las páginas e hice una lista de todas las páginas que proporciona Big O: https://pastebin.com/X3c7i4aF – BlackCap