Although finding an exact solution to the k-means problem for arbitrary input is NP-hard, the standard approach to finding an approximate solution (often called Lloyd's algorithm or the k-means algorithm) is used widely and frequently finds reasonable solutions quickly.
Iako je pronalaženje tačnog rešenja za k-means problem za proizvoljani ulaz NP-težak, standardni pristup pronalaženja približnog rešenja (često nazvan Lojdov algoritam ili k-means algoritam) je u širokoj upotrebi i često brzo nađe razumljiva rešenja.