有没有什么情况下你更喜欢O(log n)时间复杂度而不是O(1)时间复杂度?还是O(n)到O(log n)

你能举个例子吗?


当前回答

我在这里的回答是,在随机矩阵的所有行的快速随机加权选择是一个例子,当m不是太大时,复杂度为O(m)的算法比复杂度为O(log(m))的算法更快。

其他回答

假设您正在嵌入式系统上实现一个黑名单,其中0到1,000,000之间的数字可能被列入黑名单。这就给你留下了两个选择:

使用1,000,000位的bitset 使用黑名单整数的排序数组,并使用二进制搜索来访问它们

对bitset的访问将保证常量访问。从时间复杂度来看,它是最优的。从理论和实践的角度来看(它是O(1),常量开销极低)。

不过,你可能更喜欢第二种解决方案。特别是如果您希望黑名单整数的数量非常小,因为这样内存效率更高。

即使您不为内存稀缺的嵌入式系统开发,我也可以将任意限制从1,000,000增加到1,000,000,000,000,并提出相同的论点。那么bitset将需要大约125G的内存。保证最坏情况复杂度为O(1)可能无法说服您的老板为您提供如此强大的服务器。

在这里,我强烈倾向于二叉搜索(O(log n))或二叉树(O(log n))而不是O(1)位集。在实践中,最坏情况复杂度为O(n)的哈希表可能会击败所有这些算法。

人们已经回答了你的确切问题,所以我要回答一个稍微不同的问题,人们来这里时可能会想到这个问题。

许多“O(1)时间”算法和数据结构实际上只需要预期的O(1)时间,这意味着它们的平均运行时间是O(1),可能仅在某些假设下。

常见的例子:哈希表,“数组列表”的扩展(也就是动态大小的数组/向量)。

在这种情况下,您可能更喜欢使用保证时间绝对受对数限制的数据结构或算法,即使它们的平均性能可能更差。 一个例子可能是平衡二叉搜索树,它的运行时间平均较差,但在最坏的情况下更好。

在关注数据安全的上下文中,如果更复杂的算法对定时攻击有更好的抵抗能力,那么更复杂的算法可能比不太复杂的算法更可取。

总有一个隐藏常数,在O(log n)算法中可以更低。因此,在实际生活数据中,它可以更快地工作。

还有空间问题(比如在烤面包机上运行)。

还有开发人员的时间问题——O(log n)可能更容易实现和验证1000倍。

我很惊讶没有人提到内存绑定应用程序。

可能存在一种算法具有较少的浮点运算,这要么是因为它的复杂性(即O(1) < O(log n)),要么是因为复杂度前面的常数更小(即2n2 < 6n2)。无论如何,如果较低的FLOP算法的内存限制更大,您可能仍然更喜欢具有更多FLOP的算法。

我所说的“内存受限”是指您经常访问的数据经常超出缓存。为了获取这些数据,在对其执行操作之前,必须将内存从实际内存空间拉到缓存中。这个抓取步骤通常非常慢——比您的操作本身慢得多。

因此,如果你的算法需要更多的操作(但这些操作是在已经在缓存中的数据上执行的[因此不需要读取]),它仍然会在实际的walltime方面以更少的操作(必须在缓存外的数据上执行[因此需要读取])胜过你的算法。