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

你能举个例子吗?


当前回答

在实时情况下,当你需要一个固定的上界时,你会选择一个堆排序,而不是快速排序,因为堆排序的平均行为也是它的最差情况行为。

其他回答

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

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

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

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

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

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

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

当O(1)中的“1”工作单元相对于O(log n)中的工作单元非常高,且期望集大小较小时。例如,如果数组中只有两到三个项,那么计算Dictionary哈希码可能比迭代数组要慢。

or

当O(1)算法中的内存或其他非时间资源需求相对于O(log n)算法非常大时。

在重新设计程序时,发现一个过程用O(1)而不是O(lgN)进行了优化,但如果不是这个程序的瓶颈,就很难理解O(1) alg。这样就不用用O(1)算法了 当O(1)需要大量的内存而你无法提供时,而O(lgN)的时间可以接受。

以下是我的观点:

有时,当算法在特定的硬件环境中运行时,会选择较差的复杂度算法来代替较好的算法。假设我们的O(1)算法非顺序地访问一个非常大的固定大小数组的每个元素来解决我们的问题。然后将该阵列放在机械硬盘驱动器或磁带上。

在这种情况下,O(logn)算法(假设它按顺序访问磁盘)变得更有利。