K-means: differenze tra le versioni

L'algoritmo ha acquistato notorietà dato che converge molto velocemente. Infatti, si è osservato che generalmente il numero di iterazioni sonoè minoriminore del numero di punti. Comunque, l'algoritmo puo' essere molto lento nel caso peggiore: D. Arthur e S. Vassilvitskii hanno mostrato che esistono certi insiemi di punti per i quali l'algoritmo impiega un tempo superpolinomiale, <math>2^{\Omega(\sqrt{n})}</math>, a convergere. Più recentemente, A. Vattani ha migliorato questo risultato mostrando che l'algoritmo puo' impiegare tempo esponenziale, <math>2^{\Omega(n)}</math>, a convergere anche per certi insiemi di punti sul piano. D'altra parte, D. Arthur, B. Manthey e H. Roeglin hanno mostrato che la smoothed complexity dell'algoritmo è polinomiale, la qual cosa e' a supporto del fatto che l'algoritmo è veloce in pratica.