Ejercicio 1
Determine la complejidad temporal del algoritmo Check:
Antes de calcular la complejidad, se debe verificar si el algoritmo termina. Los elementos de la matriz son números enteros, por lo que pueden exceder el valor de 9, lo que significa que tab[value-1] cae fuera del tamaño de la matriz. Por lo tanto, el algoritmo no es viable e inútil para continuar con el análisis.
Ejercicio 2
Analizar la complejidad del algoritmo. escribe otro algoritmo que hace exactamente lo mismo que Algorithm pero con una complejidad de tiempo asintótica estrictamente mejor.
El algoritmo es realmente complicado de entender. La forma más sencilla es probar su funcionamiento con un vector pequeño como <3, 5, 4, 4, 5, 7>. Te dejo probar paso a paso en papel.
En el ciclo, cuando dos cajas son idénticas, incrementamos el valor de c. Dado el contenido secuencial del ciclo, i permanece estable mientras j evoluciona. Entonces contamos el número de ocurrencias en la tabla del valor del cuadro i. La segunda rama da una condición cuando j alcanza una especie del tamaño del vector. En este caso, se verifica que el número de ocurrencias del valor de la casilla i supera el último cómputo registrado en m. Luego incrementamos i y colocamos j en el mismo cuadro.
Esto no cambia la operación de encontrar el número de ocurrencias de cada casilla porque si el valor era anterior, ya se ha contado en su totalidad. Precisamente, comenzar i y j en el mismo lugar produce menos cálculo.
Si retomamos la operación, i y j están en la misma casilla. j se incrementa hasta el final de la matriz. Luego avanzo un espacio y me muevo al mismo lugar. Por lo tanto, el número de iteraciones es la suma de n (tamaño de la matriz) a 1, es decir, n(n-1)/2. Ambas ramas tienen la misma complejidad en 0(1), por lo que la complejidad del algoritmo es O(n²).
Para simplificarlo, basta con realizar el algoritmo en dos etapas. Primero, ordenamos la tabla (posible en O(n log(n)). Luego leemos la tabla en dos casillas tab[i] y tab[i+1]. Siempre que los valores sean iguales, incrementamos un contador c. Si es diferente, buscamos si c>m como el algoritmo propuesto. La complejidad es por lo tanto O(n log(n) + n), o bien O(n log(n)).
Ejercicio 3
Completa las dos tablas siguientes:
Ejercicio 4
¿Cuál es el tiempo de ejecución (asintótico) de cada uno de los siguientes algoritmos, en función de n? Justifique sus respuestas.
Para)
para i = 1 an do
para j = 1 a 2n + 1 hacer
imprimir (“Hola mundo”)
final para
final para
B)
para i = 1 a 10 hacer
para j = 1 an hacer
imprimir (“Hola mundo”)
final para
final para
vs)
para i = 1 an do
para j = yo an hacer
imprimir (“Hola mundo”)
final para
final para
D)
para i = 1 an do
para j = 1 a 2 ∗ i + 1 hacer
imprimir (“Hola mundo”)
final para
final para
mi)
para i = 1 a n ∗ n hacer
para j = 1 para hacer
imprimir (“Hola mundo”)
final para
final para
F)
para i = 0 a m hacer
t ← 1
mientras que (t <m) hacer
imprimir (“Hola mundo”)
t ← t ∗ 2
terminar mientras
final para
a) O(n²). Aquí el primer bucle hace (n-1) iteraciones y el segundo bucle 2n iteraciones, por lo que un total de (n-1)*2n.
Bien). Aquí el primer ciclo hace 10 iteraciones y el segundo ciclo n iteraciones, por lo que un total de 10n. Atención, según cierto cálculo que haría 9 iteraciones seguidas de n-1 iteraciones. Afortunadamente, en el notación Landau no cambia nada, ¡así que no hay necesidad de discutir sobre el número de iteraciones!
c) O(n²). Muy clásico, cada ciclo hace n-1 iteraciones.
d) O(n²). El primer ciclo es clásico. El segundo va de 1 a 2i+1, así que si hacemos algunos ejemplos: 3, 5, 7, …, 2n+1 (aquí ejecutamos los dos bucles al mismo tiempo). Tenemos por tanto la suma de los primeros n términos impares, por tanto cuadrática.
También es posible calcular la complejidad multiplicando la complejidad de cada uno de los bucles. El primer ciclo tiende a n iteraciones cuando n es grande; el segundo ciclo tiende a n iteraciones cuando n es grande. Entonces tenemos una complejidad de O(n*n)=O(n²).
Tenga cuidado de comprobar el número de iteraciones cuando n es grande, ¡no siempre estará en O(n)!
e) O(n^4). La reflexión es la misma que para el algoritmo d. Aquí tenemos los primeros n términos elevados al cuadrado.
f) O(m log(m)). Para el primer bucle todo está bien, el problema vendrá del segundo. Aquí el valor de t se duplica en cada iteración y el ciclo se detiene cuando t excede el valor de m. Sea k el número de iteraciones realizadas. Nos detenemos cuando 2^k >m entonces cuando k > log(m). De ahí la complejidad.
Ejercicio 5
Sea TPARA(n), TB(n) y TVS(n) los tiempos de ejecución de los algoritmos A, B y C, respectivamente.
Instrucción A
si (n <100) entonces
Instrucción B
demás
para (j = 1 an) hacer
Instrucción C
final para
terminara si
¿Cuál es el tiempo de ejecución de este algoritmo, bajo cada uno de los siguientes conjuntos de suposiciones? Justifique sus respuestas.
- TPARA(n) = O (n), TB(n) = O (n2) y TVS(n) = O (log n).
- TPARA(n) = O (n2), TB(n) = O (n2) y TVS(n) = O (log n).
- TPARA(n) = O (n2), TB(n) = O (n3) y TVS(n) = O (log n).
Dado que los valores grandes de n determinan el tiempo de ejecución asintótico, podemos ignorar la parte if de la declaración if. Por tanto, en todos los casos, el tiempo de ejecución de este algoritmo es O(TA(n) + nTC(n)).
- O (n log n)
- O(n²)
- O(n²)
Si tienes dudas, también puedes usar la fórmula clásica en el caso de ramificar 0(max(T_branches)). En este caso, tendríamos O(TA(n) + max(TC(n), nTC(n)) ).
Ejercicio 6
¿Cuál es la complejidad en el peor de los casos de cada uno de los siguientes fragmentos de código?
Dos bucles seguidos:
- para (i = 0; i <N; i ++) {
- secuencia de declaraciones}
- para (j = 0; j <M; j ++) {
- secuencia de declaraciones}
¿Cómo cambiaría la complejidad si el segundo ciclo fuera a N en lugar de a M?
Un bucle anidado seguido de un bucle no anidado:
- para (i = 0; i <N; i ++) {
- para (j = 0; j <N; j ++) {
- secuencia de declaraciones
- }}
- para (k = 0; k <N; k ++) {
- secuencia de declaraciones}
Un bucle anidado en el que el número de ejecuciones del bucle interior depende del valor del índice del bucle exterior:
- para (i = 0; i <N; i ++) {
- para (j = N; j > i; j–) {
- secuencia de declaraciones
- }}
- El primer bucle es O(N) y el segundo bucle es O(M). Como no sabes cuál es más grande, dices que es O(N+M). También se puede escribir O(max(N,M)). En el caso de que el segundo ciclo vaya a N en lugar de M, la complejidad es O(N). Puede ver esto en cualquiera de las expresiones anteriores. O(N+M) se convierte en O(2N) y cuando quitas la constante es O(N). O(max(N,M)) se convierte en O(max(N,N)) que es O(N).
- El primer conjunto de bucles anidados es O(N²) y el segundo bucle es O(N). Es O(N²+N) que es O(N²).
- Esto es muy similar a nuestro ejemplo anterior de un ciclo anidado donde el número de iteraciones del ciclo interno depende del valor de índice del ciclo externo. La única diferencia es que, en este ejemplo, el índice del bucle interno cuenta hacia atrás desde N hasta i+1. Siempre ocurre que el ciclo interno se ejecuta N veces, luego N-1, luego N-2, etc., por lo que el número total de veces que se ejecuta la "secuencia de instrucción" más interna es O(N²).
Ejercicio 7
Proporcione un análisis del tiempo de ejecución (notación Big-Oh) para cada uno de los siguientes 4 fragmentos de programa. Tenga en cuenta que el tiempo de ejecución aquí corresponde al número de veces que se ejecuta la operación sum++. sqrt es la función que devuelve la raíz cuadrada de un número dado.
- Si se tarda 10 ms en ejecutar el programa (b) para n=100, ¿cuánto tiempo se tardará en ejecutar n=400?
- Si se tarda 10 ms en ejecutar el programa (a) para n = 100, ¿qué tamaño de problema se puede resolver en 40 ms?
A está en O(sqrt(n)) es una secuencia secuencial de bucles, tenemos 0(sqrt(n)/2 + sqrt(n)/4 + sqrt(n)/4 +8)
B no termina, ¡el segundo bucle no está bien escrito! Teniendo en cuenta el bucle escrito correctamente, habríamos tenido tres bucles interdependientes acotados en 0(sqrt(n)), 0(1) y O(1) — de i a i+8; de d a d+8 que hace solo 8 iteraciones. Que es 0 (raíz cuadrada (n)).
c está en O(n^5). Tres bucles anidados de complejidad respectiva 0(n), 0(n²), 0(n²) por lo tanto 0(n*n²*n²).
d tiene una condición de bifurcación que no es válida porque no devuelve un booleano, el algoritmo no termina, por lo que no es necesario calcular la complejidad.
Con producto cruzado: sqrt(100)=xey=10 ms; sqrt(400)=2x toma 20ms
En 40ms, n=1600.
ES 
FR 
EN