我正在阅读这篇论文 Product quantization for nearest neighbor search .
在表 II 第 5 页的最后一行，它给出了
the complexity given in this table for searching the k smallest elements is the average complexity for n >> k and when the elements are arbitrarily ordered
这是 n+klogkloglogn。
我想我们可以使用线性选择算法以 O(n) 得到未排序的 k 个最近邻居，然后用 O(klogk) 对 k 个最近邻居进行排序，所以我们总共可以有 O(n+klogk) 吗？但是 loglogn 术语从何而来？
论文中为此引用了 TAOCP 书，但我手头没有这本书，谁能帮我解释一下？
最佳答案
首先，表 II 报告了每个步骤的复杂性，因此您必须添加所有项才能衡量 ADC 的复杂性。
表的最后一行是SDC和ADC的单一复杂度，即:
n + k log k log log n
该术语对应于我们用来在一组 n 个变量中找到 k 个最小值的选择算法的平均算法成本，我们从 Donald Knuth 的书 [25] 中复制/粘贴了这些值。
我手上没有这本书，无法核对，但听起来不错。
来自作者
关于algorithm - 近似最近邻时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37803181/