我正在阅读这篇论文《用于最近邻搜索的产品量化》.
在第5页的表II的最后一行中，它给出了：
对于搜索k个最小元素，此表中给出的复杂度是n>>k且元素是任意排序时的平均复杂度。
它是n+klogkloglogn。
我猜我们可以使用线性选择算法以O(n)获取未排序的k个最近邻居，并使用O(klogk)对k个最近邻进行排序，所以我们总共可以得到O(n+klogk)。但是，loglogn项从何而来呢？
该论文引用了TAOCP书中的内容，但我手头没有这本书，有人能为我解释一下吗？
近似最近邻时间复杂度
3
- dontloo
3
1个回答
2
首先，表II报告了每个步骤的复杂度，因此您需要添加所有术语来衡量ADC的复杂度。
在表的最后一行，SDC和ADC的单个复杂度相同，即：
n + k log k log log n
该术语对应于我们使用的选择算法的平均算法成本，用于在一组n个变量中找到k个最小值，我们从Donald Knuth的书[25]中复制/粘贴。
我手头没有这本书，所以无法检查，但听起来是正确的。
作者提供
在表的最后一行，SDC和ADC的单个复杂度相同，即：
n + k log k log log n
该术语对应于我们使用的选择算法的平均算法成本，用于在一组n个变量中找到k个最小值，我们从Donald Knuth的书[25]中复制/粘贴。
我手头没有这本书，所以无法检查，但听起来是正确的。
作者提供
- gsamaras
5
谢谢！我不太确定在ADC情况下它是如何变成“loglogn”的，你能解释一下吗？谢谢！ - dontloo
看我的更新@dontloo，那应该足够了，如果你有新的问题，请发布一个新的。 :) - gsamaras
非常感谢您的澄清，这就是我困惑的地方，我只能理解
n + k log k，这是我能得到的最接近此公式的形式。无论如何，谢谢您，我想我会在超出本文档范围的更清晰的问题中发帖。 - dontloo只是想知道你从哪里找到这个的？你联系过作者吗？ - dontloo
正如我在我的回答中所写的，是的 @dontloo! :) - gsamaras
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
n+k log k，而ADC则为log log n。由于列之间太靠近，您可以将它们一起读作n+k log k log log n。 - user31264log log n的时间复杂度对我来说甚至更加没有意义。 - dontloo