在任何情况下，您更喜欢高大o时间复杂度算法而不是低大o时间复杂度算法吗?

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

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

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

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

我很惊讶没有人提到内存绑定应用程序。

可能存在一种算法，由于其复杂性(例如O(1) <O(log n)))或者因为前面的常数复杂度更小(即2 <我> n < / i > <一口> 2 > < /晚餐& lt;6 n <我> < / i > <一口> 2 > < /晚餐)。无论如何，如果较低的FLOP算法的内存限制更大，您可能仍然更喜欢具有更多FLOP的算法。

我所说的“内存受限”是指您经常访问的数据经常超出缓存。为了获取这些数据，在对其执行操作之前，必须将内存从实际内存空间拉到缓存中。这个抓取步骤通常非常慢——比您的操作本身慢得多。

因此，如果你的算法需要更多的操作(但这些操作是在已经在缓存中的数据上执行的[因此不需要读取])，它仍然会在实际的walltime方面以更少的操作(必须在缓存外的数据上执行[因此需要读取])胜过你的算法。

我在这里的回答对随机矩阵的所有行进行快速随机加权选择是一个例子，当m不是太大时，复杂度为O(m)的算法比复杂度为O(log(m))的算法更快。

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

因此，对于一个插入、删除或搜索比访问更频繁的应用程序，并且只能在这两种结构之间进行选择，我们更喜欢红黑树。在这种情况下，你可能会说我们更喜欢红黑树更麻烦的O(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的存储空间。

使用哪种方法取决于您的硬件。在大多数合理的现代构型中，你会使用log N的方法。我可以想象第二种方法是正确的答案，如果由于某种原因，您正在运行在RAM非常短但有足够大容量存储的环境中。磁盘上的三分之一tb不是什么大问题，在磁盘上的一次探测中获取数据是有价值的。简单的二进制方法平均需要13。(但是，请注意，通过集群你的键，你可以把它减少到保证3次读取，在实践中你会缓存第一个。)

并行执行算法的可能性。

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

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

是的。

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

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

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

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

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

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

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

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

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

一个更普遍的问题是，如果在某些情况下，人们更喜欢O(f(n))算法而不是O(g(n))算法，即使g(n) << f(n)作为n趋于无穷。正如其他人已经提到的，在f(n) = log(n)和g(n) = 1的情况下，答案显然是“是的”。即使在f(n)是多项式而g(n)是指数的情况下，有时也是肯定的。一个著名而重要的例子是用于解决线性规划问题的单纯形算法。20世纪70年代，它被证明是O(2^n)。因此，其最坏情况下的行为是不可行的。但是——它的O(g(n))0行为非常好，即使对于有成千上万个变量和约束的实际问题也是如此。在20世纪80年代，线性规划的多项式时间算法(如O(g(n))1)被发现，但30年后，单纯形算法似乎仍然是首选算法(除非某些非常大的问题)。这显然是因为平均情况的行为通常比最坏情况的行为更重要，但也因为更微妙的原因，单纯形算法在某种意义上更有信息量(例如，灵敏度信息更容易提取)。

假设您正在嵌入式系统上实现一个黑名单，其中0到1,000,000之间的数字可能被列入黑名单。这就给你留下了两个选择:

1. 使用1,000,000位的bitset
2. 使用黑名单整数的排序数组，并使用二进制搜索来访问它们

对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)的哈希表可能会击败所有这些算法。

使用O(log(n))算法而不是O(1)算法有一个很好的用例，许多其他答案都忽略了这一点:不可变性。哈希映射有O(1)个put和get，假设哈希值分布良好，但它们需要可变状态。不可变树映射有O(log(n))个put和get，渐近地慢一些。然而，不可变性可以有足够的价值来弥补较差的性能，并且在需要保留多个版本的映射的情况下，不可变性允许您避免必须复制映射，这是O(n)，因此可以改善性能。

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

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

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

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

