在某些情况下，您是否更喜欢较高的 big-O 时间复杂度算法而不是较低的算法？

Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?

在某些情况下，您更喜欢 O(log n) 时间复杂度而不是 O(1) 时间复杂度？或者 O(n) 到 O(log n)?

有没有例子？

总有隐藏常数，在O(log n)算法上可以更低。因此它可以在实践中更快地处理现实生活中的数据。

还有 space 个问题（例如 运行 在烤面包机上）。

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

在关注数据安全的情况下，如果更复杂的算法对 timing attacks 具有更好的抵抗力，则更复杂的算法可能比不太复杂的算法更可取。

我很惊讶还没有人提到内存限制应用程序。

可能有一种算法由于其复杂性而具有较少的浮点运算（即 O(1) < O( log n)) 或者因为复杂度前面的常量较小 (即 2n2 < 6n2)。无论如何，如果较低的 FLOP 算法更受内存限制，您可能仍然更喜欢具有更多 FLOP 的算法。

我所说的 "memory-bound" 的意思是您经常访问缓存外的数据。为了获取此数据，您必须先将内存从实际内存 space 拉入缓存，然后才能对其执行操作。这个获取步骤通常很慢——比你的操作本身慢得多。

因此，如果您的算法需要更多操作（但这些操作是对缓存中已有的数据执行的[因此不需要提取]），它仍然会以更少的操作（必须是对缓存外数据执行[因此需要获取]）根据实际挂钟时间。

我在这里的回答 是一个例子，当 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 条记录——在最高情况下，您看到的存储空间不足 1 兆字节。

O(1) 方法：不存储 UPC，而是将其用作数组的条目。在最低的情况下，您将看到几乎三分之一的 TB 存储空间。

您使用哪种方法取决于您的硬件。在大多数合理的现代配置中，您将使用 log N 方法。我可以想象第二种方法是正确的答案，如果出于某种原因你 运行 在 RAM 非常短但你有足够大容量存储的环境中。磁盘上 1/3 TB 的数据没什么大不了的，在磁盘的一次探测中获取数据是值得的。简单的二进制方法平均需要 13 个。 （但是请注意，通过将您的密钥聚类，您可以将其减少到保证 3 次读取，实际上您将缓存第一个。）

并行执行算法的可能性。

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

有些算法不能并行化但复杂度很低class。考虑另一种算法，它可以实现相同的结果并且可以轻松并行化，但具有更高的复杂度 class。在一台机器上执行时，第二种算法比较慢，但在多台机器上执行时，实际执行时间越来越低，而第一种算法无法加速。

是的。

在真实案例中，我们 运行 进行了一些测试，以使用短字符串键和长字符串键进行 table 查找。

我们使用了一个 std::map，一个 std::unordered_map 和一个散列，在字符串的长度上最多采样 10 次（我们的键倾向于类似 guid，所以这是不错的） ，以及一个对每个字符进行采样的散列（理论上减少了冲突），一个未排序的向量，我们在其中进行 == 比较，以及（如果我没记错的话）一个未排序的向量，我们还存储一个散列，首先比较散列, 然后比较字符。

这些算法运行从O(1)（unordered_map）到O(n)（线性搜索）。

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

O(lg n)存在于两者之间。我不记得它是怎么做到的。

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

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

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

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

