¿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 … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 1 – Part 1»
Deje que w(n) y A(n) denoten respectivamente, el peor caso y el tiempo promedio de ejecución de un algoritmo ejecutado en una entrada de tamaño n. ¿Cuál de las siguientes es SIEMPRE CIERTA? (GATE CS 2012) (A) (B) (C) (D) (A) A (B) B (C) C (D) D Respuesta: (C) Explicación: La complejidad del tiempo … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 4»
En una competición se observan cuatro funciones diferentes. Todas las funciones usan un solo bucle for y dentro del bucle for, se ejecuta el mismo conjunto de declaraciones. Considere lo siguiente para bucles: A) for(i = 0; i < n; i++) B) for(i = 0; i < n; i += 2) C) for(i … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 9»
Considere el siguiente fragmento de programa para invertir los dígitos en un entero dado para obtener un nuevo entero. Sea n = D1D2…Dm int n, rev; rev = 0; while (n > 0) { rev = rev*10 + n%10; n = n/10; } La condición invariable del ciclo al final de la i-ésima iteración es: … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 19»
¿Cuál es la complejidad temporal de fun()? int fun(int n) { int count = 0; for (int i = 0; i < n; i++) for (int j = i; j > 0; j–) count = count + 1; return count; } (A) Theta (n) (B) Theta (n^2) (C) Theta (n*Logn) (D) Theta (nLognLogn) Respuesta: (B) … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 2»
Considere las siguientes dos funciones. ¿Cuáles son las complejidades temporales de las funciones? int fun1(int n) { if (n <= 1) return n; return 2*fun1(n-1); } int fun2(int n) { if (n <= 1) return n; return fun2(n-1) + fun2(n-1); } (A) O(2^n) para fun1() y fun2() (B) O(n) para fun1() y O(2^n) para fun2() … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 19 – Part 1»
Considere las siguientes funciones: f(n) = 2^n g(n) = n! h(n) = n^logn ¿Cuál de las siguientes afirmaciones sobre el comportamiento asintótico de f(n), g(n) y h(n) es verdadera? (A) f(n) = O(g(n)); g(n) = O(h(n)) (B) f(n) = (g(n)); g(n) = O(h(n)) (C) g(n) = O(f(n)); h(n) = O(f(n)) (D) h(n) = O(f(n)); g(n) … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 13»
La relación de recurrencia que captura el tiempo óptimo del problema de la Torre de Hanoi con n discos es. (GATE CS 2012) (A) T(n) = 2T(n – 2) + 2 (B) T(n) = 2T(n – 1) + n (C) T(n) = 2T(n/2) + 1 (D) T(n) = 2T(n – 1) + 1 Respuesta: (D) … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 3»
En la siguiente función C, sea n >= m. int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m, n); } ¿Cuántas llamadas recursivas realiza esta función? (A) (logn) (B) (n) (C) (loglogn) (D) (sqrt(n)) (A) A (B) B (C) C (D) D Respuesta: (A) Explicación: El código anterior es la implementación … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 14»
Considere las siguientes tres afirmaciones I (n + k)^m = (n^m), donde k y m son constantes II 2^(n + 1) = 0(2^n) III 2^(2n + 1) = 0(2^n) ¿Cuáles de estas afirmaciones son correctas? (PUERTA CS 2003) (A) I y II (B) I y III (C) II y III (D) I, II y III … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 16»