Complejidad problema

[Chumi-Colores]

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

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

¿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]

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]

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]

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

[Chumi-Colores]

yap, muchas gracias