algorithm - k-means的时间复杂度是多少？

Question

我正在浏览k-means 维基百科页面。基于算法，​​我认为复杂度是O(n*k*i)（n=总元素，k=集群迭代次数）

那么有人可以向我解释一下来自维基百科的这个声明，这个 NP 有多难？

如果k和d（维度）是固定的，则问题可以及时准确地解决，其中是要聚类的实体数。O(ndk+1 log n)n

Answer 1

这取决于您所说的k均值。

求k-means目标函数的全局最优问题

是 NP-hard，其中是簇（并且有簇），是簇中的维点，是簇的质心（点的平均值）。SiikxjdSiμiSi

然而，运行标准算法的固定次数t的迭代只需要, 对于(-维) 点，其中是质心（或簇）的数量。这就是实际实现所做的（通常在迭代之间随机重新启动）。O(t*k*n*d)ndk

标准算法仅逼近上述函数的局部最优值，我见过的所有k均值算法也是如此。

Answer 2

在这个答案中，请注意，i在 k-means 目标公式中i使用的和在 k-means 的时间复杂度分析中使用的（即，直到收敛所需的迭代次数）是不同的。

Answer 3

问题是 NP-Hard，因为有另一个众所周知的 NP 难题可以简化为（平面）k-means 问题。查看论文The Planar k-means Problem is NP-hard (by Mahajan et al.) 了解更多信息。