复杂度为 O(n/log(n)) 的算法

Question

有这么复杂的著名算法吗？

我在想也许是一个跳跃列表，其中节点的级别不是由抛硬币的反面次数决定的，而是使用从 (1,log(n) ) 期间来确定节点的级别。这样的数据结构将具有复杂度为 O(n/log(n)) 的 find(x) 操作（我认为至少如此）。我很好奇还有没有其他的。

Answer 1

当使用 the method of Four Russians 来加速现有算法。经典的四个俄罗斯人加速将布尔矩阵上的 matrix/vector 乘积的成本从 O(n²) 降低到 O(n² / 日志 n)。用于两个长度为 n 的字符串的序列比对的标准动态规划算法运行时间为 O(n²)，可以减少到 O(n² / log n) 使用类似的技巧。

同样，前缀奇偶校验问题——在支持"flip"和"parity of the prefix of a sequence"操作的同时需要维护一个布尔值序列可以在O(log n / log log n) 通过使用四俄罗斯人加速。 （请注意，如果将运行时间表示为 k = log n 的函数，则为 O(k / log k)。