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

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

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

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

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

以下是我的观点:

有时，当算法在特定的硬件环境中运行时，会选择较差的复杂度算法来代替较好的算法。假设我们的O(1)算法非顺序地访问一个非常大的固定大小数组的每个元素来解决我们的问题。然后将该阵列放在机械硬盘驱动器或磁带上。

在这种情况下，O(logn)算法(假设它按顺序访问磁盘)变得更有利。

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

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

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.

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

选择大O复杂度高的算法而不是大O复杂度低的算法的原因有很多:

most of the time, lower big-O complexity is harder to achieve and requires skilled implementation, a lot of knowledge and a lot of testing. big-O hides the details about a constant: algorithm that performs in 10^5 is better from big-O point of view than 1/10^5 * log(n) (O(1) vs O(log(n)), but for most reasonable n the first one will perform better. For example the best complexity for matrix multiplication is O(n^2.373) but the constant is so high that no (to my knowledge) computational libraries use it. big-O makes sense when you calculate over something big. If you need to sort array of three numbers, it matters really little whether you use O(n*log(n)) or O(n^2) algorithm. sometimes the advantage of the lowercase time complexity can be really negligible. For example there is a data structure tango tree which gives a O(log log N) time complexity to find an item, but there is also a binary tree which finds the same in O(log n). Even for huge numbers of n = 10^20 the difference is negligible. time complexity is not everything. Imagine an algorithm that runs in O(n^2) and requires O(n^2) memory. It might be preferable over O(n^3) time and O(1) space when the n is not really big. The problem is that you can wait for a long time, but highly doubt you can find a RAM big enough to use it with your algorithm parallelization is a good feature in our distributed world. There are algorithms that are easily parallelizable, and there are some that do not parallelize at all. Sometimes it makes sense to run an algorithm on 1000 commodity machines with a higher complexity than using one machine with a slightly better complexity. in some places (security) a complexity can be a requirement. No one wants to have a hash algorithm that can hash blazingly fast (because then other people can bruteforce you way faster) although this is not related to switch of complexity, but some of the security functions should be written in a manner to prevent timing attack. They mostly stay in the same complexity class, but are modified in a way that it always takes worse case to do something. One example is comparing that strings are equal. In most applications it makes sense to break fast if the first bytes are different, but in security you will still wait for the very end to tell the bad news. somebody patented the lower-complexity algorithm and it is more economical for a company to use higher complexity than to pay money. some algorithms adapt well to particular situations. Insertion sort, for example, has an average time-complexity of O(n^2), worse than quicksort or mergesort, but as an online algorithm it can efficiently sort a list of values as they are received (as user input) where most other algorithms can only efficiently operate on a complete list of values.