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

你能举个例子吗?


当前回答

考虑一个红黑树。它具有O(log n)的访问、搜索、插入和删除操作。与数组相比,数组的访问权限为O(1),其余操作为O(n)。

因此,对于一个插入、删除或搜索比访问更频繁的应用程序,并且只能在这两种结构之间进行选择,我们更喜欢红黑树。在这种情况下,你可能会说我们更喜欢红黑树更麻烦的O(log n)访问时间。

为什么?因为权限不是我们最关心的。我们正在权衡:应用程序的性能更大程度上受到其他因素的影响。我们允许这种特定的算法受到性能影响,因为我们通过优化其他算法获得了很大的收益。

So the answer to your question is simply this: when the algorithm's growth rate isn't what we want to optimize, when we want to optimize something else. All of the other answers are special cases of this. Sometimes we optimize the run time of other operations. Sometimes we optimize for memory. Sometimes we optimize for security. Sometimes we optimize maintainability. Sometimes we optimize for development time. Even the overriding constant being low enough to matter is optimizing for run time when you know the growth rate of the algorithm isn't the greatest impact on run time. (If your data set was outside this range, you would optimize for the growth rate of the algorithm because it would eventually dominate the constant.) Everything has a cost, and in many cases, we trade the cost of a higher growth rate for the algorithm to optimize something else.

其他回答

并行执行算法的可能性。

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

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

Alistra指出了这一点,但未能提供任何例子,所以我会。

您有一个包含10,000个UPC代码的列表,用于您的商店销售的产品。10位UPC,整数价格(便士价格)和30个字符的收据描述。

O(log N)方法:你有一个排序的列表。ASCII是44字节,Unicode是84字节。或者,将UPC视为int64,将得到42和72字节。10,000条记录——在最高的情况下,您看到的存储空间略低于1mb。

O(1)方法:不存储UPC,而是将其用作数组的一个条目。在最低的情况下,您将看到近三分之一tb的存储空间。

Which approach you use depends on your hardware. On most any reasonable modern configuration you're going to use the log N approach. I can picture the second approach being the right answer if for some reason you're running in an environment where RAM is critically short but you have plenty of mass storage. A third of a terabyte on a disk is no big deal, getting your data in one probe of the disk is worth something. The simple binary approach takes 13 on average. (Note, however, that by clustering your keys you can get this down to a guaranteed 3 reads and in practice you would cache the first one.)

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

Yes.

在实际情况下,我们运行了一些使用短字符串和长字符串键进行表查找的测试。

我们使用了std::map, std::unordered_map和一个哈希,该哈希最多对字符串长度进行10次采样(我们的键倾向于guidlike,所以这是体面的),以及一个哈希,对每个字符进行采样(理论上减少了冲突),一个未排序的向量,其中我们进行==比较,以及(如果我没记错的话)一个未排序的向量,其中我们还存储了一个哈希,首先比较哈希,然后比较字符。

这些算法的范围从O(1) (unordered_map)到O(n)(线性搜索)。

对于中等大小的N,通常O(N)优于O(1)。我们怀疑这是因为基于节点的容器需要我们的计算机在内存中跳跃更多,而基于线性的容器则不需要。

O(lgn)存在于两者之间。我不记得是怎么回事了。

性能差异并不大,在更大的数据集上,基于哈希的表现要好得多。所以我们坚持使用基于哈希的无序映射。

实际上,对于合理的n大小,O(lgn)为O(1)。如果你的计算机在你的表中只有40亿的空间,那么O(lgn)的上界是32。(lg(2^32)=32)(在计算机科学中,lg是log based 2的简称)。

在实践中,lg(n)算法比O(1)算法慢,不是因为对数增长因子,而是因为lg(n)部分通常意味着算法有一定程度的复杂性,并且这种复杂性比lg(n)项中的任何“增长”都增加了更大的常数因子。

然而,复杂的O(1)算法(如哈希映射)很容易具有类似或更大的常数因子。

考虑一个红黑树。它具有O(log n)的访问、搜索、插入和删除操作。与数组相比,数组的访问权限为O(1),其余操作为O(n)。

因此,对于一个插入、删除或搜索比访问更频繁的应用程序,并且只能在这两种结构之间进行选择,我们更喜欢红黑树。在这种情况下,你可能会说我们更喜欢红黑树更麻烦的O(log n)访问时间。

为什么?因为权限不是我们最关心的。我们正在权衡:应用程序的性能更大程度上受到其他因素的影响。我们允许这种特定的算法受到性能影响,因为我们通过优化其他算法获得了很大的收益。

So the answer to your question is simply this: when the algorithm's growth rate isn't what we want to optimize, when we want to optimize something else. All of the other answers are special cases of this. Sometimes we optimize the run time of other operations. Sometimes we optimize for memory. Sometimes we optimize for security. Sometimes we optimize maintainability. Sometimes we optimize for development time. Even the overriding constant being low enough to matter is optimizing for run time when you know the growth rate of the algorithm isn't the greatest impact on run time. (If your data set was outside this range, you would optimize for the growth rate of the algorithm because it would eventually dominate the constant.) Everything has a cost, and in many cases, we trade the cost of a higher growth rate for the algorithm to optimize something else.