Prerrequisito: Análisis de Algoritmos | Análisis O grande En el artículo anterior , se discute el análisis del algoritmo utilizando la notación asintótica Big O. En este artículo, se discuten algunos ejemplos para ilustrar la notación de complejidad de tiempo de Big O y también aprender a calcular la complejidad de tiempo de cualquier programa. … Continue reading «Ejemplos de análisis Big-O»
¿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»
Una relación de recurrencia es una ecuación que define recursivamente una secuencia o array multidimensional de valores, una vez que se dan uno o más términos iniciales; cada término adicional de la secuencia o array se define como una función de los términos anteriores. A continuación se muestran los pasos necesarios para resolver una ecuación … Continue reading «Resolviendo Ecuaciones de Recurrencia Homogéneas Usando Reducción de Polinomios»
El método del árbol de recurrencia es una forma de resolver las relaciones de recurrencia . En este método, una relación de recurrencia se convierte en árboles recursivos. Cada Node representa el costo incurrido en varios niveles de recursividad. Para encontrar el costo total, se suman los costos de todos los niveles. Pasos para resolver … Continue reading «¿Cómo resolver las relaciones de recurrencia de la complejidad del tiempo usando el método de árbol de recursión?»
¿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»