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

Question

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

你有什么例子吗？

Answer 1

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

• 大多数时候，较低的大 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) 算法并不重要。
• 有时小写时间复杂度的优势真的可以忽略不计。对于 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) 空间。问题是您可以等待很长时间，但非常怀疑您能否找到足够大的 RAM 来将其用于您的算法
• 并行化是我们分布式世界中的一个很好的特性。有些算法很容易并行化，有些算法根本无法并行化。有时，在 1000 台复杂度更高的商用机器上运行算法比使用一台复杂度略高的机器更有意义。
• 在某些地方(安全)，复杂性可能是一个要求。没有人希望拥有一种哈希算法可以非常快地哈希(因为这样其他人可以更快地暴力破解你)
• 虽然这与switch的复杂度无关，但是一些安全函数应该写成prevent timing attack的方式.它们大多处于相同的复杂度级别，但经过修改后总是需要更坏的情况才能做某事。一个例子是比较字符串是否相等。在大多数应用程序中，如果第一个字节不同，则快速中断是有意义的，但在安全方面，您仍将等待最后告诉坏消息。
• 有人为较低复杂度的算法申请了专利，公司使用较高复杂度的算法比付费更经济。
• 一些算法可以很好地适应特定情况。例如，插入排序的平均时间复杂度为 O(n^2)，比快速排序或合并排序差，但作为 online algorithm它可以在收到值列表(作为用户输入)时对值列表进行高效排序，而大多数其他算法只能对完整的值列表进行有效操作。