¿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»