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»
¿Qué significa cuando decimos que un algoritmo X es asintóticamente más eficiente que Y? (A) X será una mejor opción para todas las entradas (B) X será una mejor opción para todas las entradas excepto posiblemente las entradas pequeñas (C) X será una mejor opción para todas las entradas excepto posiblemente las entradas grandes (D) … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 11»
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 de las opciones dadas proporciona el orden creciente de complejidad asintótica de las funciones f1, f2, f3 y f4? f1(n) = 2^n f2(n) = n^(3/2) f3(n) = nLogn f4(n) = n^(Logn) (A) f3, f2, f4, f1 (B) f3, f2, f1, f4 (C) f2, f3, f1, f4 (D) f2, f3, f4, f1 Respuesta: (A) Explicación: … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 19 – Part 2»
¿Cuál es la complejidad temporal del algoritmo de Floyd-Warshall para calcular el camino más corto de todos los pares en un gráfico con n vértices? (A) O(n^2logn) (B) Theta(n^2logn) (C) Theta(n^4) (D) Theta(n^3) Respuesta: (D) Explicación: el algoritmo de Floyd-Warshall utiliza tres bucles para calcular la ruta más corta de todos los pares. Entonces, la … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 12»
Considere la siguiente función int unknown(int n) { int i, j, k = 0; for (i = n/2; i <= n; i++) for (j = 2; j <= n; j = j * 2) k = k + n/2; return k; } ¿Cuál es el valor de retorno de la función? (PUERTA CS 2013) (A) … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 18»
¿Cuál es la complejidad temporal de la siguiente función? void fun(int n, int arr[]) { int i = 0, j = 0; for(; i < n; ++i) while(j < n && arr[i] < arr[j]) j++; } (A) O(n) (B) O(n^2) (C) O(nlogn) (D) O(n(logn)^2) Respuesta: (A) Explicación: A primera vista, la complejidad del tiempo parece … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 8»
La siguiente afirmación es válida. registro(n!) = (n registro n). (A) Verdadero (B) Falso Respuesta: (A) Explicación: El orden de crecimiento de y es el mismo para valores grandes de , es decir, . Entonces, la complejidad temporal de fun() es . La expresión se puede derivar fácilmente siguiendo la aproximación de Stirling (o la … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 10»
¿Cuál de los siguientes no es O(n^2)? (A) (15^10) * n + 12099 (B) n^1.98 (C) n^3 / (sqrt(n)) (D) (2^20) * n Respuesta: (C) Explicación: El orden de crecimiento de la opción c es n 2.5 que es mayor que n 2 . Cuestionario de esta pregunta Publicación traducida automáticamente Artículo escrito por GeeksforGeeks-1 … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 5»
Sea s una array ordenada de n enteros. Sea t(n) el tiempo que tarda el algoritmo más eficiente en determinar si hay dos elementos con una suma menor que 1000 en s. ¿Cuál de las siguientes afirmaciones es verdadera? (GATE CS 2000) a) t (n) es 0 (1) b) n < t (n) < n … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 17»