在任何情况下，您是否希望 O(log n) 时间复杂度达到 O(1) 时间复杂度？或 O(n) 到 O(log n) ？
O(log n)
O(1)
O(n)
你有什么例子吗？
我很惊讶没有人提到过内存限制的应用程序 .
由于其复杂性（即O（1）<O（log n））或者因为复杂性前面的常数较小（即2n2 <6n2），可能存在具有较少浮点运算的算法 . 无论如何，如果较低的FLOP算法更受内存限制，您可能仍然更喜欢具有更多FLOP的算法 .
我所说的“内存限制”是指您经常访问经常超出缓存的数据 . 为了获取这些数据，您必须先将实际内存空间中的内存提取到缓存中，然后才能对其执行操作 . 这个提取步骤通常非常慢 - 比您的操作本身慢得多 .
因此，如果您的算法需要更多操作（但这些操作是在已经在缓存中的数据上执行的[因此不需要提取]），它仍然会以较少的操作（必须在外部执行）执行算法 . -cache数据[因此需要获取]）就实际的壁时而言 .
考虑一棵红黑树 . 它具有 O(log n) 的访问，搜索，插入和删除功能 . 与数组进行比较，该数组可以访问 O(1) ，其余操作是 O(n) .
因此，给定一个应用程序，我们插入，删除或搜索比我们访问更频繁，并且只在这两个结构之间进行选择，我们更喜欢红黑树 . 在这种情况下，您可能会说我们更喜欢红黑树更加繁琐 O(log n) 访问时间 .
为什么？因为访问不是我们最重要的考虑因素 . 我们正在进行权衡：我们的应用程序的性能受到除此之外的因素的更大影响 . 我们允许这种特定算法遭受性能，因为我们通过优化其他算法来获得大量增益 .
所以问题的答案就是： when the algorithm's growth rate isn't what we want to optimize ，当我们想要优化其他东西时 . 所有其他答案都是特殊情况 . 有时我们会优化其他操作的运行时间 . 有时我们会优化内存 . 有时我们会优化安全性 . 有时我们会优化可维护性 . 有时我们会优化开发时间 . 当您知道算法的增长率对运行时间的影响不是最大时，即使最重要的常数足够低也可以优化运行时间 . （如果您的数据集超出此范围，您将优化算法的增长率，因为它最终将主导常量 . ）一切都有成本，在许多情况下，我们交易的成本更高的成本算法优化别的东西 .
一个更普遍的问题是，是否有人会更喜欢 O(f(n)) 算法到 O(g(n)) 算法，即使 g(n) << f(n) 为 n 趋于无穷大 . 正如其他人已经提到的那样，在 f(n) = log(n) 和 g(n) = 1 的情况下，答案显然是"yes" . 即使在 f(n) 是多项式但 g(n) 是指数的情况下，有时也是如此 . 一个着名而重要的例子是用于解决线性规划问题的Simplex Algorithm . 在20世纪70年代，它被证明是 O(2^n) . 因此，其糟糕的行为是不可行的 . 但是 - 它的平均案例行为非常好，即使对于成千上万个变量和约束的实际问题也是如此 . 在20世纪80年代，人们发现了用于线性规划的多项式时间算法（例如Karmarkar's interior-point algorithm），但30年后，单纯形算法似乎仍然是首选算法（除了某些非常大的问题） . 这是因为显而易见的原因，平均情况行为通常比最坏情况行为更重要，但也有一个更微妙的原因，即单纯形算法在某种意义上更具信息性（例如灵敏度信息更容易提取） .
O(f(n))
O(g(n))
g(n) << f(n)
n
f(n) = log(n)
g(n) = 1
f(n)
g(n)
O(2^n)
简单地说：因为系数 - 与设置，存储和该步骤的执行时间相关的成本 - 可以通过较小的大O问题比使用较大的问题大得多 . Big-O只是算法可扩展性的衡量标准 .
考虑以下来自Hacker's Dictionary的示例，提出依赖于Multiple Worlds Interpretation of Quantum Mechanics的排序算法：
使用量子过程随机置换数组，如果数组未排序，则销毁Universe . 所有剩余的宇宙现在都已排序[包括您所在的宇宙] .
（来源：http://catb.org/~esr/jargon/html/B/bogo-sort.html）
请注意，此算法的big-O是 O(n) ，它击败了迄今为止在通用项目上的任何已知排序算法 . 线性步长的系数也非常低（因为它只是比较，而不是交换，线性完成） . 事实上，类似的算法可用于解决两者中的任何问题NP和co-NP在多项式时间内，因为可以使用量子过程生成每个可能的解（或可能证明没有解），然后在多项式时间内验证 .
但是，在大多数情况下，我们可能不希望承担多个世界可能不正确的风险，更不用说执行第2步的行为仍“留给读者” .
Alistra钉了它，但没有提供任何例子，所以我会 .
您有一个10,000个UPC代码列表，用于商店销售的商品代码 . 10位UPC，价格整数（便士价格）和收据描述的30个字符 .
O（log N）方法：您有一个排序列表 . 如果是ASCII则为44字节，如果是Unicode则为84或者，将UPC视为int64，得到42和72字节 . 10,000条记录 - 在最高的情况下，您看起来有点不到一兆字节的存储空间 .
O（1）方法：不存储UPC，而是将其用作数组的入口 . 在最低的情况下，您正在查看几乎三分之一的TB存储空间 .
您使用哪种方法取决于您的硬件 . 在大多数任何合理的现代配置中，您将使用log N方法 . 我可以想象第二种方法是正确的答案，如果由于某种原因你在一个RAM非常短但你有大量存储空间的环境中运行 . 磁盘上三分之一的TB是没什么大不了的，将数据放在一个磁盘探测器中是值得的 . 简单的二进制方法平均需要13个 . （但是，请注意，通过对键进行聚类，可以将其保证为3次读取，实际上，您将缓存第一个 . ）
是 .
在实际情况中，我们使用短字符串键和长字符串键进行了一些表查找 .
我们使用 std::map ， std::unordered_map ，哈希在字符串长度上最多采样10次（我们的键往往像guid一样，所以这很不错），并且哈希对每个字符进行采样（理论上减少了冲突） ），一个未分类的向量，我们进行 == 比较，并且（如果我没记错的话）一个未分类的向量，我们也存储一个哈希，首先比较哈希值，然后比较字符 .
std::map
std::unordered_map
==
这些算法的范围从 O(1) （unordered_map）到 O(n) （线性搜索） .
对于适度大小的N，通常O（n）击败O（1） . 我们怀疑这是因为基于节点的容器需要我们的计算机更多地在内存中跳转，而基于线性的容器则没有 .
O(lg n) 存在于两者之间 . 我不记得它是怎么做的 .
O(lg n)
性能差异并不大，在较大的数据集上，基于散列的数据集表现得更好 . 所以我们坚持使用基于哈希的无序映射 .
实际上，对于合理大小的n， O(lg n) 是 O(1) . 如果您的计算机在表中只有40亿个条目，那么 O(lg n) 将被 32 限制在上方 . （lg（2 ^ 32）= 32）（在计算机科学中，lg是基于日志的简写2） .
32
在实践中，lg（n）算法比O（1）算法慢，不是因为对数增长因子，而是因为lg（n）部分通常意味着算法存在一定程度的复杂性，并且复杂性增加了比lg（n）项中的任何“增长”更大的常数因子 .
但是，复杂的O（1）算法（如哈希映射）很容易产生类似或更大的常数因子 .
使用O（log（n））算法代替O（1）算法有一个很好的用例，许多其他答案都忽略了这种算法：不变性 . 哈希映射具有O（1）个put和gets，假设散列值的分布很好，但它们需要可变状态 . 不可变树映射具有O（log（n））puts和gets，它渐近地变慢 . 但是，不变性可能足以弥补性能的下降，并且在需要保留多个版本的映射的情况下，不变性允许您避免必须复制映射，即O（n），因此可以改进性能 .
在数据安全性受到关注的情况下，如果更复杂的算法对timing attacks具有更好的抵抗力，则更复杂的算法可能优于不太复杂的算法 .
在需要坚定上限的实时情况下，您可以选择例如因为Heapsort的平均行为也是最糟糕的行为，因此是一个heapsort而不是Quicksort .
把我的2美分投入：
当算法在某个硬件环境上运行时，有时会选择更复杂的算法来代替更好的算法 . 假设我们的O（1）算法非顺序地访问一个非常大的固定大小数组的每个元素来解决我们的问题 . 然后将该阵列放在机械硬盘驱动器或磁带上 .
在这种情况下，O（logn）算法（假设它顺序访问磁盘）变得更有利 .
At any point when n is bounded and the constant multiplier of O(1) algorithm is higher than the bound on log(n). 例如，在散列集中存储值是O（1），但可能需要昂贵的散列函数计算 . 如果数据项可以是平凡的比较（关于某些顺序）并且n上的界限使得log n明显小于任何一个项目上的散列计算，然后存储在 balancer 二叉树中可能比存储在散列集中更快 .
对于我们想要设计问题的安全应用程序通常就是这种情况，这些问题的算法目的很慢，以阻止某人过快地获得问题的答案 .
这里有几个例子 .
密码散列有时会任意慢，以便更难以通过强力猜测密码 . 这个Information Security post有一个关于它的要点（以及更多） .
Bit Coin使用一个可控制的慢速问题，为计算机网络解决，以便"mine"硬币 . 这允许集体系统以受控速率开采货币 .
非对称密码（如RSA）旨在进行解密而不会故意减慢密钥，以防止没有私钥的其他人破解加密 . 这些算法被设计为希望 O(2^n) 时间被破解，其中 n 是密钥的位长（这是强力的） .
在CS的其他地方，在最坏的情况下，快速排序是 O(n^2) ，但在一般情况下是 O(n*log(n)) . 因此，在分析算法效率时，"Big O"分析有时并不是您唯一关心的问题 .
O(n^2)
O(n*log(n))
当 n 很小时， O(1) 一直很慢 .
重新设计程序时，发现程序用O（1）而不是O（lgN）优化，但如果它很难理解O（1）alg . 那么你就不必使用O（1）算法
当O（1）需要大量无法提供的内存时，可以接受O（lgN）的时间 .
假设您正在嵌入式系统上实施黑名单，其中0到1,000,000之间的数字可能会被列入黑名单 . 这留下了两个可能的选择：
使用1,000,000位的位集
使用已列入黑名单的排序数组，并使用二进制搜索来访问它们
访问bitset将保证持续访问 . 就时间复杂性而言，它是最佳的 . 从理论和实际的角度来看（O（1）具有极低的恒定开销） .
不过，您可能希望更喜欢第二种解决方案 . 特别是如果你期望黑名单整数的数量非常小，因为它会更有效 .
即使你没有为内存稀缺的嵌入式系统开发，我也可以增加1,000,000到1,000,000,000,000的任意限制，并提出相同的论点 . 然后bitset将需要大约125G的内存 . 保证O（1）的最坏情况复杂性可能无法说服你的老板为你提供如此强大的服务器 .
在这里，我强烈希望在O（1）位集上进行二进制搜索（O（log n））或二叉树（O（log n）） . 并且可能的是，具有O（n）的最坏情况复杂度的哈希表将在实践中击败所有这些哈希表 .
可以并行执行算法 .
我不知道是否有类 O(log n) 和 O(1) 的示例，但是对于某些问题，当算法更容易并行执行时，您选择具有更高复杂度类的算法 .
有些算法不能并行化，但复杂度很低 . 考虑另一种算法，它可以实现相同的结果并且可以轻松并行化，但具有更高的复杂性等级 . 在一台机器上执行时，第二种算法较慢，但在多台机器上执行时，实际执行时间越来越低，而第一种算法无法加速 .
始终存在隐藏常量，其可以在O（log n）算法上更低 . 因此，它可以在实践中更快地用于实际数据 .
还存在空间问题（例如在烤面包机上运行） .
还有开发人员时间问题 - O（log n）可能更容易实现和验证1000 .
要么
人们已经回答了你的确切问题，所以我会解决一个人们在来这里时可能会想到的一个稍微不同的问题 .
很多"O(1) time"算法和数据结构实际上只需要 expected O（1）时间，这意味着它们的平均运行时间为O（1），可能只在某些假设下 .
Common examples: 哈希表，扩展"array lists"（a.k.a . 动态大小的数组/向量） .
在这种情况下，您可能更喜欢使用保证时间的数据结构或算法 absolutely 以对数方式界定，即使它们平均表现较差 .因此，一个例子可能是 balancer 的二叉搜索树，其运行时间平均更差，但在最坏的情况下更好 .
添加到已经很好的答案 . 一个实际的例子是postgres数据库中的哈希索引与B树索引 .
散列索引形成哈希表索引以访问磁盘上的数据，而btree顾名思义使用Btree数据结构 .
在Big-O时间中，这些是O（1）vs O（logN） .
由于在现实生活中，特别是在数据库系统中，哈希索引目前不受欢迎，因此在没有冲突的情况下实现散列是非常困难的（可能导致O（N）最坏情况的复杂性）并且因此，更难以制作他们崩溃安全（称为提前写入记录 - 在postgres中的WAL） .
这种权衡是在这种情况下进行的，因为O（logN）对于索引来说足够好并且实现O（1）非常困难并且时间差异并不重要 .
可能有许多理由偏好具有较高O时间复杂度的算法而不是较低的算法：
大部分时间，较低的大O复杂度难以实现，需要熟练的实施，大量的知识和大量的测试 .
big-O隐藏了关于常量的详细信息：在 10^5 中执行的算法从大O视角比 1/10^5 * log(n) （ O(1) vs O(log(n) ）更好，但对于最合理的 n ，第一个将表现更好 . 例如，矩阵乘法的最佳复杂度是 O(n^2.373) 但是常量是如此之高，以至于没有（据我所知）计算库使用它 .当你计算一些大的东西时，
10^5
1/10^5 * log(n)
O(log(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(log log N)
n = 10^20
时间复杂并非一切 . 想象一下在 O(n^2) 中运行并且需要 O(n^2) 内存的算法 . 当n不是很大时，它可能优于 O(n^3) 时间和 O(1) 空间 . 问题是你可以等待很长时间，但我很怀疑你能找到一个足够大的RAM来与你的算法一起使用它
O(n^3)
并行化是我们分布式世界的一个很好的特性 . 有些算法很容易并行化，有些算法根本没有并行化 . 有时，在1000台商用机器上运行算法比使用复杂性稍高的一台机器更复杂 .
在某些地方（安全），复杂性可能是必需的 . 没有人想要一个可以快速散列的哈希算法（因为那时其他人可以更快地强制你）
虽然这与切换复杂性无关，但是某些安全功能应该以prevent timing attack的方式编写 . 它们大多数都停留在相同的复杂性类别中，但是以一种总是需要更糟糕的方式进行修改 . 一个例子是比较字符串是否相等 . 在大多数应用程序中，如果第一个字节不同，则快速断开是有意义的，但在安全性方面，您仍然会等待最终告诉坏消息 .
有人为低复杂度算法申请了专利，对于公司来说，使用更高的复杂性而不是付钱更为经济 .
一些算法很好地适应特定情况 . 例如，插入排序的平均时间复杂度为 O(n^2) ，比quicksort或mergesort差，但作为online algorithm，它可以在接收到的值（作为用户输入）时有效地对值列表进行排序，其中大多数其他算法只能有效地运行在完整的值列表上 .
我的答案Fast random weighted selection across all rows of a stochastic matrix是一个例子，当 m 不是太大时，复杂度为O（m）的算法比复杂度为O（log（m））的算法要快 .
m
22 回答
我很惊讶没有人提到过内存限制的应用程序 .
由于其复杂性（即O（1）<O（log n））或者因为复杂性前面的常数较小（即2n2 <6n2），可能存在具有较少浮点运算的算法 . 无论如何，如果较低的FLOP算法更受内存限制，您可能仍然更喜欢具有更多FLOP的算法 .
我所说的“内存限制”是指您经常访问经常超出缓存的数据 . 为了获取这些数据，您必须先将实际内存空间中的内存提取到缓存中，然后才能对其执行操作 . 这个提取步骤通常非常慢 - 比您的操作本身慢得多 .
因此，如果您的算法需要更多操作（但这些操作是在已经在缓存中的数据上执行的[因此不需要提取]），它仍然会以较少的操作（必须在外部执行）执行算法 . -cache数据[因此需要获取]）就实际的壁时而言 .
考虑一棵红黑树 . 它具有
O(log n)的访问，搜索，插入和删除功能 . 与数组进行比较，该数组可以访问O(1)，其余操作是O(n).因此，给定一个应用程序，我们插入，删除或搜索比我们访问更频繁，并且只在这两个结构之间进行选择，我们更喜欢红黑树 . 在这种情况下，您可能会说我们更喜欢红黑树更加繁琐
O(log n)访问时间 .为什么？因为访问不是我们最重要的考虑因素 . 我们正在进行权衡：我们的应用程序的性能受到除此之外的因素的更大影响 . 我们允许这种特定算法遭受性能，因为我们通过优化其他算法来获得大量增益 .
所以问题的答案就是： when the algorithm's growth rate isn't what we want to optimize ，当我们想要优化其他东西时 . 所有其他答案都是特殊情况 . 有时我们会优化其他操作的运行时间 . 有时我们会优化内存 . 有时我们会优化安全性 . 有时我们会优化可维护性 . 有时我们会优化开发时间 . 当您知道算法的增长率对运行时间的影响不是最大时，即使最重要的常数足够低也可以优化运行时间 . （如果您的数据集超出此范围，您将优化算法的增长率，因为它最终将主导常量 . ）一切都有成本，在许多情况下，我们交易的成本更高的成本算法优化别的东西 .
一个更普遍的问题是，是否有人会更喜欢
O(f(n))算法到O(g(n))算法，即使g(n) << f(n)为n趋于无穷大 . 正如其他人已经提到的那样，在f(n) = log(n)和g(n) = 1的情况下，答案显然是"yes" . 即使在f(n)是多项式但g(n)是指数的情况下，有时也是如此 . 一个着名而重要的例子是用于解决线性规划问题的Simplex Algorithm . 在20世纪70年代，它被证明是O(2^n). 因此，其糟糕的行为是不可行的 . 但是 - 它的平均案例行为非常好，即使对于成千上万个变量和约束的实际问题也是如此 . 在20世纪80年代，人们发现了用于线性规划的多项式时间算法（例如Karmarkar's interior-point algorithm），但30年后，单纯形算法似乎仍然是首选算法（除了某些非常大的问题） . 这是因为显而易见的原因，平均情况行为通常比最坏情况行为更重要，但也有一个更微妙的原因，即单纯形算法在某种意义上更具信息性（例如灵敏度信息更容易提取） .简单地说：因为系数 - 与设置，存储和该步骤的执行时间相关的成本 - 可以通过较小的大O问题比使用较大的问题大得多 . Big-O只是算法可扩展性的衡量标准 .
考虑以下来自Hacker's Dictionary的示例，提出依赖于Multiple Worlds Interpretation of Quantum Mechanics的排序算法：
（来源：http://catb.org/~esr/jargon/html/B/bogo-sort.html）
请注意，此算法的big-O是
O(n)，它击败了迄今为止在通用项目上的任何已知排序算法 . 线性步长的系数也非常低（因为它只是比较，而不是交换，线性完成） . 事实上，类似的算法可用于解决两者中的任何问题NP和co-NP在多项式时间内，因为可以使用量子过程生成每个可能的解（或可能证明没有解），然后在多项式时间内验证 .但是，在大多数情况下，我们可能不希望承担多个世界可能不正确的风险，更不用说执行第2步的行为仍“留给读者” .
Alistra钉了它，但没有提供任何例子，所以我会 .
您有一个10,000个UPC代码列表，用于商店销售的商品代码 . 10位UPC，价格整数（便士价格）和收据描述的30个字符 .
O（log N）方法：您有一个排序列表 . 如果是ASCII则为44字节，如果是Unicode则为84或者，将UPC视为int64，得到42和72字节 . 10,000条记录 - 在最高的情况下，您看起来有点不到一兆字节的存储空间 .
O（1）方法：不存储UPC，而是将其用作数组的入口 . 在最低的情况下，您正在查看几乎三分之一的TB存储空间 .
您使用哪种方法取决于您的硬件 . 在大多数任何合理的现代配置中，您将使用log N方法 . 我可以想象第二种方法是正确的答案，如果由于某种原因你在一个RAM非常短但你有大量存储空间的环境中运行 . 磁盘上三分之一的TB是没什么大不了的，将数据放在一个磁盘探测器中是值得的 . 简单的二进制方法平均需要13个 . （但是，请注意，通过对键进行聚类，可以将其保证为3次读取，实际上，您将缓存第一个 . ）
是 .
在实际情况中，我们使用短字符串键和长字符串键进行了一些表查找 .
我们使用
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). 如果您的计算机在表中只有40亿个条目，那么O(lg n)将被32限制在上方 . （lg（2 ^ 32）= 32）（在计算机科学中，lg是基于日志的简写2） .在实践中，lg（n）算法比O（1）算法慢，不是因为对数增长因子，而是因为lg（n）部分通常意味着算法存在一定程度的复杂性，并且复杂性增加了比lg（n）项中的任何“增长”更大的常数因子 .
但是，复杂的O（1）算法（如哈希映射）很容易产生类似或更大的常数因子 .
使用O（log（n））算法代替O（1）算法有一个很好的用例，许多其他答案都忽略了这种算法：不变性 . 哈希映射具有O（1）个put和gets，假设散列值的分布很好，但它们需要可变状态 . 不可变树映射具有O（log（n））puts和gets，它渐近地变慢 . 但是，不变性可能足以弥补性能的下降，并且在需要保留多个版本的映射的情况下，不变性允许您避免必须复制映射，即O（n），因此可以改进性能 .
在数据安全性受到关注的情况下，如果更复杂的算法对timing attacks具有更好的抵抗力，则更复杂的算法可能优于不太复杂的算法 .
在需要坚定上限的实时情况下，您可以选择例如因为Heapsort的平均行为也是最糟糕的行为，因此是一个heapsort而不是Quicksort .
把我的2美分投入：
当算法在某个硬件环境上运行时，有时会选择更复杂的算法来代替更好的算法 . 假设我们的O（1）算法非顺序地访问一个非常大的固定大小数组的每个元素来解决我们的问题 . 然后将该阵列放在机械硬盘驱动器或磁带上 .
在这种情况下，O（logn）算法（假设它顺序访问磁盘）变得更有利 .
At any point when n is bounded and the constant multiplier of O(1) algorithm is higher than the bound on log(n). 例如，在散列集中存储值是O（1），但可能需要昂贵的散列函数计算 . 如果数据项可以是平凡的比较（关于某些顺序）并且n上的界限使得log n明显小于任何一个项目上的散列计算，然后存储在 balancer 二叉树中可能比存储在散列集中更快 .
对于我们想要设计问题的安全应用程序通常就是这种情况，这些问题的算法目的很慢，以阻止某人过快地获得问题的答案 .
这里有几个例子 .
密码散列有时会任意慢，以便更难以通过强力猜测密码 . 这个Information Security post有一个关于它的要点（以及更多） .
Bit Coin使用一个可控制的慢速问题，为计算机网络解决，以便"mine"硬币 . 这允许集体系统以受控速率开采货币 .
非对称密码（如RSA）旨在进行解密而不会故意减慢密钥，以防止没有私钥的其他人破解加密 . 这些算法被设计为希望
O(2^n)时间被破解，其中n是密钥的位长（这是强力的） .在CS的其他地方，在最坏的情况下，快速排序是
O(n^2)，但在一般情况下是O(n*log(n)). 因此，在分析算法效率时，"Big O"分析有时并不是您唯一关心的问题 .当
n很小时，O(1)一直很慢 .重新设计程序时，发现程序用O（1）而不是O（lgN）优化，但如果它很难理解O（1）alg . 那么你就不必使用O（1）算法
当O（1）需要大量无法提供的内存时，可以接受O（lgN）的时间 .
假设您正在嵌入式系统上实施黑名单，其中0到1,000,000之间的数字可能会被列入黑名单 . 这留下了两个可能的选择：
使用1,000,000位的位集
使用已列入黑名单的排序数组，并使用二进制搜索来访问它们
访问bitset将保证持续访问 . 就时间复杂性而言，它是最佳的 . 从理论和实际的角度来看（O（1）具有极低的恒定开销） .
不过，您可能希望更喜欢第二种解决方案 . 特别是如果你期望黑名单整数的数量非常小，因为它会更有效 .
即使你没有为内存稀缺的嵌入式系统开发，我也可以增加1,000,000到1,000,000,000,000的任意限制，并提出相同的论点 . 然后bitset将需要大约125G的内存 . 保证O（1）的最坏情况复杂性可能无法说服你的老板为你提供如此强大的服务器 .
在这里，我强烈希望在O（1）位集上进行二进制搜索（O（log n））或二叉树（O（log n）） . 并且可能的是，具有O（n）的最坏情况复杂度的哈希表将在实践中击败所有这些哈希表 .
可以并行执行算法 .
我不知道是否有类
O(log n)和O(1)的示例，但是对于某些问题，当算法更容易并行执行时，您选择具有更高复杂度类的算法 .有些算法不能并行化，但复杂度很低 . 考虑另一种算法，它可以实现相同的结果并且可以轻松并行化，但具有更高的复杂性等级 . 在一台机器上执行时，第二种算法较慢，但在多台机器上执行时，实际执行时间越来越低，而第一种算法无法加速 .
始终存在隐藏常量，其可以在O（log n）算法上更低 . 因此，它可以在实践中更快地用于实际数据 .
还存在空间问题（例如在烤面包机上运行） .
还有开发人员时间问题 - O（log n）可能更容易实现和验证1000 .
要么
人们已经回答了你的确切问题，所以我会解决一个人们在来这里时可能会想到的一个稍微不同的问题 .
很多"O(1) time"算法和数据结构实际上只需要 expected O（1）时间，这意味着它们的平均运行时间为O（1），可能只在某些假设下 .
Common examples: 哈希表，扩展"array lists"（a.k.a . 动态大小的数组/向量） .
在这种情况下，您可能更喜欢使用保证时间的数据结构或算法 absolutely 以对数方式界定，即使它们平均表现较差 .
因此，一个例子可能是 balancer 的二叉搜索树，其运行时间平均更差，但在最坏的情况下更好 .
添加到已经很好的答案 . 一个实际的例子是postgres数据库中的哈希索引与B树索引 .
散列索引形成哈希表索引以访问磁盘上的数据，而btree顾名思义使用Btree数据结构 .
在Big-O时间中，这些是O（1）vs O（logN） .
由于在现实生活中，特别是在数据库系统中，哈希索引目前不受欢迎，因此在没有冲突的情况下实现散列是非常困难的（可能导致O（N）最坏情况的复杂性）并且因此，更难以制作他们崩溃安全（称为提前写入记录 - 在postgres中的WAL） .
这种权衡是在这种情况下进行的，因为O（logN）对于索引来说足够好并且实现O（1）非常困难并且时间差异并不重要 .
可能有许多理由偏好具有较高O时间复杂度的算法而不是较低的算法：
大部分时间，较低的大O复杂度难以实现，需要熟练的实施，大量的知识和大量的测试 .
big-O隐藏了关于常量的详细信息：在
10^5中执行的算法从大O视角比1/10^5 * log(n)（O(1)vsO(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台商用机器上运行算法比使用复杂性稍高的一台机器更复杂 .
在某些地方（安全），复杂性可能是必需的 . 没有人想要一个可以快速散列的哈希算法（因为那时其他人可以更快地强制你）
虽然这与切换复杂性无关，但是某些安全功能应该以prevent timing attack的方式编写 . 它们大多数都停留在相同的复杂性类别中，但是以一种总是需要更糟糕的方式进行修改 . 一个例子是比较字符串是否相等 . 在大多数应用程序中，如果第一个字节不同，则快速断开是有意义的，但在安全性方面，您仍然会等待最终告诉坏消息 .
有人为低复杂度算法申请了专利，对于公司来说，使用更高的复杂性而不是付钱更为经济 .
一些算法很好地适应特定情况 . 例如，插入排序的平均时间复杂度为
O(n^2)，比quicksort或mergesort差，但作为online algorithm，它可以在接收到的值（作为用户输入）时有效地对值列表进行排序，其中大多数其他算法只能有效地运行在完整的值列表上 .我的答案Fast random weighted selection across all rows of a stochastic matrix是一个例子，当
m不是太大时，复杂度为O（m）的算法比复杂度为O（log（m））的算法要快 .