对于安全应用程序来说，这经常是这样的情况，我们希望设计算法缓慢的问题，以阻止某人过快地获得问题的答案。

这里有几个我能想到的例子。

Password hashing is sometimes made arbitrarily slow in order to make it harder to guess passwords by brute-force. This Information Security post has a bullet point about it (and much more). Bit Coin uses a controllably slow problem for a network of computers to solve in order to "mine" coins. This allows the currency to be mined at a controlled rate by the collective system. Asymmetric ciphers (like RSA) are designed to make decryption without the keys intentionally slow in order to prevent someone else without the private key to crack the encryption. The algorithms are designed to be cracked in hopefully O(2^n) time where n is the bit-length of the key (this is brute force).

在CS的其他地方，快速排序在最坏的情况下是O(n²)，但在一般情况下是O(n*log(n))。因此，在分析算法效率时，“大O”分析有时并不是您唯一关心的事情。

总有一个隐藏常数，在O(log n)算法中可以更低。因此，在实际生活数据中，它可以更快地工作。

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

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

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)算法(如哈希映射)很容易具有类似或更大的常数因子。

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

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

并行执行算法的可能性。

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

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