• 大多数时候，较低的大o复杂度很难实现，需要熟练的实现、大量的知识和大量的测试。
• big-O隐藏了常数的细节:从大o的角度来看，在10^5中执行的算法比1/10^5 * log(n) (O(1) vs O(log(n))更好，但对于大多数合理的n，第一个算法会执行得更好。例如，矩阵乘法的最佳复杂度是O(n^2.373)，但这个常数太高了，(据我所知)没有计算库使用它。
• 当你计算大的东西时，大o是有意义的。如果你需要对一个包含三个数字的数组进行排序，那么使用O(n*log(n))还是O(n^2)算法都无关紧要。
• 有时候，小写时间复杂度的优势真的可以忽略不计。对于例子中有一个数据结构的探戈树，它给出了O(log log N)时间复杂度来查找项，但在O(log n)中也有一个二叉树。即使对于大量的n = 10^20，差异也可以忽略不计。
• 时间复杂性并不是一切。想象一个运行在O(n^2)中并且需要O(n^2)内存的算法。当n不是很大时，它可能比O(n^3) time和O(1) space更可取。问题是，你可以等待很长时间，但非常怀疑你能找到一个足够大的RAM来使用你的算法
• 并行化在分布式世界中是一个很好的特性。有些算法很容易实现并行化，而有些算法根本不能实现并行化。有时，在1000台复杂度较高的普通机器上运行一个算法比在一台复杂度略高的机器上运行更有意义。
• 在某些地方(安全性)，复杂性可能是一种需求。没有人想要一个哈希算法可以非常快地哈希(因为这样其他人就可以更快地使用暴力)。
• 虽然这与复杂性的切换无关，但一些安全函数应该以防止定时攻击的方式编写。它们大多保持在相同的复杂度类中，但是以一种总是在更坏的情况下执行某些操作的方式进行了修改。一个例子是比较字符串是否相等。在大多数应用程序中，如果第一个字节不同，则快速中断是有意义的，但在安全性方面，您仍然要等到最后才告诉坏消息。
• 有人申请了低复杂度算法的专利，对公司来说，使用更高复杂度的算法比花钱更经济。
• 有些算法能很好地适应特定的情况。例如，插入排序的平均时间复杂度为O(n^2)，比快速排序或归并排序差，但作为在线算法，它可以在接收到的值列表(作为用户输入)时有效地对其进行排序，而大多数其他算法只能有效地对完整的值列表进行操作。

以下是我的观点:

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

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

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

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

简单地说:因为系数(与该步骤的设置、存储和执行时间相关的成本)在较小的大o问题中比在较大的大o问题中要大得多。大o只是算法可伸缩性的度量。

考虑以下来自黑客词典的例子，提出了一个依赖量子力学的多重世界解释的排序算法:

1. 用量子过程随机排列数组，
2. 如果数组没有排序，毁灭宇宙。
3. 所有剩下的宇宙现在都被排序了(包括你所在的宇宙)。

(来源:http://catb.org/~esr/jargon/html/B/bogo-sort.html)

注意，这个算法的大o是O(n)，它在一般项上击败了迄今为止任何已知的排序算法。线性阶跃的系数也很低(因为它只是一个比较，而不是交换，是线性完成的)。事实上，类似的算法可以用于在多项式时间内解决NP和co-NP中的任何问题，因为每个可能的解(或可能的没有解的证明)都可以使用量子过程生成，然后在多项式时间内验证。

然而，在大多数情况下，我们可能不想冒多重世界可能不正确的风险，更不用说实现步骤2的行为仍然是“留给读者的练习”。

1. 当O(1)中的“1”工作单元相对于O(log n)中的工作单元非常高，且期望集大小较小时。例如，如果数组中只有两到三个项，那么计算Dictionary哈希码可能比迭代数组要慢。

或

2. 当O(1)算法中的内存或其他非时间资源需求相对于O(log n)算法非常大时。

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

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

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

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

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

当n很小，而O(1)总是很慢。

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

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

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

• 密码哈希有时会变得非常慢，以便通过暴力破解更难猜出密码。这个信息安全岗位有一个关于它的项目符号(以及更多)。
• 一些硬币使用一个计算机网络来解决一个可控制的缓慢问题，以“开采”硬币。这使得货币可以由集体系统以控制的速度开采。
• 非对称密码(如RSA)被设计为使没有密钥的解密故意变慢，以防止没有私钥的其他人破解加密。这些算法被设计成希望在O(2^n)时间内被破解，其中n是密钥的比特长度(这是暴力破解)。

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

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

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

const hasDuplicate = arr => {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) {
return true;
}
}
}
  

return false;
};


console.log(hasDuplicate([1, 2, 3, 4]));
console.log(hasDuplicate([1, 2, 4, 4]));

但这可以通过创建一组数据结构(即删除重复项)，然后将其大小与数组的长度进行比较，在线性时间内完成:

const hasDuplicate = arr => new Set(arr).size !== arr.length;
console.log(hasDuplicate([1, 2, 3, 4]));
console.log(hasDuplicate([1, 2, 4, 4]));

大O告诉我们，从时间复杂度的角度来看，new Set方法将更好地扩展。

然而，事实证明，“天真”;二次元方法有很多大O无法解释的因素:

• 没有额外的内存占用
• 没有堆内存分配(没有new)
• 临时Set没有垃圾收集
• 早期的救助;在已知副本可能位于数组前面的情况下，不需要检查多个元素。

如果我们的用例是在有限的小数组上，我们有一个资源受限的环境和/或其他已知的常见情况属性，允许我们通过基准测试建立嵌套循环在特定工作负载上更快，这可能是一个好主意。

另一方面，也许可以预先创建一次集合并重复使用，在所有查找中摊销其开销成本。

这不可避免地导致可维护性/可读性/优雅性和其他“软”。成本。在这种情况下，new Set()方法可能更具可读性，但通常(如果不是更多的话)实现更好的复杂性需要巨大的工程成本。

创建和维护持久的、有状态的Set结构可能会引入错误、内存/缓存压力、代码复杂性和所有其他设计权衡方式。最优地协商这些权衡是软件工程的一个重要部分，而时间复杂性只是帮助指导这个过程的一个因素。

我还没有看到其他一些例子:

• 在实时环境中，例如资源受限的嵌入式系统，有时需要牺牲复杂性(通常与缓存和内存或调度相关)，以避免偶尔出现最坏情况的惩罚，因为它们可能会导致抖动。
• 同样在嵌入式编程中，代码本身的大小也会造成缓存压力，从而影响内存性能。如果一种算法的复杂度更低，但可以节省大量代码，这可能是选择它而不是理论上更好的算法的原因。
• 在大多数递归线性算法(如快速排序)的实现中，当数组足够小时，通常会调用像插入排序这样的二次排序算法，因为对越来越小的数组调用递归函数的开销往往超过嵌套循环的开销。插入排序在大多数排序的数组上也很快，因为内部循环不会运行太多。这个答案在Chrome的V8引擎的旧版本中讨论了这一点，然后他们转移到Timsort。