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

你能举个例子吗?


当前回答

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

or

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

其他回答

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

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

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

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

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

简单地说:因为系数(与该步骤的设置、存储和执行时间相关的成本)在较小的大o问题中比在较大的大o问题中要大得多。Big-O只是算法可伸缩性的一个衡量标准。

考虑以下来自黑客词典的例子,提出了一个依赖于量子力学的多重世界解释的排序算法:

用量子过程随机排列数组, 如果数组没有排序,毁灭宇宙。 所有剩下的宇宙现在都被排序了(包括你所在的宇宙)。

(来源:http://catb.org/ esr /术语/ html / B / bogo-sort.html)

注意,这个算法的大O是O(n),它击败了迄今为止在一般项目上的任何已知排序算法。线性阶跃的系数也很低(因为它只是一个比较,而不是交换,是线性完成的)。事实上,类似的算法可以用于在多项式时间内解决NP和co-NP中的任何问题,因为每个可能的解(或没有解的可能证明)都可以使用量子过程生成,然后在多项式时间内验证。

然而,在大多数情况下,我们可能不想冒多重世界可能不正确的风险,更不用说实现步骤2的行为仍然是“留给读者的练习”。

并行执行算法的可能性。

我不知道是否有O(log n)和O(1)类的例子,但对于某些问题,当算法更容易并行执行时,您会选择具有更高复杂度类的算法。

有些算法不能并行化,但复杂度很低。考虑另一种算法,它可以达到相同的结果,并且可以很容易地并行化,但具有更高的复杂度类。当在一台机器上执行时,第二种算法速度较慢,但当在多台机器上执行时,实际执行时间越来越短,而第一种算法无法加快速度。

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