O(log N) == O(1) - 为什么不是呢？

Question

每当我考虑算法/数据结构时，我倾向于用常数替换log(N)部分。哦，我知道log(N)会发散 - 但在实际应用中有关系吗？

对于所有实际目的，log(无穷大) < 100。

我真的很好奇有哪些现实世界的例子不符合这个规律。

为了澄清：

• 我理解O(f(N))。
• 我想知道现实世界的例子，其中渐近行为比实际性能的常数更重要。
• 如果log(N)可以被一个常数替换，那么它仍然可以在O(N log N)中被一个常数替换。

这个问题是为了（a）娱乐和（b）收集论证材料，以便在我再次遇到有关设计性能的争议时使用。

- phoku

---

我也是。我几乎自动贬低了你的问题。但也许你有点意思。让我们等等人群... - Daren Thomas

使用相同的论点，你可以主张旅行推销员问题在O(1)时间内解决，因为让我们面对现实吧，实际上你永远不会想要访问超过（插入大量城市数量）个城市。 - San Jacinto

当然，这是正确的。任何具有有限N的算法严格来说都属于O(1)复杂度类，而且任何要在物理方式中表示的东西上运行的算法也属于这个复杂度类。这里需要注意理论的限制 :)。 - phoku

查找反阿克曼函数，以更好地理解“我们不妨将其视为线性”的例子。对于任何计算机合理处理的输入，该函数的结果始终小于5。请注意，此处仅为翻译，不包括其他解释或内容。 - Craig Gidney

将 O(everything) 定义为 O(1) 无疑会让考试更容易。但这种好处是有代价的。Big-O符号并不是一组复杂的随意定义，其目的是折磨大学生。它有一个目的，并且是一个相对简单的概念。你的建议只会使它更加复杂。 - yairchu

Answer 1

大 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) 进行操作。

还要记住，任何东西的大 O 值都可能有一个恒定的开销。假设这个恒定开销是 100 万。使用 O(1) 不会像 O(logn) 那样放大操作次数。

另一个要点是，所有人都认为 O(logn) 代表树数据结构中的 n 个元素，例如字节数组。但它可以是任何东西，包括文件中的字节数。

- Brian R. Bondy

---

不，你不会更喜欢在循环中使用O(1)而不是O(logN)。你宁愿使用实际上更快的那个，这需要进行测量。这就是原帖的全部意义，你完全没有理解重点。 - Brian

仅通过测量，你只能知道算法在这个输入大小下的运行速度，而不能告诉你当输入大小翻倍时它会执行得有多快。大O符号可以解决这个问题，但它不能替代测量。我认为Brian R. Bondy已经很好地理解了这个观点。 - jalf

我并不是在暗示你需要资格认证（比如针对“大规模输入”），我只是想表达你的观点是完全错误的。实际上，一个需要logN步骤的算法将始终优于需要100步骤的算法，无论输入大小如何（在极为合理的假设下，输入大小永远不会超过2^64个元素）。 - Brian

测量只对预先知道的恒定输入有效。 - Brian R. Bondy

@Brian: 我觉得你认为O(log n)在实际输入大小上是可以忽略的完全是一种离奇的想法。二分搜索是O(log n)。变量使用是O(1)。如果你需要多次使用某个值，你会每次都应用二分搜索，还是将它存储在一个变量中？你需要在回答之前进行衡量吗？...如果N变得足够大，最终O(1)总会胜出。说你的输入永远不会变得足够大，这与说“640k对于任何人来说应该足够了”的说法没有什么不同！ - Adam Bellaire

Answer 2

我认为这是一种实用的方法；O(logN)永远不会超过64。在实践中，每当术语变得像O(logN)这样“小”时，您就必须测量以查看常数因子是否胜出。另请参见

Ackermann函数的用途？

引用我自己在另一个答案评论中的话：

[大O符号]“分析”只对至少为O(N)的因子有影响。对于任何较小的因子，大O符号分析都是无用的，您必须进行测量。

