问题描述
是否有这么复杂的著名算法?
Are there any famous algorithms with this complexity?
我在想一个跳过列表,其中节点的级别不是由掷尾硬币的数量决定的,而是使用随机生成的数字(具有均匀分布) )从(1,log(n))期间确定节点的级别。这样的数据结构将具有find(x)操作,其复杂度为O(n / log(n))(至少我认为)。我很好奇是否还有其他内容。
I was thinking maybe a skip list where levels of the nodes are not determined by the number of tails coin tosses, but instead are use a number generated randomly (with uniform distribution) from the (1,log(n)) period to determine the level of the node. Such a data structure would have a find(x) operation with the complexity of O(n/log(n)) (I think, at least). I was curious whether there was anything else.
推荐答案
通常会看到运行时格式为O(n / log n)或O(log n / log log n),当使用加快了现有算法的速度。经典的四位俄罗斯人加速将在布尔矩阵上执行矩阵/矢量乘积的成本从O(n )降低到O(n / log n)。用于在两个长度为n的字符串上进行序列比对的标准动态编程算法的运行时间为O(n ),时间可以减小为O(n / log n)
It's common to see algorithms whose runtime is of the form O(n / log n) or O(log n / log log n) when using the method of Four Russians to speed up an existing algorithm. The classic Four Russians speedup reduces the cost of doing a matrix/vector product on Boolean matrices from O(n) to O(n / log n). The standard dynamic programming algorithm for sequence alignment on two length-n strings runs in time O(n), which can be decreased to O(n / log n) by using a similar trick.
类似地,前缀奇偶校验问题-您需要在支持翻转和奇偶校验的同时保持布尔值序列序列前缀操作可以通过使用四俄语加速来在时间O(log n / log log n)中解决。 (请注意,如果将运行时表示为k = log n的函数,则为O(k / log k)。
Similarly, the prefix parity problem - in which you need to maintain a sequence of Boolean values while supporting the "flip" and "parity of the prefix of a sequence" operations can be solved in time O(log n / log log n) by using a Four-Russians speedup. (Notice that if you express the runtime as a function of k = log n, this is O(k / log k).
这篇关于O(n / log(n))复杂度的算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!