有没有什么情况下，你更喜欢更高的大O时间复杂度algorithm而不是更低的？
是否有任何情况下你会更喜欢O(log n)时间复杂度到O(1)时间复杂度？ 或者O(n)到O(log n) ？
你有什么例子吗？
可能有很多理由select比较低的较大O时间复杂度的algorithm：
- 大多数情况下，较低的大O复杂度难以实现，需要熟练的实施，大量的知识和大量的testing。
- 大O隐藏了一个常量的细节 ：从大O的angular度来看，在
10^5中执行的algorithm比1/10^5 * log(n)（O(1)和O(log(n)）更好，但是对于最合理的n，第一个将会performance得更好，例如matrix乘法的最佳复杂度是O(n^2.373)但是这个常数是如此之高以至于没有（据我所知）计算库使用它。 - 当你计算一些大的东西时，大O是有意义的。 如果您需要对三个数字进行sorting，则使用
O(n*log(n))还是O(n^2)algorithm确实很less。 - 有时小写时间复杂度的优势可以忽略不计。 例如，有一个数据结构探戈树 ，它给出一个
O(log log N)时间复杂度来find一个项目，但是也有一个二叉树在O(log n)find相同的结果。 即使是大数目的n = 10^20这个差别也是微不足道的。 - 时间复杂性并不是一切。 设想一个algorithm运行在
O(n^2)并且需要O(n^2)内存。 当n不是很大时，可能比O(n^3)时间和O(1)空间更可取。 问题是你可以等待很长时间，但是非常怀疑你可以find一个足够大的RAM来和你的algorithm一起使用 - 并行化在我们的分布式世界中是一个很好的特性。 有一些algorithm很容易并行化，有些algorithm根本不能并行化。 有时在1000台商品机器上运行一个algorithm比在一台机器上复杂度稍高的情况下要复杂得多。
-
在一些地方（安全）复杂性可能是一个要求。没有人希望有一个哈希algorithm，可以快速哈希（因为那么其他人可以暴躁你的方式更快） - 虽然这与复杂性的切换没有关系，但是一些安全function应该以防止计时攻击的方式写入。 他们大多停留在相同的复杂性类别中，但被修改的方式总是会让事情变得更糟。 一个例子是比较string是否相等。 在大多数应用程序中，如果第一个字节不同，就可以快速破解，但是在安全性方面，您仍然会等待最后的结果来告诉坏消息。
- 有人获得了较低复杂度algorithm的专利，而公司使用更高的复杂性比付钱更经济。
- 一些algorithm适应特定的情况。 例如，插入sorting的平均时间复杂度为
O(n^2)，比快速sorting或合并sorting更差，但是作为在线algorithm，它可以高效地对接收到的值列表（作为用户input）进行sorting其他algorithm只能在一个完整的值列表上有效地运行。
总是有隐藏的常量，在O （log n ）algorithm中可以更低。 因此，在实际数据的实践中它可以更快地工作。
还有空间问题（例如在烤面包机上运行）。
还有开发人员的时间关注–O （log n ）可能是1000×易于实现和validation。
我很惊讶没有人提到内存绑定的应用程序。
由于其复杂性（即O （1）< O （log n ））或者因为复杂度前面的常量较小（即2 n 2 <6 n 2 ），所以可能有一个浮点运算较less的algorithm。 。 无论如何，如果更低的FLOPalgorithm是更多的内存限制，你可能仍然更喜欢FLOPalgorithm。
我所说的“内存限制”是指你经常访问不断超速的数据。 为了获取这些数据，你必须将内存从实际的内存空间转移到caching中，然后才能对其进行操作。 这个提取步骤通常非常慢 – 比您的操作本身慢得多。
因此，如果你的algorithm需要更多的操作（但是这些操作是在已经在caching中的数据上执行的[因此不需要提取]），它仍然会以较less的操作超出你的algorithm（必须在超出-cache数据[因此需要获取]）在实际的时间墙上。
在数据安全性受到关注的情况下，如果更复杂的algorithm对定时攻击具有更好的抵抗力，则更复杂的algorithm可能优于不太复杂的algorithm。
Alistra钉了它，但没有提供任何例子，所以我会的。
你有一个商店销售的10,000个UPC代码列表。 10位UPC，价格的整数（以便士为单位）以及收据描述的30个字符。
O（log N）方法：你有一个sorting列表。 如果ASCII为44个字节，如果是Unicode则为84个 或者，对待UPC作为int64，你得到42和72字节。 10,000条logging – 在最高的情况下，您正在查看一下存储容量的兆字节。
O（1）方法：不要存储UPC，而是使用它作为数组入口。 在最低的情况下，你正在寻找几乎三分之一的存储容量。
您使用哪种方法取决于您的硬件。 在大多数合理的现代configuration中，您将使用log N方法。 如果由于某种原因，你运行的RAM很短，但你有大量的存储空间的环境下运行，我可以想象第二种方法是正确的答案。 磁盘上三分之一的TB是没有什么大不了的，在一个磁盘探测器中获取数据是值得的。 简单的二进制方法平均需要13次。 （但是请注意，通过集中您的密钥，您可以将其降低到保证的3次读取，实际上您将caching第一个密钥。）
考虑一个红黑树。 它可以访问，search，插入和删除O(log n) 。 比较一个有O(1)访问权的数组，其余的操作都是O(n) 。
因此，在我们插入，删除或search应用程序的情况下，如果只访问这两个结构，我们更喜欢红黑树。 在这种情况下，你可能会说我们更喜欢红黑树的O(log n)访问时间。
为什么？ 因为访问不是我们最关心的问题。 我们正在做一个权衡：我们的应用程序的性能受到这个以外因素的影响更大。 我们允许这个特定的algorithm受到影响，因为我们通过优化其他algorithm来获得大的增益。
所以你的问题的答案就是这样： 当algorithm的增长速度不是我们想要优化的时候 ，当我们想要优化别的东西的时候 。 所有其他答案都是这样的特例。 有时我们会优化其他操作的运行时间。 有时我们会优化内存。 有时我们会优化安全性。 有时我们会优化可维护性。 有时我们会优化开发时间。 即使最重要的常数足够低，但是如果知道algorithm的增长率不是对运行时间的最大影响，那么运行时间是最优化的。 （如果你的数据集超出了这个范围，你会优化algorithm的增长速度，因为它最终会支配这个常量。）一切都有成本，而且在很多情况下，我们用更高的增长率换取成本algorithm来优化别的东西。
是。
在真实情况下，我们运行了一些testing，使用短和长的string键进行表查找。
我们使用了一个std::map ，一个std::unordered_map和一个散列，在string的长度上最多抽样10次（我们的键往往是guid-like，所以这是体面的），一个散列字符（在理论上减less了碰撞），一个未sorting的向量，我们做一个==比较，（如果我没记错的话）一个未sorting的向量，我们也存储一个散列，首先比较散列，然后比较字符。
这些algorithm的范围从O(1) （unordered_map）到O(n) （线性search）。
对于中等大小的N，O（n）通常击败O（1）。 我们怀疑这是因为基于节点的容器需要我们的计算机在内存中更多地跳转，而基于线性的容器却没有。
O(lg n)在两者之间存在。 我不记得它是如何做的。
性能差异不是那么大，在较大的数据集上，基于散列的performance要好得多。 所以我们坚持使用基于散列的无序映射。
在实践中，对于合理大小的n， O(lg n)是O(1) 。 如果你的计算机只有你的表中有40亿个条目的空间，那么O(lg n)就是32以上。 （lg（2 ^ 32）= 32）（在计算机科学中，lg是基于2的log的简写）。
实际上，lg（n）algorithm比O（1）algorithm慢，这并不是因为对数增长因子，而是因为lg（n）部分通常意味着algorithm存在一定程度的复杂度，并且复杂度增加了比从lg（n）项的任何“增长”更大的常数因子。
然而，复杂的O（1）algorithm（如哈希映射）可以很容易地具有相似或更大的常数因子。
并行执行algorithm的可能性。
我不知道类O(log n)和O(1)是否有一个例子，但是对于一些问题，当algorithm更容易并行执行时，select一个复杂度较高的类。
一些algorithm不能并行化，但是复杂度较低。 考虑另一种达到相同结果并且可以容易地并行化的algorithm，但是具有更高的复杂度级别。 在一台机器上执行时，第二种algorithm速度较慢，但在多台机器上执行时，实际执行时间越来越低，而第一种algorithm速度越来越慢。
假设您正在embedded式系统上实施黑名单，其中0到1,000,000之间的数字可能被列入黑名单。 这给你两个可能的select：
- 使用一百万位的位
- 使用黑名单整数的有序数组，并使用二进制search来访问它们
访问位组将保证不断的访问。 在时间复杂度方面，这是最优的。 无论从理论还是从实践的angular度来看（这是O（1），具有非常低的恒定开销）。
不过，你可能想要更喜欢第二个解决scheme。 特别是如果你期望黑名单整数的数量非常小，因为它会更有效率的记忆。
而且即使你不开发一个内存稀缺的embedded式系统，我也可以增加100万到1,000亿的任意限制，并作相同的论证。 那么这个bitset将需要大约125G的内存。 保证最坏情况下O（1）的复杂性可能不能说服你的老板为你提供如此强大的服务器。
在这里，我强烈希望O（1）位集合上的二进制search（O（log n））或二叉树（O（log n））。 而且，最坏情况下O（n）的哈希表在实践中将会击败所有这些哈希表。
我的答案在这里，随机matrix的所有行的快速随机加权select是一个例子，当m不是太大时，复杂度为O（m）的algorithm比复杂度为O（log（m））的algorithm快。
人们已经回答了你的确切问题，所以我会解决一个稍微不同的问题，人们可能真的想到这里来想。
很多“O（1）时间”的algorithm和数据结构实际上只是预期的 O（1）时间，这意味着它们的平均运行时间是O（1），可能只有在一定的假设下。
常见的例子：哈希表，扩展“数组列表”（又名dynamic大小的数组/向量）。
在这种情况下，您可能更喜欢使用时间保证为对数绝对有限的数据结构或algorithm，即使它们平均可能performance更差。
因此，一个例子可能是一个平衡二叉search树，它的运行时间平均更差，但在最坏的情况下更好。
一个更一般的问题是，即使g(n) << f(n)为n趋向于无穷大，是否存在某个O(f(n))algorithm优先于O(g(n))algorithm的情况。 正如其他人已经提到的，在f(n) = log(n)和g(n) = 1的情况下，答案显然是“是”。 甚至在f(n)是多项式但g(n)是指数的情况下有时也是。 一个着名而又重要的例子就是求解线性规划问题的单纯形algorithm 。 在二十世纪七十年代，它被certificate是O(2^n) 。 因此，更糟糕的行为是不可行的。 但是 – 它的平均案例行为是非常好的，即使是对数以万计的变数和约束的实际问题。 在20世纪80年代，线性规划的多项式时间algorithm（如Karmarkar的内点algorithm ）被发现，但30年后，单纯形algorithm似乎仍然是selectalgorithm（除了某些非常大的问题）。 这是明显的原因，平均情况往往比坏情况行为更重要，但也有一个更微妙的原因，单纯的algorithm在某种意义上是更多的信息（如灵敏度信息更容易提取）。
把我的2美分：
当algorithm运行在特定的硬件环境中时，有时会select更糟糕的复杂algorithm来代替更好的algorithm。 假设我们的O（1）algorithm非顺序地访问一个非常大的固定大小数组的每个元素来解决我们的问题。 然后把这个arrays放在机械硬盘或者磁带上。
在这种情况下，O（logn）algorithm（假设它顺序访问磁盘）变得更有利。
使用O（log（n））algorithm而不是O（1）algorithm的许多其他答案已经被忽略了：不变性。 哈希映射具有O（1）置入和获取，假设哈希值分配良好，但是它们需要可变状态。 不变的树映射具有O（log（n））放置和获取，这是渐近较慢。 然而，不变性可能足够有价值，以弥补更差的性能，并且在需要保留多个版本的地图的情况下，不变性允许您避免必须复制地图，即O（n），因此可以改善性能。
简单地说：因为系数（与设置，存储和执行时间相关的成本）可能比大型问题要大得多，而大型问题要小一些。 Big-O只是algorithm可扩展性的一个度量。
考虑以下“黑客词典”中的例子，提出了一个依赖量子力学多重解释的sortingalgorithm：
- 使用量子过程随机排列arrays，
- 如果数组未被sorting，则销毁该宇宙。
- 现在所有剩下的宇宙都被分类了[包括你所在的那个宇宙]。
（来源： http : //catb.org/~esr/jargon/html/B/bogo-sort.html ）
请注意，该algorithm的大O是O(n) ，它击败了通用项目上的所有已知的sortingalgorithm。 线性步骤的系数也非常低（因为它只是一个比较，而不是交换，线性完成）。 事实上，类似的algorithm可以用来解决NP和co-NP在多项式时间中的任何问题，因为可以使用量子过程来生成每个可能的解（或者可能的certificate没有解），然后在多项式时间。
但是，在大多数情况下，我们可能不想冒“多世界”可能不正确的风险，更不用说实施第二步的行为仍然是“留给读者的一个练习”。
在n有界且O（1）algorithm的常数倍数高于log（n）上的界限的任何时刻。 例如，将值存储在哈希集中是O（1），但可能需要昂贵的哈希函数计算。 如果可以对数据项进行平凡的比较（相对于某个顺序），并且n上的界限使得log n明显小于任何一个项上的散列计算，则存储在平衡二叉树中可能比存储在一个哈希集。
在需要稳定上限的实时情况下，您将select例如heapsort而不是Quicksort，因为heapsort的平均行为也是其最坏情况行为。
添加到已经很好的答案中。一个实际的例子是postgres数据库中的Hash索引与B-tree索引。
散列索引形成一个散列表索引来访问磁盘上的数据，同时btree顾名思义使用Btree数据结构。
在大O时间，这些是O（1）对O（logN）。
在postgres中，目前不鼓励哈希指数，因为在现实生活中，特别是在数据库系统中，实现无碰撞哈希非常困难（可能会导致O（N）最差的情况），因此更加困难他们崩溃安全（称为写在前面的日志 – WAL在postgres中）。
这种折衷是在这种情况下进行的，因为O（logN）对于索引是足够好的，并且实现O（1）非常困难，时间差别也不会有实际意义。
当n很小时， O(1)一直很慢。
- 当O（1）中的“1”工作单位相对于O（log n）中的工作单位非常高时，预期的设定尺寸是小的。 例如，如果只有两个或三个项目，则计算Dictionary散列码的速度可能会慢于迭代数组的速度。
要么
- 当O（1）algorithm中的存储器或其他非时间资源需求相对于O（log n）algorithm来说特别大时。
- 当重新devise一个程序时，程序被发现用O（1）而不是O（lgN）来优化，但是如果它不是这个程序的瓶颈，并且很难理解O（1）alg。 那么你就不必使用O（1）algorithm
- 当O（1）需要很多内存时，你不能提供，而O（lgN）的时间是可以接受的。
安全应用程序通常是这种情况，我们要devisealgorithm速度缓慢的问题，以阻止某人快速获得问题的答案。
这里有几个例子，我的头顶。
- 密码散列有时会变得任意慢，以致难以通过暴力猜测密码。 这个信息安全的post有一个关于它的重点（以及更多）。
- 比特硬币使用一个可控缓慢的问题来解决一个计算机networking，以便“挖掘”硬币。 这使得货币可以由集体系统以受控制的速度开采。
- 非对称密码（如RSA ）的目的是在没有密钥的情况下进行解密，以防止没有私钥的人破解encryption。 algorithm被devise成在希望
O(2^n)时间被破解，其中n是密钥的比特长度（这是蛮力）。
在CS的其他地方，在最坏的情况下，快速sorting是O(n^2) ，但一般情况下是O(n*log(n)) 。 因此，在分析algorithm效率时，“大O”分析有时并不是您唯一关心的事情。
