在任何情况下，您更喜欢较高的大 O 时间复杂度算法而不是较低的时间复杂度算法？
在某些情况下，您更喜欢 O(log n) 时间复杂度而不是 O(1) 时间复杂度？还是 O(n) 到 O(log n)？
你有什么例子吗？
O(log n) 算法而不是 O(1) 算法，但不是后者......
可能有很多理由更喜欢具有较高大 O 时间复杂度的算法而不是较低的算法：
大多数时候，较低的 big-O 复杂度更难实现，需要熟练的实施、大量的知识和大量的测试。
big-O 隐藏了有关常量的细节：从 big-O 的角度来看，在 10^5 中执行的算法比 1/10^5 * log(n) (O(1) vs O(log(n)) 更好, 但对于最合理的 n, 第一个会表现得更好. 例如, 矩阵乘法的最佳复杂度是 O(n^2.373) 但常数是如此之高, 以至于 (据我所知) 没有计算库使用它.
当你计算一些大的东西时，big-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) 时间和 O(1) 空间更可取。问题是您可以等待很长时间，但非常怀疑您能否找到足够大的 RAM 以将其与您的算法一起使用
在我们的分布式世界中，并行化是一个很好的特性。有些算法很容易并行化，有些算法根本不并行化。有时在 1000 台复杂度更高的商品机器上运行算法比使用复杂度稍高的机器更有意义。
在某些地方（安全性），可能需要复杂性。没有人想要一种哈希算法可以非常快地哈希（因为这样其他人可以更快地暴力破解你）
虽然这和switch的复杂度无关，但是一些安全函数应该写成防止定时攻击的方式。它们大多停留在同一个复杂性类别中，但被修改为总是需要更糟的情况才能做某事。一个例子是比较字符串是否相等。在大多数应用程序中，如果第一个字节不同，则快速中断是有意义的，但在安全方面，您仍然会等待最后告诉坏消息。
有人为低复杂度算法申请了专利，公司使用更高复杂度的算法比花钱更经济。
一些算法很好地适应特定情况。例如，插入排序的平均时间复杂度为 O(n^2)，比快速排序或归并排序差，但作为一种在线算法，它可以在接收到值列表（作为用户输入）时有效地对值列表进行排序，其中大多数其他算法只能有效地对完整的值列表进行操作。
总是存在隐藏常数，在 O(log n) 算法中可能会更低。因此，它可以在实际数据中更快地工作。
还有空间问题（例如在烤面包机上运行）。
还有开发人员时间问题 - O(log n) 可能更容易实现和验证 1000 倍。
n，lg n 非常接近 k，以至于大多数操作都不会注意到差异。
我很惊讶还没有人提到内存绑定的应用程序。
可能有一种算法由于其复杂性（即 O(1) < O(log n)）或因为复杂性前面的常数较小（即 2n2 < 6n2）而具有较少的浮点运算。无论如何，如果较低的 FLOP 算法更受内存限制，您可能仍然更喜欢具有更多 FLOP 的算法。
我所说的“内存受限”是指您经常访问不断超出缓存的数据。为了获取此数据，您必须先将内存从实际内存空间中提取到缓存中，然后才能对其执行操作。这个获取步骤通常很慢 - 比您的操作本身慢得多。
因此，如果您的算法需要更多操作（但这些操作是对已经在缓存中的数据执行的[因此不需要提取]），它仍然会以更少的操作（必须在-缓存数据[因此需要获取]）就实际挂起时间而言。
O(logn) 而不是 O(1)。您可以很容易地想象这样一种情况，即对于所有可行的 n，内存限制较少的应用程序将在更快的 wall-time 中运行，即使在更高的复杂性下也是如此。
在涉及数据安全性的上下文中，如果更复杂的算法对 timing attacks 具有更好的抵抗力，则更复杂的算法可能比不太复杂的算法更可取。
(n mod 5) + 1 成比例，它仍然是 O(1)，但会显示有关 n 的信息。因此，具有更平滑运行时间的更复杂算法可能更可取，即使它可能渐近（甚至可能在实践中）更慢。
Alistra 做到了，但没有提供任何例子，所以我会的。
您有一个包含 10,000 个 UPC 代码的列表，用于您的商店销售的商品。 10 位 UPC，整数表示价格（以美分表示的价格）和 30 位收据描述字符。
O(log N) 方法：您有一个排序列表。如果是 ASCII 则为 44 个字节，如果为 Unicode 则为 84 个字节。或者，将 UPC 视为 int64 并获得 42 和 72 字节。 10,000 条记录——在最高情况下，您所看到的存储空间略低于 1 兆字节。
O(1) 方法：不要存储 UPC，而是将其用作数组的条目。在最低的情况下，您会看到近三分之一 TB 的存储空间。
您使用哪种方法取决于您的硬件。在大多数合理的现代配置中，您将使用 log N 方法。如果由于某种原因您在 RAM 非常短但您拥有大量大容量存储的环境中运行，我可以认为第二种方法是正确的答案。磁盘上 1/3 TB 没什么大不了的，将数据放入磁盘的一次探测中是值得的。简单的二进制方法平均需要 13 个。 （但是请注意，通过对密钥进行聚类，您可以将其降低到保证 3 次读取，实际上您将缓存第一个。）
malloc(search_space_size) 并下标到它返回的内容是很容易的。
考虑一棵红黑树。它可以访问、搜索、插入和删除 O(log n)。与具有 O(1) 访问权限且其余操作为 O(n) 的数组进行比较。
因此，如果应用程序插入、删除或搜索的频率高于访问频率，并且只能在这两种结构之间进行选择，我们会更喜欢红黑树。在这种情况下，您可能会说我们更喜欢红黑树更麻烦的 O(log n) 访问时间。
为什么？因为访问不是我们最关心的问题。我们正在做一个权衡：我们的应用程序的性能更受除此之外的因素的影响。我们允许这种特定算法的性能受到影响，因为我们通过优化其他算法获得了巨大的收益。
所以你的问题的答案很简单：当算法的增长率不是我们想要优化的时候，当我们想要优化其他东西时。所有其他答案都是这种情况的特例。有时我们会优化其他操作的运行时间。有时我们会针对内存进行优化。有时我们会针对安全性进行优化。有时我们会优化可维护性。有时我们会优化开发时间。当您知道算法的增长率不是对运行时间的最大影响时，即使是压倒一切的常数足够低，也可以优化运行时间。 （如果你的数据集在这个范围之外，你会优化算法的增长率，因为它最终会支配常数。）一切都有成本，在很多情况下，我们用更高增长率的成本来换取算法来优化其他东西。
O(log n)的“访问”和“搜索”是什么？在数组 [1, 2, 1, 4] 的位置 2 中插入 5 将导致 [1, 2, 5, 1 4]（元素 4 的索引将从 3 更新到 4）。您将如何在您引用为“排序列表”的“红黑树”中的 O(log n) 中获得此行为？
是的。
在一个真实的案例中，我们运行了一些关于使用短字符串和长字符串键进行表查找的测试。
我们使用了一个 std::map，一个 std::unordered_map，其哈希值最多采样超过字符串长度的 10 倍（我们的键往往是类似 guid 的，所以这很不错），以及一个对每个字符进行采样的哈希值 (理论上减少了冲突），一个未排序的向量，我们在其中进行 == 比较，以及（如果我没记错的话）一个未排序的向量，我们还存储了一个哈希，首先比较哈希，然后比较字符。
这些算法的范围从 O(1) (unordered_map) 到 O(n) (linear search)。
对于中等大小的 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(log n)和O(1)的例子，但是对于一些问题，当算法更容易并行执行时，你会选择复杂度更高的算法。
有些算法不能并行化，但复杂度很低。考虑另一种算法，它可以实现相同的结果并且可以轻松并行化，但具有更高的复杂度等级。在一台机器上执行时，第二种算法速度较慢，但在多台机器上执行时，实际执行时间越来越短，而第一种算法无法加速。
假设您正在嵌入式系统上实施黑名单，其中 0 到 1,000,000 之间的数字可能被列入黑名单。这给你留下了两个可能的选择：
使用 1,000,000 位的位集 使用黑名单整数的排序数组并使用二进制搜索来访问它们
对位集的访问将保证持续访问。就时间复杂度而言，它是最优的。从理论和实践的角度来看（它是 O(1)，具有极低的恒定开销）。
不过，您可能更喜欢第二种解决方案。特别是如果您希望列入黑名单的整数的数量非常少，因为它会提高内存效率。
即使您不为内存稀缺的嵌入式系统进行开发，我也可以将 1,000,000 的任意限制增加到 1,000,000,000,000 并提出相同的论点。那么 bitset 将需要大约 125G 的内存。保证 O(1) 的最坏情况复杂性可能无法说服您的老板为您提供如此强大的服务器。
在这里，我更喜欢二进制搜索（O（log n））或二叉树（O（log n））而不是O（1）位集。并且，在实践中，最坏情况复杂度为 O(n) 的哈希表可能会击败所有这些哈希表。
我在这里的回答 Fast random weighted selection across all rows of a stochastic matrix 是一个例子，当 m 不太大时，复杂度为 O(m) 的算法比复杂度为 O(log(m)) 的算法快。
一个更普遍的问题是，即使在 g(n) << f(n) 和 n 趋于无穷大的情况下，是否会更喜欢 O(f(n)) 算法而不是 O(g(n)) 算法。正如其他人已经提到的，在 f(n) = log(n) 和 g(n) = 1 的情况下，答案显然是“是”。即使在 f(n) 是多项式但 g(n) 是指数的情况下，有时也是如此。一个著名且重要的例子是用于解决线性规划问题的 Simplex Algorithm。在 1970 年代，它被证明是 O(2^n)。因此，它的最坏情况行为是不可行的。但是——它的平均情况行为非常好，即使对于具有数万个变量和约束的实际问题也是如此。在 1980 年代，发现了用于线性规划的多项式时间算法（例如 Karmarkar's interior-point algorithm），但 30 年后，单纯形算法似乎仍然是首选算法（某些非常大的问题除外）。这是因为一般情况下的行为通常比最坏情况下的行为更重要，但也有一个更微妙的原因，即单纯形算法在某种意义上更具信息性（例如，敏感性信息更容易提取）。
人们已经回答了你的确切问题，所以我将解决一个稍微不同的问题，人们来到这里时可能会真正想到这个问题。
许多“O(1) 时间”的算法和数据结构实际上只需要预期的 O(1) 时间，这意味着它们的平均运行时间是 O(1)，可能只是在某些假设下。
常见示例：哈希表、“数组列表”的扩展（也称为动态大小的数组/向量）。
在这种情况下，您可能更喜欢使用时间保证绝对对数有界的数据结构或算法，即使它们的平均性能可能更差。因此，一个示例可能是平衡二叉搜索树，其运行时间平均而言更差，但在最坏的情况下更好。
把我的 2 美分放进去：
当算法在特定硬件环境上运行时，有时会选择更复杂的算法来代替更好的算法。假设我们的 O(1) 算法非顺序地访问一个非常大的、固定大小的数组的每个元素来解决我们的问题。然后将该阵列放在机械硬盘驱动器或磁带上。
在这种情况下，O(logn) 算法（假设它按顺序访问磁盘）变得更有利。
使用 O(log(n)) 算法而不是许多其他答案都忽略的 O(1) 算法有一个很好的用例：不变性。散列映射有 O(1) 的 put 和 get，假设散列值分布良好，但它们需要可变状态。不可变树映射具有 O(log(n)) 的 put 和 get，渐近地变慢。然而，不变性可以弥补较差的性能，并且在需要保留多个版本的地图的情况下，不变性允许您避免复制地图，这是 O(n)，因此可以提高表现。
简单地说：因为系数 - 与该步骤的设置、存储和执行时间相关的成本 - 使用较小的 big-O 问题可能比使用较大的问题要大得多。 Big-O 只是衡量算法可扩展性的指标。
考虑以下来自 Hacker's Dictionary 的示例，它提出了一个依赖于 Multiple Worlds Interpretation of Quantum Mechanics 的排序算法：
使用量子过程随机排列数组，如果数组未排序，则破坏宇宙。现在所有剩余的宇宙都已排序[包括你所在的宇宙]。
（来源：http://catb.org/~esr/jargon/html/B/bogo-sort.html）
请注意，该算法的大 O 是 O(n)，它优于迄今为止对通用项目的任何已知排序算法。线性步骤的系数也非常低（因为它只是比较，而不是交换，是线性完成的）。事实上，类似的算法可以用于在多项式时间内解决 NP 和 co-NP 中的任何问题，因为可以使用量子过程生成每个可能的解决方案（或没有解决方案的可能证明），然后在多项式时间内验证。
但是，在大多数情况下，我们可能不想冒多重世界可能不正确的风险，更不用说实施步骤 2 的行为仍然“留给读者作为练习”。
在 n 有界且 O(1) 算法的常数乘数高于 log(n) 的界限的任何时候。例如，在哈希集中存储值是 O(1)，但可能需要对哈希函数进行昂贵的计算。如果可以简单地比较数据项（关于某些顺序）并且 n 上的界限使得 log n 明显小于任何一项的哈希计算，那么存储在平衡二叉树中可能比存储在平衡二叉树中更快一个哈希集。
在需要确定上限的实时情况下，您会选择例如堆排序而不是快速排序，因为堆排序的平均行为也是其最坏情况的行为。
添加到已经很好的答案。一个实际的例子是哈希索引与 postgres 数据库中的 B-tree 索引。
哈希索引形成哈希表索引来访问磁盘上的数据，而 btree 顾名思义使用 Btree 数据结构。
在 Big-O 时间中，这些是 O(1) 与 O(logN)。
目前不鼓励在 postgres 中使用哈希索引，因为在现实生活中，特别是在数据库系统中，实现无冲突的哈希非常困难（可能导致 O(N) 最坏情况复杂性），因此，更难做到它们是安全的（称为预写日志记录 - postgres 中的 WAL）。
在这种情况下需要权衡取舍，因为 O(logN) 对于索引来说已经足够好了，而实现 O(1) 非常困难，而且时间差并不重要。
当 n 很小，而 O(1) 一直很慢。
当 O(1) 中的“1”工作单元相对于 O(log n) 中的工作单元非常高并且预期的集合大小很小时。例如，如果只有两个或三个项目，计算 Dictionary 哈希码可能比迭代数组要慢。
或者
当 O(1) 算法中的内存或其他非时间资源需求相对于 O(log n) 算法异常大时。
当重新设计一个程序时，发现一个程序用 O(1) 而不是 O(lgN) 进行优化，但如果不是这个程序的瓶颈，那么 O(1) 算法就很难理解了。然后，当 O(1) 需要您无法提供的大量内存时，您不必使用 O(1) 算法，而可以接受 O(lgN) 的时间。
对于我们想要设计算法缓慢的问题的安全应用程序来说，通常是这种情况，以阻止某人过快地获得问题的答案。
这是我脑海中的几个例子。
密码散列有时会变得任意慢，以便更难通过蛮力猜测密码。这个信息安全帖子有一个关于它的要点（以及更多）。
比特币使用计算机网络来解决一个可控的缓慢问题，以便“挖掘”硬币。这允许集体系统以受控的速度开采货币。
非对称密码（如 RSA）旨在使没有密钥的解密故意变慢，以防止没有私钥的其他人破解加密。这些算法被设计成希望在 O(2^n) 时间内被破解，其中 n 是密钥的位长（这是蛮力）。
在 CS 的其他地方，快速排序在最坏的情况下是 O(n^2)，但在一般情况下是 O(n*log(n))。出于这个原因，“Big 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]) { 返回真； } } } 返回错误； }; 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]));
Big O 告诉我们的是，从时间复杂度的角度来看，new Set 方法的扩展性会好很多。
然而，事实证明，“幼稚”的二次方法有很多大 O 无法解释的原因：
没有额外的内存使用
没有堆内存分配（没有新的）
临时 Set 没有垃圾收集
提前救助；如果已知重复项可能位于数组的前面，则无需检查多个元素。
如果我们的用例是有界小数组，我们有一个资源受限的环境和/或其他已知的常见情况属性允许我们通过基准确定嵌套循环在我们的特定工作负载上更快，这可能是一个好主意。
另一方面，也许该集合可以预先创建一次并重复使用，从而在所有查找中分摊其开销成本。
这不可避免地导致可维护性/可读性/优雅和其他“软”成本。在这种情况下，new Set() 方法可能更具可读性，但通常（如果不是更频繁）实现更好的复杂性需要付出巨大的工程成本。
创建和维护持久的、有状态的 Set 结构可能会引入错误、内存/缓存压力、代码复杂性以及所有其他设计权衡方式。以最佳方式协商这些权衡是软件工程的重要组成部分，时间复杂度只是帮助指导该过程的一个因素。
其他一些我还没有提到的例子：
在实时环境中，例如资源受限的嵌入式系统，有时会牺牲复杂性（通常与缓存和内存或调度有关）以避免偶尔出现无法容忍的最坏情况惩罚，因为它们可能会导致抖动。
同样在嵌入式编程中，代码本身的大小会导致缓存压力，从而影响内存性能。如果算法的复杂性更差，但会节省大量代码大小，那么这可能是选择它而不是理论上更好的算法的原因。
在大多数递归线性算法（如快速排序）的实现中，当数组足够小时，通常会调用像插入排序这样的二次排序算法，因为在越来越小的数组上调用递归函数的开销往往超过嵌套循环的成本。插入排序在大多数排序的数组上也很快，因为内部循环不会运行太多。这个答案在 Chrome 的 V8 引擎迁移到 Timsort 之前的旧版本中讨论了这个问题。
