Para aquellos que recién comienzan a hacer análisis de algoritmos, esbozar el árbol de recursión (solo uno o dos niveles) y razonar sobre él podría ser la forma más fácil de analizar las recurrencias. Dibuje el árbol de recursión y pregunte cuánto trabajo está sucediendo en cada nivel (profundidad de nodo) y cuántos niveles hay. Hay 3 casos principales:
(1) La cantidad de tiempo necesario por nivel es la misma . Entonces, la complejidad es la cantidad de trabajo por nivel multiplicado por el número de niveles. Por ejemplo, si tiene T (n) = 2T (n / 2) + O (n), entonces el trabajo realizado en cada nivel es O (n). Hay niveles de log n en el árbol de recursión, por lo que la complejidad es O (n log n).
(2) La cantidad de tiempo por nivel disminuye con el nivel exponencialmente. Por ejemplo, T (n) = 2T (n / 2) + O (n ^ 2). Cada nivel subsiguiente toma la mitad del tiempo del anterior. Esta es una serie geométrica, por lo que la complejidad total está determinada por la complejidad del primer nivel (tiempo cuadrático en este ejemplo).
- ¿El aprendizaje por refuerzo está recibiendo actualmente más atención que los algoritmos genéticos?
- ¿Por qué recibo un error de tiempo de ejecución en la conversión de un árbol binario a un árbol binario enhebrado?
- No soy bueno en algoritmos, pero estoy tratando de descubrir algo. ¿Cuáles son algunas técnicas o libros o alguna sugerencia?
- ¿Cuál es el algoritmo más genial (programación competitiva) que hayas encontrado?
- ¿Cuáles son los mejores algoritmos híbridos para el filtrado colaborativo y basado en contenido?
(3) La cantidad de tiempo por nivel aumenta exponencialmente. Entonces, la complejidad del tiempo es la misma que la del último nivel (dado que las complejidades del tiempo para los niveles forman una serie geométrica cuando se leen del último al primero). Por ejemplo, la recurrencia T (n) = 2 T (n / 2) + O (1) cae en esta categoría. Cada nivel tiene el doble del costo del anterior, y el último nivel cuesta O (n). La complejidad es, por lo tanto, O (n).
Lo que se discutió anteriormente es básicamente una versión simplificada de lo que se conoce como el Teorema Maestro para las recurrencias. Cubre muchas de las recurrencias más básicas que necesita resolver, aunque obviamente no todo.
