1）KMEANS的时间复杂度

正如这篇文章中所解释的：

KMeans 是一个 NP-hard 问题。但是，对于（d 维）点，运行标准算法的固定次数迭代仅需要是质心（或簇）的数量。这就是实际实现所做的（通常在迭代之间随机重新启动）。$t$$O(t*k*n*d)$$n$$k$

2）你什么时候会使用其中一个？

正如这篇 Wikipedia 文章中提到的，K-medoids 对异常值和噪声不太敏感，因为它最小化了函数。

与 k-means 相比，它对噪声和异常值更稳健，因为它最小化了成对差异的总和，而不是平方欧几里得距离的总和。

此外，K-medoids 可以使用各种相似性度量，其中 K-means 仅限于欧几里得（成对）距离。很好的解释[这里]。（https://stats.stackexchange.com/a/81496/279276）

3) 使用 k-medoids 需要哪些品质？

只要欧几里德距离在您的数据中没有意义，我建议您使用它。如果欧几里得距离没有意义（即不相关的分类变量：“有翅膀”、“腿数”），那么最小化欧几里得距离的平方和可能也不会。

4）输出有什么不同

主要区别在于中心点（相当于 K-Means 中的质心）属于数据点。你永远不会有一个介于两点之间的中心点。相反，它将叠加在现有点上。这篇文章清楚地表明了这一点。

这是有道理的，特别是对于分类特征（腿数），集群中心不在 3.347 腿上。

希望这可以帮助。