algorithm - resueltos - complejidad en el tiempo
¿Hay una lista maestra de la notación Big-O para todo? (6)
¿Hay una lista maestra de la notación Big-O para todo? Estructuras de datos, algoritmos, operaciones realizadas en cada caso, promedio de casos, el peor de los casos, etc.
En c ++, los estándares STL se definen por las características Big-O de los algoritmos, así como por 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 podrían incluso ser mejores listas de casos particulares de tipos particulares que los requisitos estándar.
Facilitó la elección del tipo de iterador o lista correcto para un problema en particular, ya que podía pesar fácilmente entre el consumo de espacio y la velocidad.
Por supuesto, Big-O es solo una línea guía ya que todas las constantes se eliminan. 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.
Pruebe " Introducción a los algoritmos " de 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 cercano que se me ocurre.
Si eso falla, entonces prueba The Art of Computer Programming , por Knuth. Si no está en eso, probablemente necesites hacer una investigación real.
El libro de Cormen trata más sobre cómo enseñarle cómo sería Big-O para un algoritmo determinado, en lugar de memorizar algoritmos para su desempeño de Big-O. El primero es mucho más valioso que el segundo y requiere una inversión de su parte.
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.
Para cualquiera, que está llegando a esta pregunta de Google.