Dominando el Cálculo de T(n): Análisis de Complejidad de Algoritmos Recursivos

¡Bienvenido a nuestro video sobre el Análisis de Complejidad de Algoritmos! Aquí desglosaremos el cálculo de T(n), una función esencial que mide el número de pasos o instrucciones que un algoritmo ejecuta para una entrada de tamaño 'n'. A diferencia de las mediciones en segundos, T(n) ofrece una evaluación objetiva e independiente del hardware o compilador, basándose en el concepto de una máquina idealizada y operaciones elementales (OE) de tiempo constante. Nos enfocamos en el peor caso para garantizar el rendimiento máximo en las condiciones más desfavorables.
Para algoritmos iterativos, aprenderás a calcular T(n) sumando las operaciones elementales ejecutadas por cada sentencia o estructura de control. Las sentencias simples y secuenciales tienen una complejidad constante (O(1)). En las sentencias condicionales (if/else), se determina la complejidad sumando el costo de la condición y el máximo costo de las ramas de código que pueden ejecutarse. Para los bucles de repetición (For y While), el tiempo de ejecución es el producto del número de iteraciones por el tiempo de ejecución del cuerpo del bucle. Esto resulta en complejidades lineales (O(n)) para bucles simples, cuadráticas (O(n²)) para bucles anidados, y logarítmicas (O(log n)) en casos donde los índices no se incrementan linealmente, como cuando se duplican o dividen. En estos casos no lineales, exploramos la creación de tablas para relacionar la iteración con el índice y despejar la cantidad de iteraciones en función de 'n'.
En cuanto a algoritmos recursivos, la complejidad se modela con ecuaciones de recurrencia. Estas tienen un caso base (el costo de las condiciones de parada, generalmente una constante) y un caso recursivo (el costo de las operaciones básicas realizadas en cada llamada, más el costo de las llamadas recursivas con entradas más pequeñas). Presentamos una metodología estructurada de cinco pasos para resolver estas ecuaciones de recurrencia:
1. Establecer las ecuaciones de recurrencia: Definiendo T(n) para el caso base y el caso general.
2. Eliminar la recurrencia: Resolviendo la ecuación recurrente, a menudo mediante el método de sustitución o iteraciones sucesivas hasta alcanzar el caso base.
3. Derivar el número de iteraciones: Calculando cuántas iteraciones ('i' o 'k') son necesarias para llegar al caso base, expresándolas en términos de 'n'.
4. Calcular las constantes: Determinando los valores constantes acumulados durante el proceso de eliminación de la recurrencia.
5. Reescribir la ecuación no recursiva: Obteniendo la fórmula final de T(n) de manera explícita. Aplicaremos esta metodología a un ejemplo detallado como el algoritmo T(n)=2*T(n-1), donde a través de un patrón de llamadas y sustituciones, la complejidad final se aproxima a O(2^n). También se menciona el algoritmo de Fibonacci como otro ejemplo de recurrencia.
Además, el video cubre el Teorema Maestro, una técnica poderosa y elegante utilizada para resolver ecuaciones de recurrencia que tienen la forma T(n)=aT(n/b)+f(n). Proporciona una solución directa, transformando la recurrencia en una clase de complejidad asintótica conocida al comparar el crecimiento de f(n) (costo de operaciones no recursivas) con n elevado a la logaritmo en base b de a (costo de llamadas recursivas). El teorema distingue tres casos que cubren la mayoría de las recurrencias comunes. Ejemplos clave de su aplicación incluyen la Búsqueda Binaria (cuya ecuación es T(n)=T(n/2)+1, resultando en una complejidad Θ(log n)) y el algoritmo Merge Sort (con T(n)=2T(n/2)+n, que deriva en una complejidad Θ(n log n)).
Comprender T(n) y el Teorema Maestro es esencial para clasificar los algoritmos utilizando notaciones asintóticas como Big O (O), Big Omega (Ω) y Big Theta (Θ). Este conocimiento te permitirá comparar y diseñar soluciones de software eficientes, robustas y escalables.

Entendido! Aquí tienes la lista de las fuentes utilizadas, con los títulos completos de los videos y el nombre completo del documento PDF:
• "Análisis de Algoritmos Recursivos T(n)=2*T(n-1)" (Viera Class)
• "CTEDyA - Clase 6 - Tiempo de ejecución de algoritmos iterativos" (Leonardo Amet)
• "Clase 1: Cálculo del Tn" (Matias Agustín Pérez)
• "Cálculo de tiempo de ejecución de algoritmos lineales recursivos" (Programando en la U)
• Investigación de Gemini: "T(n)_Tiempo_Ejecucion.pdf"