考虑一个红黑树。它具有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.

给已经好的答案锦上添花。一个实际的例子是postgres数据库中的哈希索引和b树索引。

哈希索引形成一个哈希表索引来访问磁盘上的数据，而btree顾名思义使用的是btree数据结构。

大O时间是O(1) vs O(logN)

目前不鼓励在postgres中使用哈希索引，因为在现实生活中，特别是在数据库系统中，实现无冲突的哈希是非常困难的(可能导致O(N)最坏情况的复杂性)，正因为如此，使它们具有崩溃安全性就更加困难了(在postgres中称为提前写日志- WAL)。

在这种情况下进行这种权衡，因为O(logN)对于索引来说已经足够好了，而实现O(1)非常困难，而且时间差并不重要。

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

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

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

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

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

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

假设您正在嵌入式系统上实现一个黑名单，其中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)的哈希表可能会击败所有这些算法。