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

你能举个例子吗?


当前回答

假设您正在嵌入式系统上实现一个黑名单,其中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(log n)算法中可以更低。因此,在实际生活数据中,它可以更快地工作。

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

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

并行执行算法的可能性。

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

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

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

以下是我的观点:

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

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