Przechodziłem przezstrona Wikipedii k-means. Na podstawie algorytmu myślę, że złożoność jestO(n*k*i) (n = całkowita liczba elementów,k = liczba iteracji klastra)

Czy więc ktoś może mi wyjaśnić to stwierdzenie z Wikipedii i jak to jest trudne?

Jeślik id (wymiar) są ustalone, problem można dokładnie rozwiązać w czasieO(ndk+1 log n), gdzien to liczba podmiotów, które mają być skupione.