K-means: differenze tra le versioni

L'algoritmo ha acquistato notorietà dato che converge molto velocemente: si è osservato infatti che generalmente il numero d'iterazioni è minore del numero di punti. Comunque, l'algoritmo può 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 può 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 è a supporto del fatto che l'algoritmo è veloce in pratica.