search

PUC-IIC2283 / 2020-IIC2283-Pruebas

Repositorio del curso Diseño y Análisis de Algoritmos 2020. Foro de interrogaciones y examen en Issues.
1 stars 0 forks source link

[i1-P3] Complejidad #11

Open jvlara opened 3 years ago

jvlara commented 3 years ago

Se pide complejidad polinomial en el tamaño de entrada w1+w2, ¿sirve si dejo expresado la complejidad por w1*w2?

marceloarenassaavedra commented 3 years ago

No, se pide la complejidad expresada como función de |w_1|+|w_2|.

Para demostrar que el algoritmo funciona en tiempo polinomial basta con usar la notacion O( ).

Saludos!

beayancan commented 3 years ago

Si entendí bien, entonces ¿ algo como O( (|w_1|+|w_2|)^2 ) serviría ?

Además, como lo vimos en clases el calculo de ed es con programación dinamica ¿tambien debe ser implementado en el seudo codigo o lo damos por hecho?

marceloarenassaavedra commented 3 years ago

Necesitas una expresión de la forma (|w_1| + |w_2|)^k que acote el tiempo de funcionamiento de tu algoritmo.

No es necesario calcular ed(w_1,w_2) para resolver esta pregunta. Pero si tu algoritmo lo necesita, entonces lo tienes que implementar.

Saludos!