resueltos recursivos notacion lineal grande ejercicios ejemplos complejidad big analisis algoritmos algoritmo algorithm

algorithm - recursivos - Recurso sobre la complejidad del tiempo de cálculo de los algoritmos



notacion big o (7)

Chicos, todos recomiendan libros de teoría de la complejidad verdadera: Arora y Barak contienen todo tipo de cosas como PCP, pruebas interactivas, computación cuántica y temas sobre gráficos de expansor, cosas que la mayoría de los programadores / desarrolladores de software nunca han escuchado o harán. utilizar. Papdimitriou está en la misma categoría. Knuth es completamente imposible de leer (y yo era un CS / Math major) y no me da ninguna intuición sobre cómo funcionan las cosas.

Si desea una forma simple de calcular los tiempos de ejecución y obtener el sabor del análisis, pruebe el primer capítulo del "Diseño y análisis de algoritmos" de Kleinberg and Tardos, que le permite examinar los fundamentos y luego puede trabajar en problemas mucho más difíciles.

¿Hay algún buen recurso (libro, referencia, sitio web, aplicación ...) que explique cómo calcular la complejidad temporal de un algoritmo?

Porque, es difícil hacer las cosas concretas en mi mente. A veces se trata de una iteración que tiene una complejidad temporal de lg n; y luego de acuerdo con el otro ciclo se convierte en nlg n; y a veces usan una gran notación omega para expresarlo, a veces big-o, etc.

Estas cosas son bastante abstractas para mí. Entonces, necesito un recurso que tenga una buena explicación y muchos ejemplos para hacerme ver qué sucede.

Con suerte, expliqué mi problema con claridad. Estoy bastante seguro de que todos los que acaban de empezar a estudiar algoritmos también tienen el mismo problema conmigo. Entonces, tal vez esos muchachos con experiencia también puedan compartir su experiencia con nosotros. Gracias...

El conjunto clásico de libros sobre el tema es Knuth''s Art of Computer Programming series. Son pesados ​​en teoría y pruebas formales, así que repasa tu cálculo antes de abordarlos.

Leí la Complejidad Computacional de Christos Papadimitriou en la universidad y realmente lo disfruté. No es una tarea fácil, el libro es largo pero está bien escrito (es decir, comprensible y adecuado para la autoaprendizaje) y contiene muchos conocimientos útiles, mucho más que solo el "cómo descubro la complejidad del tiempo del algoritmo x". .

Estoy de acuerdo en que la Introducción a los Algoritmos es un buen libro. Para obtener instrucciones más detalladas sobre, por ejemplo, cómo resolver las relaciones de recurrencia, véase Knuth''s Concrete Mathematics . Un buen libro sobre complejidad computacional en sí mismo es el de Papadimitriou . Pero ese último libro podría ser demasiado minucioso si solo quiere calcular la complejidad de los algoritmos dados.

Una breve descripción general sobre la notación de O-O-grande

  • Si puede proporcionar un algoritmo que resuelva un problema en el tiempo T (c * (n log n)) ( c es una constante), entonces la complejidad temporal de ese problema es O (n log n) . La gran O se deshace de la c , es decir, cualquier factor constante que no depende del tamaño de entrada n . Big-O le da un límite superior en el tiempo de ejecución, porque usted ha demostrado (al dar un algoritmo) que puede resolver el problema en ese período de tiempo.
  • Si puede dar una prueba de que cualquier algoritmo que resuelve el problema toma al menos tiempo T (c * (n log n)) que el problema está en Omega (n log n) . Big-Omega le da un límite inferior al problema. En la mayoría de los casos, los límites inferiores son mucho más difíciles de probar que los límites superiores, porque debes demostrar que cualquier posible algoritmo para el problema requiere al menos T (c * (n log n) . Conocer un límite inferior no significa conocer un algoritmo que alcanza ese límite inferior.
  • Si tiene un límite inferior, por ejemplo, Omega (n log n) , y un algoritmo que resuelve el problema en ese momento (un límite superior), entonces el problema está en Theta (n log n) . Esto significa que se conoce un algoritmo "óptimo" para este problema. Por supuesto, esta notación oculta el factor constante c, que puede ser bastante grande (es por eso que escribí óptimo entre comillas).

Tenga en cuenta que cuando usa estas notaciones, generalmente está hablando del peor tiempo de ejecución de un algoritmo.