Kmeans clustering is np hard BUT if we try to approximate the solution with coordinate descend then the complexity is O(NKD). Note that the results can depend on the cluster center initialization and the number of iterations.
In practice, we usually run with different initial points.
K-means
what is the complexity of k means?
Is it N-P hard or O(N.K.D) ?
Kmeans clustering is np hard BUT if we try to approximate the solution with coordinate descend then the complexity is O(NKD). Note that the results can depend on the cluster center initialization and the number of iterations.
In practice, we usually run with different initial points.
Add comment