Pregunta 2.d-e · Prácticas de programación UOC 2021

d. [15%] Orden de complejidad asintótica obtenido

Solución: $O(n)$

d. [15%] Formula y resuelve de manera exhaustiva la ecuación en recurrencia que modela la complejidad temporal de la implementación recursiva original (peor caso)

Solución: Cálculo analítico de la complejidad: Definimos el tamaño del problema como el número de elementos restantes entre los dos extremos, es decir, $p = b - a$. - Caso base ($p = 0$, es decir, $a = b$): Se realiza una comprobación condicional, un acceso a posición de array y una asignación. Todas son instrucciones elementales que englobamos en una constante de tiempo $k_1$. - Paso recursivo ($p > 0$): En el peor caso (cuando se efectúa la actualización del mínimo), se evalúan las dos estructuras de control if, los accesos indexados al vector, la operación de suma en la llamada y la reasignación de variable, sumando un coste constante $k_2$ más el tiempo de la llamada interna con tamaño reducido en 1 ($p - 1$). El sistema en recurrencia queda configurado por: $$T(p) = \begin{cases} k_1 & \text{si } p = 0 \\ k_2 + T(p - 1) & \text{si } p > 0 \end{cases}$$ Desarrollo mediante el método de expansión o sustituciones sucesivas: $$\begin{aligned} T(p) &= k_2 + T(p - 1) \\ &= k_2 + (k_2 + T(p - 2)) = 2k_2 + T(p - 2) \\ &= 3k_2 + T(p - 3) \\ &= \dots \\ &= i \cdot k_2 + T(p - i) \end{aligned}$$ Para alcanzar la base recursiva exigimos $p - i = 0 \implies i = p$. Sustituyendo el índice: $$T(p) = p \cdot k_2 + T(0) = p \cdot k_2 + k_1$$ Por consiguiente, la complejidad temporal es de orden lineal, esto es, $O(p) = O(b - a)$.

e. [5%] Si se planteara una solución alternativa cuya complejidad algorítmica fuera igualmente de orden lineal, ¿existiría algún criterio teórico relevante de complejidad para decantarse por ella? Razona la contestación en cuatro o cinco líneas.

Solución: Desde una perspectiva estrictamente asintótica, ambas alternativas poseen una cota superior idéntica: pertenecen a la clase $O(n)$ (o $O(p)$). Por tanto, la tasa de incremento del tiempo de ejecución respecto al tamaño de los datos crecerá al mismo ritmo en los dos casos. Para elegir entre una u otra convendría analizar aspectos ajenos a la complejidad teórica, tales como el consumo de memoria en la pila (overhead de llamadas), la legibilidad o factores de constante multiplicativa oculta.