Estaba pasando por elpágina de Wikipedia k-means. Basado en el algoritmo, creo que la complejidad esO(n*k*i) (n = elementos totales,k = número de iteración del cluster)

Entonces, ¿puede alguien explicarme esta declaración de Wikipedia y en qué se dificulta este NP?

Sik yd (la dimensión) es fija, el problema puede resolverse exactamente en el tiempoO(ndk+1 log n), dónden es el número de entidades a agrupar.