Análisis de Algoritmos Recursivos

Introducción

• Importancia de analizar algoritmos mediante la notación de Big O.
• Enfoque en algoritmos recursivos en este video.
• Presentación del profesor Chio, especializado en backend y arquitectura de software.

Resumen del Video Anterior

• Breve mención de la notación Big O y su definición formal.
• Relación entre el crecimiento del tiempo de ejecución de un algoritmo y la entrada.
• Análisis de complejidad de algoritmos no recursivos.

Algoritmos Recursivos

• Se presentan tres métodos para analizar la complejidad de algoritmos recursivos:
  1. Método de sustitución.
  2. Método del árbol recursivo.
  3. Método maestro.

¿Qué son las Recurrencias?

• Ecuaciones que definen una función en términos de su valor en instancias más pequeñas.
• Se utilizan para representar el tiempo de ejecución de funciones recursivas.

Ejemplos de Recurrencias

• Factorial:

  • Tiempo de ejecución: T(n) = T(n-1) + O(1).
  • Caso base: T(1) = O(1).

• Fibonacci:

  • Función de recurrencia: T(n) = T(n-1) + T(n-2).

• Subarreglo máximo:

  • Función de recurrencia: T(n) = T(n/2) + T(n/2) + O(n).
  • Detalles sobre el redondeo en arreglos impares.

Método de Sustitución

• Dos pasos principales:
  1. Adivinar la solución.
  2. Usar inducción matemática para verificar la solución.
• Ejemplo con subarreglo máximo:
  • Adivinanza inicial: T(n) = O(n log n).
  • Demostración con inducción sobre valores menores (m) y simplificaciones.

Método del Árbol Recursivo

• Visualización de las llamadas recursivas en un árbol.
• Representación gráfica de la división del problema.
• Calculo del tiempo total a partir de la suma de los nodos en cada nivel.
• Determinación de niveles: logaritmo en base al divisor.
• Sumar los totales por nivel para obtener la complejidad total.

Método Maestro

• Aplicable a funciones de recurrencia en la forma T(n) = aT(n/b) + f(n).
• Identificación de A, B y f(n).
• Cálculo de logaritmo base b de a para determinar el caso de la recurrencia:
  • Caso 1: f(n) crece más rápido.
  • Caso 2: f(n) y n^(log_b(a)) crecen igual.
  • Caso 3: f(n) crece más lento.
• Importante: debe cumplir la forma adecuada, no aplicable a todas las funciones.

Conclusión

• Resumen de los métodos presentados para analizar algoritmos recursivos.
• Invitación a profundizar en cada método y dejar comentarios con preguntas.
• Referencias adicionales en la descripción del video.
• Recordatorio para dar like, compartir y suscribirse.