¿Cuál es el valor de la siguiente recurrencia? T(n) = 5T(n/5) + , T(1) = 1, T(0) = 0 (A) Theta (n) (B) Theta (n^2) (C) Theta (sqrt(n)) (D) Theta (nLogn) Respuesta: (A) Explicación: La solución dada se puede resolver usando el método maestro . Cae en el Caso 1. Cuestionario de esta Pregunta Publicación … Continue reading «Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 2»
¿Cuál es el valor de la siguiente recurrencia? T(n) = T(n/4) + T(n/2) + cn2 T(1) = c T(0) = 0 Donde c es una constante positiva (A) O(n 3 ) (B) O(n 2 ) (C) O(n 2 Logn) (D) O(nLogn) Respuesta: (B) Explicación: El siguiente es el árbol de recurrencia inicial para la relación … Continue reading «Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 1»
¿Cuál es la complejidad temporal en el peor de los casos de la siguiente implementación del problema de suma de subconjuntos? // Returns true if there is a subset of set[] with sun equal to given sum bool isSubsetSum(int set[], int n, int sum) { // Base Cases if (sum == 0) return true; if … Continue reading «Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 3»
¿Cuál es la complejidad temporal de la siguiente función recursiva: int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor(sqrt(n))) + n); } (A) (n) (B) (nlogn) (C) (logn) (D) (loglogn) (A) A (B) B (C) C (D) D Respuesta: (D) Explicación: Relación recursiva para el HacerAlgo() es T(n) = … Continue reading «Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 8»
Considere la siguiente recurrencia. T(n) = T( ) + ¿Cuál es el valor de la recurrencia? (A) (B) (B) (B) (A) A (B) B (C) C (D) D Respuesta: (A) Explicación: Cambio de variables: sea m = lg n. La recurrencia se convierte en S(m) = S(m/2) + theta(lgm). Se aplica el caso 2 del … Continue reading «Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 11»
Supongamos que T(n) = 2T(n/2) + n, T(0) = T(1) = 1 ¿ Cuál de las siguientes es falsa? (GATE CS 2005) a) T(n) = O(n^2) b) T(n) = (nLogn) c) T(n) = (n^2) d) T(n) = O(nLogn ) (A) A (B) B (C) C (D) D Respuesta: (C) Explicación: consulte la pregunta 4 de … Continue reading «Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 4»
La complejidad temporal de la siguiente función C es (suponga que n > 0 (GATE CS 2004) int recursive (mt n) { if (n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); } (A) 0(n) (B) 0(nlogn) (C) 0(n^2) (D) 0(2^n) Respuesta: (D) Explicación: La expresión recursiva para el programa anterior será. … Continue reading «Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 9»
Considere la siguiente recurrencia: ¿Cuál de las siguientes es verdadera? (A) T(n) = (loglogn) (B) T(n) = (logn) (C) T(n) = (raíz cuadrada(n)) (D) T(n) = (n) (A) A (B) B (C) C (D) D Respuesta: (B) Explicación: Esta pregunta se puede resolver primero cambiando la variable y luego el Método Maestro. Let n = … Continue reading «Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 11 – Part 1»
El tiempo de ejecución del siguiente algoritmo Procedure A(n) If n <= 2 return(1) else return A(); se describe mejor mediante (A) O(n) (B) O(log n) (C) O(1og log n) (D) O(1) Respuesta: (C) Explicación: Para obtener una explicación, consulte la pregunta 5 de esta publicación Cuestionario de esta pregunta Publicación traducida automáticamente Artículo escrito … Continue reading «Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 7»
El tiempo de ejecución de un algoritmo está representado por la siguiente relación de recurrencia: if n <= 3 then T(n) = n else T(n) = T(n/3) + cn ¿Cuál de los siguientes representa la complejidad temporal del algoritmo? (A) (n) (B) (n log n) (C) (n^2) (D) (n^2log n) (A) A (B) B (C) … Continue reading «Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 6»