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

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

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(logn)算法(假设它按顺序访问磁盘)变得更有利。

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

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

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

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

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