PED Parcial 1 Repaso Complejidad
COMENTARIOS |
ESTADÍSTICAS |
RÉCORDS
|
Título del Test: PED Parcial 1 Repaso Complejidad Descripción: PED Parcial 1 Repaso Complejidad |
Nuevo Comentario| Comentarios |
|---|
NO HAY REGISTROS |
|
El algoritmo de búsqueda binaria estudiado en clase (búsqueda de un elemento en un vector ordenado) tiene una complejidad de O(log2n). Verdadero. Falso. El algoritmo de intercambio directo o burbuja estudiado en clase (ordenación de los elementos de un vector) tiene una complejidad de Ω(n2), siendo n el número de elementos del vector. Verdadero. Falso. El resultado del cálculo de la complejidad temporal en el mejor caso de un algoritmo X, da como resultado n + n*log(n). Por lo tanto, diremos que la complejidad del algoritmo X cuando n → ∞ pertenece a Ω (n). Verdadero. Falso. En la escala de complejidades se cumple que: O(log n) ⊂ O(log log n). Verdadero. Falso. La complejidad espacial es la cantidad de recursos espaciales que un algoritmo consume o necesita para su ejecución. Verdadero. Falso. La complejidad temporal del siguiente fragmento de código es O(n) int i, j, n, sum; for (i = 4; i < n; i++) { for (j = i–3, sum = a[i-4]; j <= i; j++) sum += a[j]; cout << “La suma del subarray “ << i-4 << “ es “ << sum << endl; }. Verdadero. Falso. La complejidad temporal (en su caso peor) del siguiente fragmento de código es O(n2 ) int i, j, n, sum; for (i = 4; i < n; i++) { for (j = i–3, sum = a[i-4]; j <= i; j++) sum += a[j]; cout << “La suma del subarray “ << i-4 << “ es “ << sum << endl; }. Verdadero. Falso. LA COTA PROMEDIO DE COMPLEJIDAD ES EL RESULTADO DE HACER LA MEDIA ENTRE LA COTA SUPERIOR Y LA COTA INFERIOR. Verdadero. Falso. Si la complejidad temporal de un algoritmo en el mejor caso es lineal y en el peor caso es lineal, podemos decir que la complejidad promedio es lineal. Verdadero. Falso. El algoritmo de búsqueda binaria estudiado en clase (búsqueda de un elemento en un vector ordenado) tiene una complejidad de Ω(1). Verdadero. Falso. El algoritmo de intercambio directo o burbuja estudiado en clase (ordenación de los elementos de un vector) tiene una complejidad promedio de Θ(n2), siendo n el número de elementos del vector. Verdadero. Falso. En la escala de complejidades, la mejor complejidad temporal que se puede conseguir en un algoritmo es O(n), siendo “n” la talla del problema. Verdadero. Falso. En la escala de complejidades se cumple que O(n log n) ⊂ O(n2). Verdadero. Falso. La complejidad temporal de un algoritmo depende de la complejidad espacial del mismo. Verdadero. Falso. La complejidad temporal (en su caso mejor) del siguiente fragmento de código es Ω(n) int i, length, n, i1, i2, k; for (i = 0, length = 1; i < n-1; i++) { for (i1 = i2 = k = i; k < n-1 && a[k] < a[k+1]; k++, i2++); if (length < i2 – i1 + 1) length = i2 – i1 + 1; }. Verdadero. Falso. La complejidad temporal en su caso promedio del algoritmo de ordenación de intercambio directo (burbuja) visto en clase es Θ(n2). Verdadero. Falso. La mejor complejidad temporal que se puede conseguir en un algoritmo es O(n), siendo “n” la talla del problema. Verdadero. Falso. |