¿Hay una lista maestra de la notación Big-O para todo?
https://stackoverflow.com/questions/180510
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Hay una lista maestra de la notación Big-O para todo? Estructuras de datos, algoritmos, operaciones realizadas en cada caso, caso medio, caso más desfavorable, etc.
Solución
Diccionario de algoritmos y estructuras de datos es una lista bastante completa e incluye complejidad ( 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 alternativa.
Otros consejos
El libro de Cormen es más sobre cómo enseñarle cómo demostrar qué Big -O sería para un algoritmo dado, en lugar de memorización memorizada del algoritmo para su rendimiento Big-O. Lo primero es mucho más valioso que lo segundo, y requiere una inversión de su parte.
Intente " Introducción a los algoritmos " por Cormen, Leisersen, y Rivest. Si no está allí probablemente no vale la pena saberlo.
En c ++, los estándares STL se definen por las características Big-O de los algoritmos, así como los requisitos de espacio. De esa manera, podría cambiar entre las implementaciones de STL de la competencia y saber que su programa tenía las mismas características de tiempo de ejecución. Particularmente buenas implementaciones de STL podrían incluso listas de casos especiales de tipos particulares para ser mejores que los requisitos estándar.
Facilitó la selección del tipo de iterador o lista correcto para un problema particular, ya que fácilmente podría pesar entre el consumo de espacio y la velocidad.
Por supuesto, Big-O es solo una línea 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.
Introducción a los algoritmos, segunda edición , también conocida como CLRS (Cormen, Leiserson, Rivest, Stein) , es lo más cercano que puedo pensar.
Si eso no funciona, intente El arte de la programación de computadoras , por Knuth. Si no está en ellos, probablemente necesites hacer una investigación real.
A cualquiera que llegue a esta pregunta de Google.
