search

darroyue / IIC2283

25 stars 0 forks source link

Complejidad problema #2

Open Chumi-Colores opened 11 months ago

Chumi-Colores commented 11 months ago

En el enunciado sale que el índice de similitud se calcula así imagen

Entonces se tendrían que hacer n(n-1)/2 operaciones F. Lo que haría que el problema tuviera una complejidad intrínseca mínima de O(n^2). Sin embargo se nos pide una complejidad distinta de esa imagen

¿Es esto un error? ¿O existe alguna forma de comparar cada par de string entre ellos menos de n(n-1)/2 veces?

mc-cari commented 11 months ago

Hola @Chumi-sun,

No hay error en la complejidad. El índice de similitud es la 'cantidad de pares de secuencias distintas que cumplen la relación ≈', la fórmula solo es una de las formas de calcularla.

Chumi-Colores commented 11 months ago

Muchas gracias por la aclaración.

Entonces para estar seguro, la complejidad no se refiere a la operación F, sino al cálculo del índice total?

mc-cari commented 11 months ago

Es la complejidad es sobre el código que entregas en la tarea, no sobre una parte en particular.

Chumi-Colores commented 11 months ago

yap, muchas gracias