Dada una array arr[] , la tarea es encontrar la cantidad de elementos de la array cuyos cuadrados ya están presentes en la array. Ejemplos: Entrada: arr[] = {2, 4, 5, 20, 16} Salida: 2 Explicación: {2, 4} tiene sus cuadrados {4, 16} presentes en la array. Entrada: arr[] = {1, 30, 3, 8, 64} … Continue reading «Cuente los elementos de la array cuyos cuadrados perfectos están presentes en la array dada»
¿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»
En el análisis asintótico de algoritmos, a menudo encontramos términos como Big-Oh, Omega, Theta y Tilde, que describen el rendimiento de un algoritmo. Puede consultar los siguientes enlaces para obtener más información sobre el análisis asintótico: Análisis de Algoritmos Notaciones diferentes Diferencia entre Big Oh, Big Omega y Big Theta En este artículo vamos a ver … Continue reading «Diferencia entre notaciones de O grande y tilde»
¿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»