Los siguientes ejercicios corregidos tratan sobre el análisis de algoritmos, especialmente el cálculo de corrección, integridad y complejidad del tiempo.
Ejercicio 1
Determine la complejidad de tiempo del algoritmo de verificación:
Verifique la exactitud y la integridad, especialmente lo que sucedió durante la primera iteración.
Ejercicio 2
Analizar la complejidad del algoritmo. Escriba otro algoritmo que haga exactamente lo mismo que Algoritmo pero con una complejidad de tiempo asintótica estrictamente mejor.
La complejidad es O (| A | ²). Puede mejorar el algoritmo: primero, ordene la tabla en O (n log n) y luego verifique las ocurrencias en O (n), por lo que la complejidad se convierte en O (n log n).
Ejercicio 3
¿Cuál es el tiempo de ejecución (asintótico) de cada uno de los siguientes algoritmos, en función de n? Justifica tus respuestas.
Para)
para i = 1 an do
para j = 1 a 2n + 1 hacer
print ("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 an ∗ n hacer
para j = 1 para hacer
imprimir ("Hola mundo")
final para
final para
F)
para (i = 0 am) hacer
t ← 1
mientras que (t <m) hacer
print ("Hola mundo")
t ← t ∗ 2
terminar mientras
final para
- a) O (n²)
- Bien)
- c) O (n²)
- d) O (n²)
- e) O (n4)
- f) O (m log (m))
Ejercicio 4
Deje TPARA(n), TB(n) y TVS(n) denotan el tiempo 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, según cada uno de los siguientes conjuntos de suposiciones? Justifica tus 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 despreciar la parte if del enunciado if. Por tanto, en todos los casos, el tiempo de ejecución de este algoritmo es O (TA (n) + nTC (n)).
- a) O (n log n)
- b) O (n²)
- c) O (n²)
Ejercicio 5
¿Cuál es la complejidad del 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 bucle fuera a N en lugar de M?
Un ciclo anidado seguido de un ciclo 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 veces que se ejecuta el bucle interno depende del valor del índice del bucle externo:
- 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). Esto también se puede escribir como O (max (N, M)). En el caso de que el segundo bucle 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 elimina 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 (N2) y el segundo bucle es O (N). Esto es O (max (N2, N)) que es O (N2).
- Esto es muy similar a nuestro ejemplo anterior de un ciclo anidado donde el número de iteraciones del ciclo interno depende del valor del índice del ciclo externo. La única diferencia es que en este ejemplo, el índice de bucle interno está contando hacia atrás desde N hasta i + 1. Sigue siendo cierto 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 instrucciones" más interna es O (N2).
- 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 corresponde aquí 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 necesitan 10 ms para ejecutar el programa (b) para n = 100, ¿cuánto tardará en ejecutarse para n = 400?
- Si se necesitan 10 ms para ejecutar el programa (a) para n = 100, ¿qué tamaño de problema se puede resolver en 40 ms?
A y b en O (sqrt (n)), cyd en O (n ^ 5)
Con producto cruzado: sqrt (100) = xey = 10ms; sqrt (400) = 2x toma 20ms
En 40 ms, a puede ejecutar n = 1600.
ES 
FR 
EN