和

“使用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)算法将比它更快。

(但是请阅读文章以了解上下文)。

- Brian

---

我觉得你提出的数据集有趣，可能需要我们孙辈的一生才能运行完，并且你想编写两种方式的代码（O(1)和O(logN)），并使用测试数据来测量时间。与其像你的回答所建议的那样务实，只选择在学术上表现更好的那个，不如考虑到它的实际代价（字面意义上是“花费生命”），当人们质疑为什么它没有及时完成时，你会不会希望有更多的依据来支持自己的决定？ - mrduclaw

如果我表达不清楚，我向您道歉。我的意思是，也许今天你使用的最大数据集可能是10^9级别的，而我可以想象50年后它可能会达到10^20或其他级别，但即使如此，我的论点仍然成立。即使对于非常巨大的数字，logN仍然足够小，以至于你不能基于复杂性理论在logN和1之间做出实际决策。 - Brian

我完全不同意。我们的数据集仍在增长。您所考虑的是，我们可能会达到10^20个信息"节点"。 我们认为这一点是正确的。但我们的分歧在于，我认为每个“节点”（或每个人的数据集）将包含数千兆字节的信息。此时，您已经超出了logbase2 n = 64。随着数据集的增长，情况确实会有所不同。 - San Jacinto

64在logN中的意义是什么？如何使LogN不大于64？ - Frank Q.

@Brian “‘分析’仅适用于至少是O（N）的因素”？您能否更详细地为我解释一下？为什么至少是O（N）？ - John

Answer 3

这是一个常见的误解 - 请记住大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)可能会更好。

- Falaina

---

他的意思（如果我理解得正确）是，您需要比“1000000 * a”输入大得多，才能获得比“a”输入多100倍的运行时间。 log（1000000）= 6，因此，如果将输入扩大1000000倍，则只会使运行时间变慢6倍。 - laura

我明白他说的意思了。关键在于你是否关心那个 lg(N) 的速度因素。我想可以这样说，谁会在乎一个 lg(N) 的差别呢，但这取决于应用程序的性能要求。 - Falaina

最好的情况是，OP正在警告我们不要盲目相信O（1）算法总是比O（log（n））更快；但是，得了吧，任何真正在学校学过大O符号的人都应该记得其中的注意事项。 - Calyth

Answer 4

您要求一个现实世界的例子，我可以给您一个。计算生物学。在ASCII编码中编码的一条DNA链在空间上大约是几十亿字节。一个典型的数据库显然会有成千上万这样的链。

现在，在索引/搜索算法的情况下，当与常数相结合时，log(n)的倍数会产生很大的差异。为什么呢？这是其中一个应用程序，其输入大小是天文数字级别的。此外，输入大小将始终继续增长。

诚然，这些类型的问题很少见。只有这么多大型应用程序。然而，在这种情况下......它会带来天翻地覆的变化。

- San Jacinto

---

谢谢您提供的例子。但是即使使用基数 2，那仍然低于 100。 - phoku

我不确定这会有什么区别。如果您的算法具有低或高常数，那么这个log(n)乘数将产生很大的差异。我不明白为什么100是一个神奇的数字。如果内部算法需要10分钟进行一次操作，那么为什么1610分钟看起来和410分钟一样无害呢？这将需要另外2个小时才能运行完毕！ - San Jacinto

Answer 5

在你描述的方式中，等式是一种常见的滥用符号。

为了澄清：我们通常写成 f(x) = O(logN) 来表示“f(x) 是 O(logN)”。

无论如何，O(1) 意味着无论输入集合有多大，执行一个操作所需的步骤/时间都是恒定的（作为上限）。但对于 O(logN)，步骤/时间数量仍然随着输入大小（其对数）而增长，只是增长得非常缓慢。对于大多数实际应用程序，您可以放心地假设这个步骤数不会超过100，但我敢打赌，存在多个数据集足够大，以至于您的声明既危险又无效（数据包跟踪、环境测量等）。

- Michael Foukarakis

---

你怎么能说大O符号在实际中没有用处呢？我直接使用过它几次，也经常将其作为指南间接使用，而且我见过其他人因为不理解它而犯了愚蠢的错误。 - Draemon

抱歉，但这是一个非常错误的说法。大 O 记号被广泛用于实际应用中，它是衡量两种不同算法可扩展性的重要方法。但我确实同意，OP 是一种常见的误用。 - Falaina

我也使用它，但它只描述了函数的渐近行为，当像OP那样发表声明时，仍有许多实际（即：实现定义）因素需要考虑。 - Michael Foukarakis

也许你应该稍微改一下你的回答。我明白你的意思，但说它“不用于实际目的”有点误导。 - jalf

我能理解它可能会被误解。我将其删除并为OP添加了一些澄清。 - Michael Foukarakis

Answer 6

对于足够小的N，O(N^N)可以在实践中用1来代替。不是O(1)(根据定义)，但对于N=2，您可以将其视为具有4个部分的单个操作或恒定时间操作。

如果所有操作都需要1小时呢？即使N很小，O(log N)和O(1)之间的差异也很大。

或者如果您需要运行算法一千万次呢？好的，那花了30分钟，所以当我在一个比原来大100倍的数据集上运行它时，应该仍然需要30分钟，因为O(logN)与O(1)“相同”...嗯...什么？

你说“我理解O(f(N))”，这显然是错误的。

现实世界的应用，哦...我不知道.... O()-符号的每个用途？

例如，在包含1000万项的排序列表中进行二进制搜索。这正是我们在数据变得足够大时使用哈希表的原因。如果您认为O(logN)与O(1)相同，那么为什么会使用哈希而不是二叉树呢？

- Thomas

---

公平地说：考虑 C = 执行时间大于估计宇宙年龄的指令数量。具有这种运行时间的任何算法都属于 O(1)。在某种意义上，运行时间为 O(exp(N)) 且常数足够小的算法更好，因为存在一个 N，使得算法将在我去世之前完成。 - phoku

@phoku 这只适用于特定的输入。在这种情况下，你可能会直接硬编码所需的指令，从而实现O(1)算法。我不确定你想证明什么。当你检查潜在的输入大小时，你会知道是选择高常数的算法还是log(n)算法。 - San Jacinto

@phoku：没错，但我们并不总是使用哈希表而不是二叉树。一个包含10个元素的列表几乎总是比哈希表查找更快。哈希表是O(1)（摊销），但操作比普通的二分查找更昂贵。断点取决于您的数据。 - Thomas

@phoku：澄清一下：我只回答了你的第三句话。你的第二句话似乎是无意义的。仅仅因为你有一个难以理解的长时间（但有限）去做某事，并不意味着你可以在那段时间内完成任何和所有的事情，无论输入大小如何。你必须将C定义为“运行时解决所有问题的指令集”，这是可证明错误的（参见停机问题）。 - Thomas

Answer 7

正如许多人已经说过的，对于现实世界，你需要首先考虑常数因素，甚至在担心O(log N)的因素之前。

然后，考虑你期望N是什么。如果你有充分的理由认为N<10，你可以使用线性搜索而不是二进制搜索。这是O(N)而不是O(log N)，根据你的标准来看，这将是显著的，但是一个将找到的元素移动到前面的线性搜索可能会表现得比更复杂的平衡树更好，具体取决于应用程序。

另一方面，注意，即使log N不太可能超过50，性能因子10确实非常巨大——如果你计算受限，这样的因子很容易决定你的应用程序成败。如果这还不够，你经常会看到算法中的(log N)^2或(log N)^3等因子，因此即使你认为可以忽略一个(log N)的因子，也并不意味着你可以忽略更多的因子。

最后，注意线性规划的单纯形算法的最坏情况性能为O(2^n)。然而，在实践中，最坏情况从未出现过；在实践中，单纯形算法是快速、相对简单的，因此非常受欢迎。

大约30年前，有人开发了一个线性规划的多项式时间算法，但最初它并不实用，因为结果是太慢了。

现在，有实用的线性规划替代算法（具有多项式时间最坏情况，对于这个值得多少），可以在实践中胜过单纯形方法。但是，根据问题的不同，单纯形方法仍然是有竞争力的。

- comingstorm

Answer 8

观察到 O(log n) 通常与 O(1) 难以区分，这是一个好的观点。

举个熟悉的例子，假设我们想在一个包含一万亿个元素的排序数组中查找单个元素：

• 使用线性搜索，平均需要5000亿步
• 使用二分搜索，平均需要40步

现在假设我们向正在搜索的数组中添加了一个元素，现在我们必须搜索另一个元素：

• 使用线性搜索，平均需要5000亿零1步（难以区分的变化）
• 使用二分搜索，平均需要40步（难以区分的变化）

现在假设我们将正在搜索的数组中的元素数量增加一倍，现在我们必须搜索另一个元素：

• 使用线性搜索，平均需要1万亿步（非常明显的变化）
• 使用二分搜索，平均需要41步（难以区分的变化）

从这个例子中可以看出，就所有实际目的而言，像二分搜索这样的 O(log n) 算法通常与像全知这样的 O(1) 算法难以区分。

重点是：我们使用 O(log n) 算法，因为它们通常与常数时间难以区分，并且它们通常比线性时间算法表现出色。

显然，这些示例假设合理的常数。显然，这些是通用观察结果，不适用于所有情况。显然，这些点适用于曲线的渐近端，而不是 n=3 端。

但是这个观察解释了为什么我们使用诸如调整查询以执行索引查找而不是表扫描之类的技术 - 因为索引查找在几乎任何数据集大小下都可以快速操作，而表扫描在足够大的数据集上非常慢。索引查找是 O(log n)。

- yfeldblum

Answer 9

您可能会对Soft-O感兴趣，它忽略了对数成本。请查看维基百科中的这一段。

- sdcvvc

Answer 10

你所说的“是否重要”是什么意思？

如果你面临一个 O(1) 算法和一个 O(lg n) 算法的选择，那么你不应该认为它们是相等的。你应该选择常数时间的算法。为什么不呢？

如果不存在常数时间算法，那么对数时间算法通常是你能得到的最好的结果。那么，它是否重要呢？你只需要选择你能找到的最快的算法。

你能给我一个情况，在这种情况下，定义两者相等会有所收获吗？最多，它不会有任何影响，最坏的情况是，你会隐藏一些真正的可扩展性特征。因为通常来说，常数时间算法将比对数时间算法更快。

即使如你所说，对于所有实际目的而言，lg(n) < 100，那么这仍然是你其他开销之上的一个因素100。如果我调用你的函数N次，那么你的函数运行的时间复杂度是对数时间还是常数时间就开始变得重要了，因为总的复杂度将是 O(n lg n) 或 O(n)。

因此，与其问在“现实世界”中假设对数复杂度为常数是否重要，我会问是否有任何意义这样做。

通常情况下，你可以假设对数算法足够快，但是如果将其视为常数，你能得到什么好处呢？

- jalf

---

当然它很重要 - O(log N)算法可能更简单、更易于维护和更快实现。 - phoku

没有人争辩过你可以找到一些输入情况，在其中 O(logn) 算法会比 O(1) 算法更快。但是通常情况下，当其他条件相同时，你应该选择一个 O(1) 算法。每个人都被这条评论中的第一行弄得困住了，却忽略了 O(1)算法没有比 O(logn)算法有更大的常数开销的理由。 - Brian R. Bondy

@phoku：那么O(log N)算法是否足够高效就很重要了。它不需要是常数时间，而是需要足够快以便能够使用。 - jalf