O(logk) 竞争复杂度的含义
Meaning of O(logk) competitive complexity
我正在研究现有算法以提高其复杂性。现有算法使用K-means聚类，而我选择使用K-means++来聚类。
之所以选择 K-means++，是因为与 K-mean 相比，它的聚类结果更快、更准确。
现在，接近尾声时，我必须比较新算法和现有算法的复杂度，我发现我无法理解 K-means++ 的复杂度为 O(logk) 竞争.
我试着在网上到处寻找解释，包括堆栈溢出。
我唯一理解的是，竞争与 "on-line" 和 "off-line" 算法有关。谁能解释一下它是如何应用在这里的？
您正在阅读的完整句子类似于 "The k-means++ clustering is O(log k)-competitive to the optimal k-means solution"。
这不是关于其算法复杂性的陈述。这是关于其有效性的声明。您可以将 O 表示法用于其他事情。
K-means 尝试最小化 "potential"，该 "potential" 计算为点与其聚类中心的距离平方和。
对于任何特定的聚类问题，K-means++ 解决方案的预期潜力最多是最佳解决方案潜力的 8(ln k + 2) 倍。为简洁起见，8(ln k + 2) 缩短为 O(log k)。
k-means++ 解决方案具有 O(log k) 竞争性这一说法的确切含义是存在一些常数 C 使得 k-means++ 潜力与最佳之间的预期比率对于所有足够大的 k，可能的潜力小于 C*(log k)。
最小的常数约为 8
我正在研究现有算法以提高其复杂性。现有算法使用K-means聚类，而我选择使用K-means++来聚类。
之所以选择 K-means++，是因为与 K-mean 相比，它的聚类结果更快、更准确。
现在，接近尾声时，我必须比较新算法和现有算法的复杂度，我发现我无法理解 K-means++ 的复杂度为 O(logk) 竞争.
我试着在网上到处寻找解释，包括堆栈溢出。
我唯一理解的是，竞争与 "on-line" 和 "off-line" 算法有关。谁能解释一下它是如何应用在这里的？
您正在阅读的完整句子类似于 "The k-means++ clustering is O(log k)-competitive to the optimal k-means solution"。
这不是关于其算法复杂性的陈述。这是关于其有效性的声明。您可以将 O 表示法用于其他事情。
K-means 尝试最小化 "potential"，该 "potential" 计算为点与其聚类中心的距离平方和。
对于任何特定的聚类问题，K-means++ 解决方案的预期潜力最多是最佳解决方案潜力的 8(ln k + 2) 倍。为简洁起见，8(ln k + 2) 缩短为 O(log k)。
k-means++ 解决方案具有 O(log k) 竞争性这一说法的确切含义是存在一些常数 C 使得 k-means++ 潜力与最佳之间的预期比率对于所有足够大的 k，可能的潜力小于 C*(log k)。
最小的常数约为 8