一个更普遍的问题是，即使 g(n) << f(n) 因为 n 趋于无穷大，是否存在人们更喜欢 O(f(n)) 算法而不是 O(g(n)) 算法的情况。正如其他人已经提到的，在 f(n) = log(n) 和 g(n) = 1 的情况下，答案显然是 "yes"。即使在 f(n) 是多项式但 g(n) 是指数的情况下，有时也是肯定的。一个著名且重要的例子是线性规划的 Simplex Algorithm for solving linear programming problems. In the 1970s it was shown to be O(2^n). Thus, its worse-case behavior is infeasible. But -- its average case behavior is extremely good, even for practical problems with tens of thousands of variables and constraints. In the 1980s, polynomial time algorithms (such a Karmarkar's interior-point algorithm) 被发现，但 30 年后，单纯形算法似乎仍然是首选算法（某些非常大的问题除外）。这是一个明显的原因，平均情况下的行为通常比最坏情况下的行为更重要，但也有一个更微妙的原因，即单纯形算法在某种意义上提供更多信息（例如，敏感信息更容易提取）。

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

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

对位集的访问将保证持续访问。就时间复杂度而言，是最优的。从理论和实践的角度来看（它是 O(1)，具有极低的常量开销）。

不过，您可能更喜欢第二种解决方案。特别是如果您希望列入黑名单的整数数量非常少，因为这样会提高内存效率。

即使你不为内存稀缺的嵌入式系统开发，我也可以将 1,000,000 的任意限制增加到 1,000,000,000,000，并提出相同的论点。那么bitset将需要大约125G的内存。保证 O(1) 的最坏情况复杂度可能无法说服您的老板为您提供如此强大的服务器。

在这里，我强烈希望二分搜索 (O(log n)) 或二叉树 (O(log n)) 而不是 O(1) 位集。并且可能，最坏情况复杂度为 O(n) 的哈希 table 将在实践中击败所有这些。

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

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

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

常见示例： 哈希表，"array lists" 的扩展（a.k.a。动态大小 arrays/vectors）。

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

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

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

将我的 2 美分放入：

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

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

在需要确定上限的实时情况下，您会 select 例如堆排序而不是快速排序，因为堆排序的平均行为也是最坏情况下的行为。

在 n 有界且 O(1) 算法的常量乘数高于 log(n) 上的界限的任何点。 例如，将值存储在 a hashset 是 O(1)，但可能需要对哈希函数进行昂贵的计算。如果可以简单地比较数据项（相对于某种顺序）并且 n 的界限使得 log n 明显小于任何一项的哈希计算，那么存储在平衡二叉树中可能比存储在一个哈希集。

简单地说：因为系数——与设置、存储和该步骤的执行时间相关的成本——对于较小的 big-O 问题可能比较大的问题大得多。 Big-O 只是算法 可扩展性.

的衡量标准

考虑黑客词典中的以下示例，提出依赖于 Multiple Worlds Interpretation of Quantum Mechanics 的排序算法：

  1. Permute the array randomly using a quantum process,
  2. If the array is not sorted, destroy the universe.
  3. All remaining universes are now sorted [including the one you are in].

（来源：http://catb.org/~esr/jargon/html/B/bogo-sort.html）

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

然而，在大多数情况下，我们可能不想冒 Multiple Worlds 可能不正确的风险，更不用说实施步骤 2 的行为仍然是 "left as an exercise for the reader".

  1. 当 O(1) 中的“1”工作单元相对于 O(log n) 中的工作单元非常高并且预期的集合大小很小时。例如，如果只有两个或三个项目，计算字典哈希码可能比迭代数组慢。

或

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

添加到已经很好的 answers.A 实际示例中是哈希索引与 postgres 数据库中的 B 树索引。

哈希索引形成哈希table索引来访问磁盘上的数据，而btree顾名思义使用B树数据结构。

在 Big-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)算法.那么你就不必使用 O(1) 算法
  2. 当O(1)需要很多你无法提供的内存，而O(lgN)的时间可以接受。

安全应用程序通常是这种情况，我们希望设计的问题的算法故意很慢，以阻止某人过快地获得问题的答案。

这里有几个例子。

  • 密码散列有时会任意慢，以便更难通过暴力猜测密码。这个 Information Security post 有一个关于它的要点（以及更多）。
  • Bit Coin 使用计算机网络解决一个可控的缓慢问题，以便 "mine" 硬币。这使得货币可以由集体系统以可控的速度开采。
  • 非对称密码（如RSA）旨在使没有密钥的解密故意变慢，以防止没有私钥的其他人破解加密。这些算法旨在希望在 O(2^n) 时间内破解，其中 n 是密钥的位长度（这是蛮力）。

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

有很多好的答案，其中一些提到常数因子、输入大小和内存限制，以及许多其他原因，复杂性只是一个理论指导，而不是 end-all 确定 real-world 适合给定目的或速度。

这里有一个简单、具体的例子来说明这些想法。比方说我们想弄清楚一个数组是否有重复的元素。天真的二次方法是写一个嵌套循环：

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]));

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

然而，事实证明“朴素”的二次方法有很多 Big O 无法解释的地方：

  • 没有额外的内存使用
  • 没有堆内存分配（没有new）
  • 临时Set
    • 没有垃圾回收
  • 提前救助；在已知重复项可能位于数组前面的情况下，无需检查多个元素。

如果我们的用例是在有界小数组上，我们有一个 resource-constrained 环境 and/or 其他已知的 common-case 属性允许我们通过基准测试确定嵌套循环在我们特定的工作量，这可能是个好主意。

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

这不可避免地会导致 maintainability/readability/elegance 和其他“软”成本。在这种情况下，new Set() 方法可能更具可读性，但通常（如果不是更频繁的话）实现更好的复杂性需要付出巨大的工程成本。

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

我还没有看到其他一些示例：

  • 在 real-time 环境中，例如 resource-constrained 嵌入式系统，有时会牺牲复杂性（通常与缓存和内存或调度相关）以避免偶尔发生 worst-case 惩罚不能容忍，因为它们可能会引起抖动。
  • 同样在嵌入式编程中，代码本身的大小也会造成缓存压力，影响内存性能。如果算法的复杂性较差，但会节省大量代码，这可能是选择它而不是理论上更好的算法的原因。
  • 在大多数递归线性算法（如快速排序）的实现中，当数组足够小时，通常会调用二次排序算法（如插入排序），因为在越来越小的数组上递归函数调用的开销往往超过嵌套的成本循环。插入排序在 mostly-sorted 数组上也很快，因为内部循环不会 运行 太多。 在迁移到 Timsort 之前在 Chrome 的 V8 引擎的旧版本中讨论了这一点。