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 complejidad ciclomática de una sección de código es la medida cuantitativa del número de caminos linealmente independientes en ella. Es una métrica de software utilizada para indicar la complejidad de un programa. Se calcula utilizando el gráfico de flujo de control del programa. Los Nodes en el gráfico indican el grupo más pequeño de … Continue reading «Complejidad ciclomática»
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 el algoritmo determinista , para una entrada particular dada, la computadora siempre producirá la misma salida pasando por los mismos estados, pero en el caso del algoritmo no determinista , para la misma entrada, el compilador puede producir una salida diferente en diferentes ejecuciones. De hecho, los algoritmos no deterministas no pueden resolver el … Continue reading «Diferencia entre algoritmos deterministas y no deterministas»
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»
En nuestros artículos anteriores sobre Análisis de Algoritmos , habíamos discutido brevemente las notaciones asintóticas, su desempeño en el mejor y el peor de los casos, etc. En este artículo, discutimos el análisis del algoritmo utilizando la notación asintótica Big – O en completo detalle. Análisis Big-O de algoritmos Podemos expresar la complejidad algorítmica usando la … Continue reading «Análisis de Algoritmos | Análisis O grande»
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»
¿Qué es un algoritmo? Conceptos básicos del algoritmo La palabra Algoritmo significa “ Un conjunto de reglas a seguir en los cálculos u otras operaciones de resolución de problemas ” o “ Un procedimiento para resolver un problema matemático en un número finito de pasos que frecuentemente mediante operaciones recursivas ”. Por lo tanto, el … Continue reading «¿Qué es el algoritmo? Introducción a los Algoritmos»
Considere las siguientes funciones ¿Cuál de las siguientes es verdadera? (GATE CS 2000) (a) h(n) es 0(f(n)) (b) h(n) es 0(g(n)) (c) g(n) no es 0(f(n) ) (d) f(n) es 0(g(n)) (A) a (B) b (C) c (D) d Respuesta: (D) Explicación: g(n) = 2^ = n^ f(n) y g(n) son del mismo orden asintótico … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 15»