¿Qué es la complejidad temporal de fun()?
int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
(A) O(n^2)
(B) O(nLogn)
(C) O(n)
(D) O(nLognLogn)
Respuesta: (C)
Explicación: Para un entero de entrada n, la instrucción más interna de fun() se ejecuta las siguientes veces.
n + n/2 + n/4 + … 1
Entonces la complejidad del tiempo T(n) se puede escribir como
T(n) = O(n + n/2 + n/4 + … 1) = O(n)
El valor de cuenta también es n + n/2 + n/4 + .. + 1
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA