每当我考虑算法/数据结构时，我倾向于用常量替换 log(N) 部分。哦，我知道 log(N) 会发散——但这在现实世界的应用程序中重要吗？
对于所有实际目的，log(infinity) < 100。
我真的很好奇现实世界中这不成立的例子。
澄清：
这个问题是为了（a）娱乐和（b）收集论据，如果我（再次）陷入关于设计性能的争议。
大 O 表示法告诉您算法如何随着输入的增长而变化。O(1) 告诉你输入增长多少并不重要，算法总是一样快。O(logn) 表示算法会很快，但随着输入的增长，它会花费更长的时间。
当您开始组合算法时，O(1) 和 O(logn) 会产生很大的不同。
以使用索引进行连接为例。如果您可以在 O(1) 而不是 O(logn) 中进行连接，您将获得巨大的性能提升。例如，使用 O(1)，您可以加入任意次数，但仍然有 O(1)。但是对于 O(logn)，您需要每次将操作计数乘以 logn。
对于大输入，如果你已经有一个 O(n^2) 的算法，你宁愿做一个内部 O(1) 而不是 O(logn) 的操作。
还要记住，任何事物的 Big-O 都可能具有恒定的开销。假设恒定开销为 100 万。对于 O(1)，恒定开销不会像 O(logn) 那样放大操作数量。
另一点是，例如，每个人都认为 O(logn) 表示树数据结构的 n 个元素。但它可以是任何东西，包括文件中的字节。
我认为这是一种务实的做法；O(logN) 永远不会超过 64。在实践中，每当项变得像 O(logN) 一样“小”时，您必须测量以查看常数因子是否胜出。也可以看看
引用我对另一个答案的评论：
[Big-Oh]“分析”仅对至少 O(N) 的因素很重要。对于任何较小的因素，大哦分析是没有用的，你必须测量。
和
“对于 O(logN)，您的输入大小确实很重要。” 这是问题的重点。当然这很重要…… 理论上。OP提出的问题是，这在实践中重要吗？我认为答案是否定的，不存在，也永远不会存在 logN 增长如此之快以至于总是被恒定时间算法击败的数据集。即使对于我们孙辈可以想象的最大的实际数据集，logN 算法也很有可能击败恒定时间算法 - 你必须始终测量。
编辑
好话：
http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey
大约中途，Rich 讨论了 Clojure 的哈希尝试，显然是 O(logN)，但是对数的底很大，因此即使包含 40 亿个值，trie 的深度也最多为 6。这里的“6”仍然是一个 O(logN) 值，但它是一个非常小的值，因此选择丢弃这个很棒的数据结构，因为“我真的需要 O(1)”是一件愚蠢的事情。这强调了从实用主义者的角度来看，这个问题的大多数其他答案都是错误的，他们希望他们的算法“运行得快”和“规模化得好”，而不管“理论”怎么说。
编辑
也可以看看
http://queue.acm.org/detail.cfm?id=1814327
它说
如果这些操作导致页面错误和缓慢的磁盘操作，那么 O(log2(n)) 算法有什么好处？对于大多数相关数据集，避免页面错误的 O(n) 甚至 O(n^2) 算法将围绕它运行。
（但请阅读文章了解上下文）。
这是一个常见的错误 - 请记住，大 O 表示法并不是告诉您算法在给定值下的绝对性能，它只是告诉您增加输入大小时算法的行为。
当您在该上下文中使用它时，就会清楚为什么算法 A ~ O(logN) 和算法 B ~ O(1) 算法不同：
如果我在大小为 a 的输入上运行 A，然后在大小为 1000000*a 的输入上运行 A，我可以预期第二个输入的 log(1,000,000) 倍于第一个输入
如果我在大小为 a 的输入上运行 B，然后在大小为 1000000*a 的输入上运行 B，我可以预期第二个输入与第一个输入所花费的时间大致相同
编辑：再考虑一下您的问题，我确实认为其中有一些智慧。虽然我永远不会说 O(lgN) == O(1) 是正确的，但O( lgN ) 算法可能会用于 O(1) 算法。这又回到了上面关于绝对性能的观点：仅仅知道一种算法是 O(1) 而另一种算法是 O(lgN) 并不足以声明您应该使用 O(1) 而不是 O(lgN)，这当然是考虑到您的可能输入范围，O(lgN) 可能对您最有用。
你要求一个真实的例子。我给你一个。计算生物学。以 ASCII 编码的一条 DNA 链在空间中达到千兆字节的水平。一个典型的数据库显然会有成千上万个这样的链。
现在，在索引/搜索算法的情况下，log(n) 倍数在与常数结合时会产生很大的差异。之所以？这是您的输入大小是天文数字的应用程序之一。此外，输入大小将始终继续增长。
诚然，这类问题很少见。这么大的应用程序只有这么多。不过，在这种情况下……它会带来天壤之别。
正如许多人已经说过的那样，对于现实世界，您需要先查看常数因子，然后再担心 O(log N) 的因子。
然后，考虑您期望的 N 是什么。如果您有充分的理由认为 N<10，您可以使用线性搜索而不是二元搜索。那是 O(N) 而不是 O(log N)，根据您的灯光，这将很重要 - 但是将找到的元素移动到前面的线性搜索可能会胜过更复杂的平衡树，具体取决于应用程序。
另一方面，请注意，即使 log N 不太可能超过 50，10 的性能因子也确实很大——如果您受计算限制，那么这样的因子很容易成就或破坏您的应用程序。如果这对你来说还不够，你会经常在算法中看到 (log N)^2 或 (logN)^3 的因子，所以即使你认为可以忽略 (log N) 的一个因子，这并不意味着你可以忽略更多。
最后，请注意线性规划的单纯形算法的最坏情况性能为 O(2^n)。但是，对于实际问题，最坏的情况永远不会出现；在实践中，单纯形算法速度快、相对简单，因此非常受欢迎。
大约 30 年前，有人开发了一种用于线性规划的多项式时间算法，但最初并不实用，因为结果太慢了。
如今，有一些实用的线性规划替代算法（具有多项式时间最坏情况，这是值得的），它在实践中可以胜过单纯形法。但是，根据问题，单纯形法仍然具有竞争力。
Equality, the way you're describing it, is a common abuse of notation.
To clarify: we usually write f(x) = O(logN) to imply "f(x) is O(logN)".
At any rate, O(1) means a constant number of steps/time (as an upper bound) to perform an action regardless of how large the input set is. But for O(logN), number of steps/time still grows as a function of the input size (the logarithm of it), it just grows very slowly. For most real world applications you may be safe in assuming that this number of steps will not exceed 100, however I'd bet there are multiple examples of datasets large enough to mark your statement both dangerous and void (packet traces, environmental measurements, and many more).
对于足够小的 N，O(N^N) 实际上可以用 1 代替。不是 O(1)（根据定义），但是对于 N=2，您可以将其视为一个包含 4 个部分的操作，或一个恒定时间手术。
如果所有操作都需要 1 小时怎么办？即使 N 很小，O(log N) 和 O(1) 之间的差异也会很大。
或者如果您需要运行该算法一千万次？好的，这花了 30 分钟，所以当我在一百倍大的数据集上运行它时，它仍然需要 30 分钟，因为 O(logN) 与 O(1)“相同”......嗯......什么？
你所说的“我理解 O(f(N))”显然是错误的。
现实世界的应用程序，哦……我不知道……每次都使用 O() 表示法吗？
例如，在 1000 万个项目的排序列表中进行二进制搜索。当数据足够大时，这正是我们使用哈希表的原因。如果您认为 O(logN) 与 O(1) 相同，那么您为什么要使用哈希而不是二叉树？
O(log n)经常无法区分的观察O(1)是一个很好的观察。
作为一个熟悉的例子，假设我们想在一个包含 1,000,000,000,000 个元素的排序数组中找到一个元素：
假设我们在要搜索的数组中添加了一个元素，现在我们必须搜索另一个元素：
假设我们将要搜索的数组中的元素数量加倍，现在我们必须搜索另一个元素：
正如我们从这个例子中看到的那样，出于所有意图和目的，像二分搜索这样的算法通常与像全知这样O(log n)的算法没有区别。O(1)
要点是：*我们使用O(log n)算法是因为它们通常与恒定时间无法区分，而且它们的性能通常比线性时间算法好得多。
显然，这些例子假定了合理的常数。显然，这些是一般性观察，并不适用于所有情况。显然，这些点适用于曲线的渐近末端，而不是n=3末端。
但是这个观察解释了为什么，例如，我们使用诸如调整查询来进行索引查找而不是表扫描之类的技术——因为无论数据集的大小如何，索引查找都在几乎恒定的时间内运行，而表扫描是在足够大的数据集上非常慢。索引搜索是O(log n)。
您可能对忽略对数成本的 Soft-O 感兴趣。检查维基百科中的这一段。
它是否“重要”是什么意思？
如果您面临一个O(1)算法和一个算法的选择O(lg n)，那么您不应该假设它们是相等的。您应该选择恒定时间的。你为什么不呢？
如果不存在恒定时间算法，那么对数时间算法通常是你能得到的最好的。再说一遍，这有关系吗？你只需要采取你能找到的最快的速度。
你能给我一个通过将两者定义为相等来获得任何东西的情况吗？在最好的情况下，它没有任何区别，在最坏的情况下，你会隐藏一些真正的可扩展性特征。因为通常情况下，恒定时间算法会比对数算法更快。
即使，正如您所说，lg(n) < 100出于所有实际目的，这仍然是您其他开销的 100 倍。如果我调用你的函数 N 次，那么你的函数是运行对数时间还是常数就变得很重要，因为总复杂度是 thenO(n lg n)或O(n).
因此，与其问你假设对数复杂性在“现实世界”中是否“重要”，我会问这样做是否有任何意义。
通常你可以假设对数算法足够快，但是考虑到它们是恒定的，你会得到什么？
O(logN)*O(logN)*O(logN) 非常不同。O(1) * O(1) * O(1) 仍然是常数。此外，简单的快速排序风格 O(nlogn) 与 O(n O(1))=O(n) 不同。尝试对 1000 和 1000000 个元素进行排序。后者不是慢 1000 倍，而是 2000 倍，因为 log(n^2)=2log(n)
理论上
是的，在实际情况下，log(n) 以常数为界，我们会说 100。但是，在正确的情况下将 log(n) 替换为 100 仍然会丢弃信息，从而使您拥有的操作上限计算得更松散，用处也更少。在您的分析中将 O(log(n)) 替换为 O(1) 可能会导致您的大 n 案例的性能比您基于小 n 案例的预期差 100 倍。您的理论分析可能更准确，并且可能在您构建系统之前预测到问题。
我认为大 O 分析的实际目的是尽可能早地尝试预测算法的执行时间。您可以通过删除 log(n) 项来使您的分析更容易，但这样您就降低了估计的预测能力。
在实践中
如果您阅读了 Larry Page 和 Sergey Brin 关于 Google 架构的原始论文，他们谈到对所有内容都使用哈希表以确保例如查找缓存的网页只需要一次硬盘搜索。如果您使用 B-tree 索引进行查找，您可能需要四到五个硬盘搜索来执行未缓存的查找 [*]。从业务角度来看，将缓存网页存储上的磁盘需求增加四倍是值得关注的，并且如果您不排除所有 O(log(n)) 项，则可以预测。
PS抱歉以谷歌为例，他们就像计算机科学版的戈德温定律中的希特勒。
[*] 假设从磁盘读取 4KB，索引中有 1000 亿个网页，B 树节点中每个键大约 16 个字节。
问题的标题具有误导性（请注意，选择它是为了引发辩论）。
O(log N) == O(1) 显然是错误的（张贴者也知道这一点）。根据定义，大 O 表示法涉及渐近分析。当您看到 O(N) 时，N 被视为接近无穷大。如果为 N 分配了一个常数，则它不是大 O。
请注意，这不仅仅是理论计算机科学家需要关心的挑剔细节。用于确定算法的 O 函数的所有算术都依赖于它。当你为你的算法发布 O 函数时，你可能会忽略很多关于它的性能的信息。
Big O 分析很酷，因为它可以让您比较算法，而不会陷入特定于平台的问题（字长、每次操作的指令、内存速度与磁盘速度）。当 N 趋于无穷大时，这些问题就消失了。但是当 N 为 10000、1000、100 时，这些问题以及我们在 O 函数中遗漏的所有其他常数开始变得重要。
回答海报的问题：O(log N) != O(1)，你是对的，O(1) 的算法有时并不比 O(log N) 的算法好多少，具体取决于大小输入，以及在大 O 分析期间被忽略的所有内部常量。
如果你知道你会增加 N，那么使用大 O 分析。如果你不是，那么你需要一些经验测试。
Yes, log(N) < 100 for most practical purposes, and No, you can not always replace it by constant.
For example, this may lead to serious errors in estimating performance of your program. If O(N) program processed array of 1000 elements in 1 ms, then you are sure it will process 106 elements in 1 second (or so). If, though, the program is O(N*logN), then it will take it ~2 secs to process 106 elements. This difference may be crucial - for example, you may think you've got enough server power because you get 3000 requests per hour and you think your server can handle up to 3600.
Another example. Imagine you have function f() working in O(logN), and on each iteration calling function g(), which works in O(logN) as well. Then, if you replace both logs by constants, you think that your program works in constant time. Reality will be cruel though - two logs may give you up to 100*100 multiplicator.
假设在您的整个应用程序中，一种算法占用户等待最常见操作的时间的 90%。
假设实时 O(1) 操作在您的架构上需要一秒钟，而 O(logN) 操作基本上是 0.5 秒 * log(N)。嗯，在这一点上，我真的很想在曲线和直线的交点处给你画一个带有箭头的图形，说：“这很重要。” 在这种情况下，您希望对小型数据集使用 log(N) 操作，对大型数据集使用 O(1) 操作。
Big-O 表示法和性能优化是一项学术练习，而不是为用户提供已经很便宜的操作的真正价值，但如果它是关键路径上的一项昂贵操作，那么你打赌它很重要！
当您不确定 O(log n) = O(1) 时，确定 Big-O 表示法的规则会更简单。
正如 krzysio 所说，您可能会累积 O(log n)s，然后它们会产生非常明显的差异。想象一下你进行了二分搜索：O(log n) 次比较，然后想象每个比较的复杂度为 O(log n)。如果你忽略两者，你会得到 O(1) 而不是 O(log 2 n)。同样，您可能会以某种方式到达 O(log 10 n)，然后您会注意到不太大的“n”有很大的不同。
正如其他人指出的那样，Big-O 告诉您问题的性能如何扩展。相信我——这很重要。我遇到过好几次非常糟糕的算法，因为它们太慢而无法满足客户的需求。了解差异并找到 O(1) 解决方案很多时候是一个巨大的改进。
然而，当然，这不是全部 - 例如，您可能会注意到快速排序算法总是会切换到小元素的插入排序（维基百科说 8 - 20），因为这两种算法在小数据集上的行为。
因此，了解您将做哪些权衡是一个问题，这涉及对问题、架构和经验的透彻理解，以了解使用哪个以及如何调整所涉及的常量。
没有人说 O(1) 总是比 O(log N) 好。但是，我可以向您保证，O(1) 算法也可以更好地扩展，因此即使您对系统上有多少用户或要处理的数据大小做出错误的假设，也没关系到算法。
你是对的，在许多情况下，这对于实际目的来说并不重要。但关键问题是“增长速度有多快”。我们知道的大多数算法都采用输入的大小，因此它线性增长。
但是有些算法的 N 值以复杂的方式导出。如果 N 是“具有 X 个不同数字的彩票的可能彩票组合的数量”，那么如果你的算法是 O(1) 或 O(logN)，它就会突然变得很重要
对于任何可以接受不同大小 N 的输入的算法，它所进行的操作数的上限是某个函数 f(N)。
big-O 告诉你的只是那个函数的形状。
O(1) 表示存在某个数 A，对于大 N，f(N) < A。
O(N) 意味着有一些 A 使得 f(N) < AN 对于大 N。
O(N^2) 表示对于大 N，存在一些 A 使得 f(N) < AN^2。
O(log(N)) 表示对于大 N，存在一些 A 使得 f(N) < AlogN。
Big-O 没有说明 A 有多大（即算法有多快），或者这些函数在哪里相互交叉。它只是说，当您比较两种算法时，如果它们的大 O 不同，则存在一个 N 值（可能很小或可能很大），其中一种算法将开始优于另一种算法。
Big-OH 告诉您，在给定某个常数因子的情况下，一种算法比另一种算法更快。如果您的输入暗示了一个足够小的常数因子，那么您可以通过线性搜索而不是对某个碱基的 log(n) 搜索来获得巨大的性能提升。
O(log N) can be misleading. Take for example the operations on Red-Black trees.
The operations are O(logN) but rather complex, which means many low level operations.
无论何时N存储在某种内存中的对象数量都是正确的。毕竟，通过 64 位指针表示的每个字节的二进制搜索只需 64 步即可实现。实际上，只需 618 步就可以对可观测宇宙中的所有普朗克体积进行二分搜索。
因此，在几乎所有情况下，只要 N 是（或可能是）物理量，用 O(N) 近似 O(log N) 是安全的，并且我们确定只要 N 是（或可能是）一个物理量，则 log N < 618
但这是假设N。它可能代表其他东西。请注意，它并不总是很清楚它是什么。举个例子，以矩阵乘法为例，为简单起见假设为方阵。对于普通算法，矩阵乘法的时间复杂度为 O(N^3)。但是这里的 N 是什么？它是边长。这是一种衡量输入大小的合理方式，但使用矩阵中的元素个数（N^2）也是相当合理的。让 M=N^2，现在我们可以说平凡矩阵乘法的时间复杂度是 O(M^(3/2))，其中 M 是矩阵中元素的数量。
不幸的是，我本身没有任何现实世界的问题，这是你问的。但至少我可以编造一些有意义的东西：
让 f(S) 是一个函数，它返回 S 的幂集中所有元素的哈希值之和。这里有一些拟定：
f(S):
ret = 0
for s = powerset(S))
ret += hash(s)
在这里，hash就是简单的散列函数，并且powerset是一个生成器函数。每次调用它时，它将生成 S 的下一个（根据某种顺序）子集。生成器是必要的，因为否则我们将无法存储大量数据的列表。顺便说一句，这是一个这样的电源组生成器的 python 示例：
def powerset(seq):
"""
Returns all the subsets of this set. This is a generator.
"""
if len(seq) <= 1:
yield seq
yield []
else:
for item in powerset(seq[1:]):
yield [seq[0]]+item
yield item
https://www.technomancy.org/python/powerset-generator-python/
那么 f 的时间复杂度是多少？与矩阵乘法一样，我们可以选择 N 来表示很多东西，但至少两个是很有意义的。一个是 S 中元素的数量，在这种情况下，时间复杂度是 O(2^N)，但另一种衡量它的合理方法是 N 是 S 的幂集中元素的数量。在这种情况下，时间复杂度是 O(N)
那么对于 S 的合理大小，log N 是多少？好吧，包含一百万个元素的列表并不罕见。如果n是S的大小，N是P(S)的大小，那么N=2^n。所以 O(log N) = O(log 2^n) = O(n * log 2) = O(n)
在这种情况下，这很重要，因为在现实世界中 O(n) == O(log n) 很少见。
假设您使用以 O(log N) 运行的图像处理算法，其中 N 是图像的数量。现在......说它以恒定的时间运行会让人们相信无论有多少图像，它仍然会在大约相同的时间内完成它的任务。如果在单个图像上运行算法假设需要一整天，并且假设 O(logN) 永远不会超过 100...想象一下那个人会尝试在一个非常大的图像数据库上运行算法的惊讶- 他希望它在一天左右的时间内完成……但它需要几个月才能完成。
我不相信真正存在可以在具有大常数的 O(1) 和 O(logN) 之间自由选择的算法。如果一开始有 N 个元素要使用，那么将其设为 O(1) 是完全不可能的，唯一可能的是将 N 移动到代码的其他部分。
我想说的是，在所有实际情况下，我都知道您有一些空间/时间权衡，或者一些预处理，例如将数据编译为更有效的形式。
也就是说，你并没有真正去 O(1)，你只是将 N 部分移到别处。要么将代码的某些部分的性能与一些内存量交换，要么将算法的一部分的性能与另一部分交换。为了保持清醒，您应该始终着眼于大局。
我的观点是，如果你有 N 个项目，它们就不会消失。换句话说，您可以在低效的 O(n^2) 算法或更糟糕的算法和 O(n.logN) 之间进行选择：这是一个真正的选择。但是你永远不会真正去 O(1)。
我试图指出的是，对于每个问题和初始数据状态，都有一个“最佳”算法。你可以做得更糟，但永远不会更好。有了一些经验，您可以很好地猜测这种内在复杂性是什么。然后，如果您的整体治疗与这种复杂性相匹配，您就知道您有一些东西。您将无法降低这种复杂性，而只能移动它。
如果问题是 O(n)，它不会变成 O(logN) 或 O(1)，您只需添加一些预处理，以使整体复杂性保持不变或更糟，并且可能会改进后续步骤。假设您想要数组的较小元素，您可以在 O(N) 中搜索或使用任何常见的 O(NLogN) 排序处理对数组进行排序，然后使用 O(1) 进行第一个。
随便这样做是个好主意吗？仅当您的问题还要求第二、第三等元素时。那么你最初的问题是真正的 O(NLogN)，而不是 O(N)。
如果您为结果等待十倍或二十倍的时间，情况就不一样了，因为您简化了 O(1) = O(LogN)。
我正在等待一个反例；-) 这是任何实际情况，您可以在 O(1) 和 O(LogN) 之间进行选择，并且每个 O(LogN) 步骤都无法与 O(1) 进行比较。您所能做的就是采用更差的算法而不是自然算法，或者对较大图片的其他部分进行一些重处理（预计算结果，使用存储空间等）