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

你能举个例子吗?


当前回答

在n有界且O(1)算法的常数乘子高于log(n)上的界的任意点。例如,在哈希集中存储值是O(1),但可能需要对哈希函数进行昂贵的计算。如果数据项可以简单地进行比较(相对于某些顺序),并且n的边界是这样的,log n明显小于任何一项上的哈希计算,那么存储在平衡二叉树中可能比存储在哈希集中更快。

其他回答

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

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

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

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

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

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

or

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

有很多很好的答案,其中一些提到了常量因素,输入大小和内存限制,以及许多其他原因,复杂性只是一个理论指导原则,而不是最终决定现实世界是否适合给定的目的或速度。

这里有一个简单而具体的例子来说明这些想法。假设我们想要找出一个数组是否有重复的元素。简单的二次型方法是编写一个嵌套循环:

const hasDuplicate = arr => { 对于(设I = 0;I < arrr .length;我+ +){ For(令j = I + 1;J < arrr .length;j + +) { If (arr[i] === arr[j]) { 返回true; } } } 返回错误; }; console.log(hasDuplicate([1,2,3,4])); console.log(hasDuplicate([1,2,4,4]));

但这可以通过创建一组数据结构(即删除重复项),然后将其大小与数组的长度进行比较,在线性时间内完成:

const hasDuplicate = arr => new Set(arr)。== arrr .length; console.log(hasDuplicate([1,2,3,4])); console.log(hasDuplicate([1,2,4,4]));

大O告诉我们,从时间复杂性的角度来看,新的Set方法将更好地扩展。

然而,事实证明,“天真的”二次元方法有很多大O不能解释的:

没有额外的内存占用 没有堆内存分配(没有新的) 临时Set没有垃圾收集 早期的救助;在已知副本可能位于数组前面的情况下,不需要检查多个元素。

如果我们的用例是在有限的小数组上,我们有一个资源受限的环境和/或其他已知的常见情况属性,允许我们通过基准测试建立嵌套循环在特定工作负载上更快,这可能是一个好主意。

另一方面,也许可以预先创建一次集合并重复使用,在所有查找中摊销其开销成本。

这不可避免地导致可维护性/可读性/优雅性和其他“软”成本。在这种情况下,新的Set()方法可能更具可读性,但通常(如果不是更多的话)要获得更好的复杂性需要付出巨大的工程成本。

创建和维护持久的、有状态的Set结构可能会带来bug、内存/缓存压力、代码复杂性和所有其他设计权衡方式。最优地协商这些权衡是软件工程的一个重要部分,而时间复杂性只是帮助指导这个过程的一个因素。


我还没有看到其他一些例子:

In real-time environments, for example resource-constrained embedded systems, sometimes complexity sacrifices are made (typically related to caches and memory or scheduling) to avoid incurring occasional worst-case penalties that can't be tolerated because they might cause jitter. Also in embedded programming, the size of the code itself can cause cache pressure, impacting memory performance. If an algorithm has worse complexity but will result in massive code size savings, that might be a reason to choose it over an algorithm that's theoretically better. In most implementations of recursive linearithmic algorithms like quicksort, when the array is small enough, a quadratic sorting algorithm like insertion sort is often called because the overhead of recursive function calls on increasingly tiny arrays tends to outweigh the cost of nested loops. Insertion sort is also fast on mostly-sorted arrays as the inner loop won't run much. This answer discusses this in an older version of Chrome's V8 engine before they moved to Timsort.

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