Pregunta 2.d - Análisis de complejidad y eficienc… · Prácticas de programación UOC 2023

Tema: Análisis de complejidad y eficiencia · Del examen Examen Prueba de síntesis enero 2023 (2023)

Enunciado

A partir del siguiente algoritmo codificado en C:

#define MAX 128

int mystery(int v[MAX], int x)

{

int res;

assert(x >= 0 && x < MAX);

if (x == 0) {

if ((v[0] % 2) != 0)

res = v[0];

else

res = 0;

} else {

if ((v[x] % 2) != 0)

res = v[x] + mystery(v, x - 1);

else

res = mystery(v, x - 1);

}

return res;

}

d)

[15%] Obtén la complejidad computacional en notación asintótica de la versión recursiva en el peor de los casos, resolviendo la relación de recurrencia paso a paso.

Enunciado: Pregunta 2.d - Análisis de complejidad y eficienc… · Prácticas de programación UOC 2023

Solución

Según los criterios oficiales de corrección

Resolución de la relación de recurrencia paso a paso.

Solución: En cada nivel de recursión el índice disminuye en una unidad, realizándose un número constante de operaciones elementales. En el peor caso (todos los valores son impares), la función de coste temporal cumple: T(0)=k1T(0) = k_1 T(x)=k2+T(x−1), si x>0T(x) = k_2 + T(x - 1), \text{ si } x > 0 Desplegando la recurrencia tras ii sustituciones: T(x)=k2+T(x−1)=2k2+T(x−2)=⋯=i×k2+T(x−i)T(x) = k_2 + T(x - 1) = 2k_2 + T(x - 2) = \dots = i \times k_2 + T(x - i) El caso base se alcanza cuando x−i=0→i=xx - i = 0 \rightarrow i = x: T(x)=x×k2+T(0)=x×k2+k1T(x) = x \times k_2 + T(0) = x \times k_2 + k_1

Obtén la complejidad computacional en notación asintótica de la versión recursiva en el peor de los casos.

Solución: O(x)O(x)

La explicación paso a paso, hecha con IA, es Premium. Premium

Resuélvelo aquí mismo: corrección automática, pistas y solución paso a paso.

‹ Pregunta 2.d · 2023 · Pregunta 2.d · 2023 ›

Más ejercicios de Análisis de complejidad y eficiencia