我正在阅读一些关于 ML 和聚类的笔记，它声称聚类的运行时间是 O(kn)，其中 k 是聚类数，n 是点数。

我想知道为什么这是真的，是否有人对此进行了分析。

到目前为止，这是我的想法：

回想一下聚类算法。

1) 初始化质心$z^{(i)}, ..., z^{(k)}$

2）重复以下两个步骤，直到成本没有进一步变化：

a) 对于每个固定质心，选择一个最优聚类，使得点最接近当前质心。$z^{(i)}$$x^{(i)}$

b) 对于固定集群，重新计算当前质心：$z^{(j)} = \frac{\sum_{i \in C_{j}} x^{(i)}}{|C_j|}$

我们知道，由于收敛证明，聚类不会永远运行。所以它不会永远运行。现在，步骤 a) 采用 O(kn) 最坏情况，因为对于每个质心，我们必须计算到每个数据点$z^{(i)}$$x^{i}$并选择最小值并将其分配给该集群，在最坏的情况下，我们会执行 O(n) 来计算每个质心 k 的最小值。所以 O(kn) （我知道我们可以使用堆或其他什么，这不是我感兴趣的）。现在在下一步中，我们计算最坏情况下 O(k+n) 小于 O(kn) 的新均值，因此步骤 b) 对运行时没有任何实际贡献。但是，基本上......我们怎么知道它不会继续这样做很多次？注释如何暗示它收敛于 O(1)。那部分我不清楚。如果其他人清楚，请随时启发我！