O(log n) 到底是什么意思？

编程入门行业动态更新时间:2024-10-25 11:28:40

O(log n) <a href=https://www.elefans.com/category/jswz/34/1771017.html style= 到底是什么意思？"/>

O(log n) 到底是什么意思？

问：

我正在学习 Big O Notation 运行时间和摊销时间。我理解 O(n) 线性时间的概念，这意味着输入的大小会成比例地影响算法的增长……例如，二次时间 O(n2) 等也是如此……甚至算法，例如置换生成器，具有 O(n!) 次，由阶乘增长。

例如，以下函数是 O(n)，因为算法的增长与其输入 n 成比例：

f(int n) {int i;for (i = 0; i < n; ++i)printf("%d", i);
}

类似地，如果有一个嵌套循环，时间将是 O(n2)。

但是 O(log n) 到底是什么？例如，完全二叉树的高度为 O(log n) 是什么意思？

我确实知道（可能不是很详细）对数是什么，从某种意义上说：log10 100 = 2，但我不明白如何识别具有对数时间的函数。

答1:

huntsbot高效搞钱，一站式跟进超10+任务平台外包需求

我无法理解如何识别具有日志时间的功能。

对数运行时间函数最常见的属性是：

选择执行某些操作的下一个元素是几种可能性之一，并且

只需要选择一个。

或者

执行动作的元素是 n 的数字

这就是为什么，例如，在电话簿中查找人员是 O(log n)。您无需检查电话簿中的每个人才能找到合适的人；取而代之的是，您可以通过根据他们的姓名按字母顺序查找的位置来简单地分而治之，并且在每个部分中，您只需要探索每个部分的子集，然后才能最终找到某人的电话号码。

当然，更大的电话簿仍然会花费您更长的时间，但不会像额外大小的比例增加那样快速增长。

我们可以扩展电话簿示例来比较其他类型的操作及其运行时间。我们将假设我们的电话簿中有具有唯一名称的企业（“黄页”）和可能没有唯一名称的人员（“白页”）。一个电话号码最多分配给一个人或一个企业。我们还将假设翻到特定页面需要恒定的时间。

以下是我们可能在电话簿上执行的一些操作的运行时间，从最快到最慢：

O(1)（在最坏的情况下）：给定商家名称所在的页面和商家名称，找到电话号码。

O(1)（一般情况下）：给定一个人的名字所在的页面和他们的名字，找到电话号码。

O(log n)：给定一个人的名字，通过在你还没有搜索到的书的一半左右选择一个随机点来找到电话号码，然后检查这个人的名字是否在那个点。然后重复这个过程大约一半的人的名字所在的书的部分。（这是对人名的二分搜索。）

O(n)：找出所有电话号码中包含数字“5”的人。

O(n)：给定一个电话号码，找到那个号码的人或企业。

O(n log n)：打印机办公室发生了混淆，我们的电话簿的所有页面都以随机顺序插入。通过查看每一页上的名字，然后将该页放在新的空电话簿中的适当位置来修正排序，使其正确。

对于以下示例，我们现在在打印机办公室。电话簿正在等待邮寄给每个居民或企业，每个电话簿上都有一个标签，标识应该邮寄到哪里。每个人或企业都有一本电话簿。

O(n log n)：我们想要个性化电话簿，所以我们要在他们指定的副本中找到每个人或企业的名字，然后在电话簿中圈出他们的名字，并写一个简短的感谢信感谢他们的惠顾.

O(n2)：办公室发生错误，每个电话簿中的每个条目的电话号码末尾都有一个额外的“0”。取一些白色并删除每个零。

O(n · n!)：我们已准备好将电话簿装载到装运码头上。不幸的是，本应装载书籍的机器人出现了故障：它正在以随机顺序将书籍放到卡车上！更糟糕的是，它会将所有书籍装载到卡车上，然后检查它们的顺序是否正确，如果不正确，它会卸载它们并重新开始。（这是可怕的 bogo 排序。）

O(nn)：你修复了机器人，让它正确加载东西。第二天，您的一位同事对您进行恶作剧，并将装卸平台机器人连接到自动打印系统。每次机器人去加载原始电话簿时，工厂打印机都会重复运行所有电话簿！幸运的是，机器人的错误检测系统足够复杂，当遇到要加载的复制书时，机器人不会尝试打印更多的副本，但它仍然必须加载每本已打印的原始和复制书。

@cletus：恐怕是巧合。我之所以选择它是因为电话簿的 N 很大，人们了解他们是什么以及他们做什么，并且因为它作为一个例子是多才多艺的。另外，我必须在解释中使用机器人！全方位的胜利。（另外，看起来你的答案是在我开始成为 StackOverflow 的成员之前做出的！）

“办公室发生了一个错误，每个电话簿中的每个条目的电话号码末尾都有一个额外的“0”。取一些白色并删除每个零。 <-- 这不是 N 次方。 N 定义为输入的大小。输入的大小是电话号码的数量，即每本书的号码数量乘以书籍的数量。这仍然是一个线性时间运算。

@Billy：在此示例中，N 是一本书中的人数。因为电话簿中的每个人也都有自己的电话簿副本，所以有 N 个相同电话簿，每个电话簿中有 N 个人，即 O(N^2)。

O(1) 不是最好的情况，而不是最坏的情况，因为它奇怪地突出显示为？

这个答案被原始问题接受了，这有多不可思议？在我看来，这个答案并没有解释 O(log n) 时间到底是什么：你只给出了很多例子（也包括与问题几乎无关的事情）而没有准确（总是）解释为什么这些例子的复杂性操作确实正确。极好的！

答2:

一个优秀的自由职业者，应该有对需求敏感和精准需求捕获的能力，而huntsbot提供了这个机会

O(log N) 基本上意味着时间呈线性增长，而 n 呈指数增长。因此，如果计算 10 个元素需要 1 秒，则计算 100 个元素需要 2 秒，计算 1000 个元素需要 3 秒，依此类推。

当我们进行分而治之的算法（例如二分搜索）时，它是 O(log n)。另一个例子是快速排序，每次我们将数组分成两部分，每次需要 O(N) 时间来找到一个枢轴元素。因此它N O(log N)

三行智慧胜过所有其他论文答案... :) 以防万一有人遗漏它，在编程上下文中，log 的基数是 2（不是 10），所以 O(log n) 的比例为 1 秒为 10元素，2 秒为 20，3 为 40 等。

同意，简洁明了，尽管 OP 的最终问题是如何识别对数函数，而不是“它是什么”

是的，对数函数是指数函数的反函数。 ((log x) base a) 是 (a power x) 的倒数。用图表对这些函数进行定性分析会给出更多的直觉。

这花了我大约 3 次通读，才意识到这并没有错。时间呈线性增长，而元素数量呈指数增长。这意味着在更短的时间内更多的元素。对于那些将 log 可视化为图形上熟悉的对数曲线的人来说，这在精神上是一种负担。

@nawfal 这不太对。当您使用符号 O(log n) 时，对数的底是无关紧要的，因为所有对数函数都彼此成比例。这就是为什么你省略了底数，而指数不是这种情况（例如 O(2^n) 与 O(10^n) 不同）。因此，即使在 base-2 的上下文中，您描述的缩放行为通常也不正确 - 它取决于常数因子。

答3:

HuntsBot周刊–不定时分享成功产品案例，学习他们如何成功建立自己的副业–huntsbot

这个问题已经发布了许多好的答案，但我相信我们确实错过了一个重要的答案——即图示的答案。

完全二叉树的高度为 O(log n) 是什么意思？

下图描绘了一个二叉树。请注意，每个级别包含的节点数量是上面级别的两倍（因此是二进制）：

.png

二分搜索是一个复杂的例子 O(log n)。假设图 1 中树的底层节点表示某个排序集合中的项目。二分搜索是一种分而治之的算法，图中显示了我们将如何需要（最多）4 次比较来找到我们在这个 16 项数据集中搜索的记录。

假设我们有一个包含 32 个元素的数据集。继续上图，发现我们现在需要 5 次比较才能找到我们要搜索的内容，因为当我们乘以数据量时，树只增长了一层。因此，算法的复杂度可以描述为对数阶。

在一张普通纸上绘制 log(n)，将得到一个曲线图，其中曲线的上升随着 n 的增加而减速：

.png

“注意每个级别如何包含与上面级别相比双倍数量的节点（因此是二进制）”这是不正确的。您所描述的是平衡二叉树。二叉树只是意味着每个节点最多有两个孩子。

实际上，它是一种非常特殊的平衡二叉树，称为完全二叉树。我已经编辑了答案，但需要有人批准。

完整的二叉树不需要将最后一层完全填充。我想说，“完整的二叉树”更合适。

您的答案试图更具体地回应 OP 的原始问题，因此它比当前接受的答案（IMO）更好，但它仍然非常不完整：您只给出了一个半个例子和 2 个图像......

这棵树有 31 项，而不是 16 项。为什么称为 16 项数据集？它上面的每个节点都代表一个数字，否则它将是一棵低效的二叉树：P

答4:

huntsbot高效搞钱，一站式跟进超10+任务平台外包需求

概述

其他人给出了很好的图表示例，例如树形图。我没有看到任何简单的代码示例。所以除了我的解释之外，我还会提供一些带有简单打印语句的算法来说明不同算法类别的复杂性。

首先，您需要对可以从获得的对数有一个大致的了解。自然科学使用 e 和自然对数。工程门徒会使用 log_10（以 10 为底的对数），而计算机科学家将大量使用 log_2（以 2 为底的对数），因为计算机是基于二进制的。有时您会看到自然对数的缩写为 ln()，工程师通常不使用 _10，只使用 log()，而 log_2 缩写为 lg()。所有类型的对数都以相似的方式增长，这就是为什么它们共享相同的 log(n) 类别。

当您查看下面的代码示例时，我建议查看 O(1)，然后是 O(n)，然后是 O(n^2)。在你对这些很好之后，再看看其他的。我已经包含了干净的示例和变体，以展示细微的变化仍然可以导致相同的分类。

您可以将 O(1)、O(n)、O(logn) 等视为增长的类别或类别。有些类别比其他类别需要更多时间。这些类别有助于为我们提供一种排序算法性能的方法。随着输入 n 的增长，一些增长得更快。下表以数字方式说明了所述增长。在下表中，将 log(n) 视为 log_2 的上限。

.jpg

各种大 O 类别的简单代码示例：

O(1) - 恒定时间示例：

算法1：

算法 1 打印 hello 一次，它不依赖于 n，所以它总是在恒定时间内运行，所以它是 O(1)。

print "hello";

算法2：

算法 2 打印 hello 3 次，但它不依赖于输入大小。即使随着 n 的增长，这个算法也只会打印 hello 3 次。话虽如此，3 是一个常数，所以这个算法也是 O(1)。

print "hello";
print "hello";
print "hello";

O(log(n)) - 对数示例：

算法 3 - 这就像“log_2”

算法 3 演示了在 log_2(n) 中运行的算法。请注意 for 循环的后操作将 i 的当前值乘以 2，因此 i 从 1 到 2 到 4 到 8 到 16 到 32 …

for(int i = 1; i <= n; i = i * 2)print "hello";

算法 4 - 这就像“log_3”

算法 4 演示了 log_3。注意 i 从 1 到 3 到 9 到 27…

for(int i = 1; i <= n; i = i * 3)print "hello";

算法 5 - 这就像“log_1.02”

算法 5 很重要，因为它有助于表明，只要数字大于 1 并且结果与自身反复相乘，就表明您正在查看对数算法。

for(double i = 1; i < n; i = i * 1.02)print "hello";

O(n) - 线性时间示例：

算法 6

这个算法很简单，打印 hello n 次。

for(int i = 0; i < n; i++)print "hello";

算法 7

该算法显示了一个变体，它将打印 hello n/2 次。 n/2 = 1/2 * n。我们忽略 1/2 常数，看到这个算法是 O(n)。

for(int i = 0; i < n; i = i + 2)print "hello";

O(n*log(n)) - nlog(n) 示例：

算法 8

将此视为 O(log(n)) 和 O(n) 的组合。 for 循环的嵌套帮助我们获得 O(n*log(n))

for(int i = 0; i < n; i++)for(int j = 1; j < n; j = j * 2)print "hello";

算法 9

算法 9 类似于算法 8，但每个循环都允许变化，这仍然导致最终结果为 O(n*log(n))

for(int i = 0; i < n; i = i + 2)for(int j = 1; j < n; j = j * 3)print "hello";

O(n^2) - n 平方示例：

算法 10

O(n^2) 可以通过嵌套标准 for 循环轻松获得。

for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)print "hello";

算法 11

与算法 10 类似，但有一些变化。

for(int i = 0; i < n; i++)for(int j = 0; j < n; j = j + 2)print "hello";

O(n^3) - n 立方示例：

算法 12

这类似于算法 10，但使用 3 个循环而不是 2 个循环。

for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)for(int k = 0; k < n; k++)print "hello";

算法 13

与算法 12 类似，但有一些变体仍会产生 O(n^3)。

for(int i = 0; i < n; i++)for(int j = 0; j < n + 5; j = j + 2)for(int k = 0; k < n; k = k + 3)print "hello";

概括

上面给出了几个直截了当的例子和变化，以帮助演示可以引入哪些细微的变化，而这些变化实际上不会改变分析。希望它能给你足够的洞察力。

惊人的。我见过的对我来说最好的解释。如果将 O(n^2) 标记为 O(n) 和 O(n) 的组合会更好，所以 O(n) * O(n) = O(n * n) = O(n^2)。没有这个等式，感觉有点跳跃。这是对先前解释的重复，但我认为这种重复可以为读者提供更多理解的信心。

这简直是有史以来最好的解释。

@IceTea，让您对您的问题有洞察力/直觉。如果您将 n 与 n/2 绘制成图表，您会发现它们都形成一条直线。这使它们处于同一类，因为它们具有相似的增长率（将其视为图表的形状）。同样，如果您将 log_2 与 log_3 绘制成图表，您会发现它们都具有“相似的形状”或“相似的增长率”。

@IceTea，@Shai 和@James 给出的解释更准确，n/2 or 2n or n+2 or n 在图中会有不同的线，但它们将具有相同的增长率，这意味着它们都将遵循线性增长。

如果我们有两个嵌套循环，但是第二个迭代器依赖于第一个迭代器，这种依赖关系会影响时间复杂度吗？

答5:

与HuntsBot一起，探索全球自由职业机会–huntsbot

下面的解释是使用完全平衡二叉树的情况来帮助您理解我们如何获得对数时间复杂度。

二叉树是这样一种情况，其中一个大小为 n 的问题被划分为大小为 n/2 的子问题，直到我们遇到大小为 1 的问题：

.png

这就是您获得 O(log n) 的方式，这是需要在上述树上完成的工作量才能达到解决方案。

具有 O(log n) 时间复杂度的常见算法是二分搜索，其递归关系为 T(n/2) + O(1)，即在树的每个后续级别，您将问题分成两半并做恒定数量的额外工作。

新手在这里。那么你能说树高是递归的分割率达到大小n = 1吗？

@Cody，是的，在大多数情况下，您的观察是准确的。此示例说明/使用 log_2。您的观察将超出 log_2，并且对于 x > 1 中的任何 log_x 都是准确的。但是，直接除法可能不会导致 1，因此您可能想说递归除法，直到最新除法的 Ceiling() 等于 1，或类似的东西。

答6:

保持自己快人一步,享受全网独家提供的一站式外包任务、远程工作、创意产品订阅服务–huntsbot

如果你有一个函数需要：

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2^n elements.

然后它需要 log2(n) 时间。 Big O notation，松散地说，意味着该关系只需要对大 n 为真，并且可以忽略常数因子和较小的项。

log2(n) 和 o(log n) 一样吗？

是的，请参阅 nawfal 的评论以获取此处的另一个答案：（复制粘贴）-在编程上下文中，日志的基数是 2（不是 10），因此 O(log n) 缩放 10 个元素为 1 秒，20 个元素为 2 秒, 3 代表 40 等

@SvenvandenBoogaart，此解决方案中的示例说明了 log_2，它属于 O(log(n)) 类。在 O(log(n)) 的同一类中还有许多其他人，即 log_x 其中 x > 1

@Andrejs，您的评论 so O(log n) scales like 1 sec for 10 elements, 2 sec for 20, 3 for 40 etc 不准确。该模式/类将与 O(n) 而不是 O(log(n)) 匹配/对齐。如果有人对 log_10 感兴趣，则等效示例是 10 个元素 1 秒，100 个元素 2 秒，1000 个元素 3 秒，等等。

答7:

huntsbot洞察每一个产品背后的需求与收益，从而捕获灵感

对数

好的，让我们尝试完全理解对数实际上是什么。

想象一下，我们有一根绳子，我们把它绑在一匹马上。如果绳子直接系在马身上，马需要拉开（例如，从男人身上）的力直接为 1。

现在想象绳子绕在一根杆子上。要逃跑的马现在必须用力拉很多倍。次数取决于绳子的粗糙度和杆子的大小，但我们假设它将一个人的力量乘以 10（当绳子转一圈时）。

现在，如果绳子绕了一次，马需要用力拉 10 倍。如果人类决定让马真的很困难，他可能会再次将绳子绕在一根杆子上，使其强度增加 10 倍。第三个循环将再次将强度增加 10 倍。

.png

我们可以看到，对于每个循环，该值增加 10。获得任何数字所需的圈数称为该数字的对数，即我们需要 3 个帖子将您的力量乘以 1000 倍，6 个帖子将您的力量乘以1,000,000。

3 是 1,000 的对数，6 是 1,000,000（以 10 为底）的对数。

那么 O(log n) 实际上是什么意思呢？

在我们上面的例子中，我们的“增长率”是 O(log n)。每增加一个环，我们的绳索可以承受的力就会增加 10 倍：

Turns | Max Force0   |   11   |   102   |   1003   |   10004   |   10000n   |   10^n

现在上面的例子确实使用了以 10 为底，但幸运的是，当我们谈论大 o 表示法时，对数的底是微不足道的。

现在让我们假设您正在尝试猜测 1-100 之间的数字。

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!

现在你需要 7 次猜测才能做到这一点。但这里的关系是什么？从每个额外的猜测中，你能猜到的最多项目是多少？

Guesses | Items1     |   22     |   43     |   84     |   165     |   326     |   647     |   12810    |   1024

使用该图，我们可以看到，如果我们使用二分搜索来猜测 1-100 之间的数字，最多需要 7 次尝试。如果我们有 128 个数字，我们也可以在 7 次尝试中猜测该数字，但 129 个数字最多需要 8 次尝试（相对于对数，这里我们需要 7 次猜测 128 值范围，10 次猜测 1024 值范围. 7 是 128 的对数，10 是 1024 的对数（以 2 为底）。

请注意，我将“最多”加粗。 Big-O 表示法总是指最坏的情况。如果幸运的话，你可以一次猜出这个数字，所以最好的情况是 O(1)，但那是另一回事了。

我们可以看到，对于每一次猜测，我们的数据集都在缩小。识别算法是否具有对数时间的一个好的经验法则是查看每次迭代后数据集是否按特定顺序收缩

O（n log n）呢？

你最终会遇到一个线性时间 O(n log(n)) 算法。上面的经验法则再次适用，但这次对数函数必须运行 n 次，例如将列表的大小减少 n 次，这发生在诸如合并排序之类的算法中。

您可以轻松识别算法时间是否为 n log n。寻找一个遍历列表 (O(n)) 的外循环。然后看看有没有内循环。如果内部循环在每次迭代中切割/减少数据集，则该循环为 (O(log n))，因此整体算法为 = O(n log n)。

免责声明：绳索对数示例取自优秀的 Mathematician’s Delight book by W.Sawyer。

没有。In our example above, our 'growth rate' is O(log n). For every additional loop, the force our rope can handle is 10 times more，由显示 n== 循环数和 our 'growth rate' => 的图表支持。 10^n，这不是 log n。该示例可以通过使 n=# horses 更正，这需要 log n 循环来约束。糟糕的教学例子会培养出只相信自己理解的学生。

答8:

huntsbot高效搞钱，一站式跟进超10+任务平台外包需求

对数运行时间 (O(log n)) 本质上意味着运行时间与输入大小的对数成比例增长 - 例如，如果 10 个项目最多花费一些时间 x，并且 100 项最多需要 2x，10,000 项最多需要 4x，那么它看起来像 O(log n) 时间复杂度。

+1，但你真的应该指出它是 log2，而不是 log10。

log2 或 log10 无关紧要。它们仅在比例因子上有所不同，这使得它们具有相同的顺序，即它们仍然以相同的速率增长。

对数的有趣之处在于，在比较相对高度时，您使用的确切底数无关紧要。无论您使用什么基数，log 10,000 / log 100 都是 2。

吹毛求疵，O(lg n) 意味着运行时间最多与 lg n 成正比。你描述的是Theta（lg n）。

@rgrig：这是真的。我已经编辑了一些“最多”以表明 big-O 的上限性质。

答9:

huntsbot汇聚了国内外优秀的初创产品创意，可按收入、分类等筛选，希望这些产品与实践经验能给您带来灵感。

首先，我建议您阅读以下书籍；

Algorithms (4th Edition)

这是一些功能及其预期的复杂性。数字表示语句执行频率。

.png

最后一个非常简单的展示，展示了它是如何计算的；

程序语句执行频率的剖析。

分析程序的运行时间（示例）。

.png

我不会把 O(n log n) 放在坏篮子里。它属于公平的。

查看大 O 复杂度图表（上图）时，您必须记住 O(n) 是实际的线性点，而不是粉红色/橙色边界。 @Andre这就是为什么O（n log n）被正确标记在“坏”性能括号中的原因，它的性能比线性差。

我在这里同意@AndréWerlang。例如 Quicksort 被认为是一种非常有效的排序算法，它的平均复杂度是 O(n log n)，绝对不应该被放在坏篮子里。

这个答案是错误的！它假设 N = N * N。实际上 N = N！您的示例实际上是 N 立方。你在你的图表中做同样的事情。你的 O(n) 实际上应该是可怕和糟糕之间的分水岭。数学证明：你说 for 循环是 O(1) 的常数。这就是 1 的真正含义，不依赖于 N。它只是意味着不可变。但它是可变的，因为它取决于 N。两倍 N 和一半的时间。因此是无效的。如果它来自那本书，不要买它！您显示的代码图形不是真实的，这是一个笑话，看，“Theesome”，这意味着三个人同时发生性关系！我的天啊

O(n) 不应该在对角线上吗？

答10:

保持自己快人一步,享受全网独家提供的一站式外包任务、远程工作、创意产品订阅服务–huntsbot

您可以通过说时间与 N 中的位数成正比来直观地想到 O(log N)。

如果一个操作对输入的每个数字或位执行恒定时间工作，则整个操作所花费的时间将与输入中的数字或位的数量成正比，而不是输入的大小；因此，O(log N) 而不是 O(N)。

如果一个操作做出一系列恒定时间决策，每一个决策都将要考虑的输入大小减半（减少 3、4、5…），那么整个操作所花费的时间将与 log base 2（base 3 , base 4, base 5…) 的输入大小为 N，而不是 O(N)。

等等。

我认为，比大多数解释都足够准确且更容易掌握。

这是对 log10 N 的解释，是吗？

@LiuYan刘研他们没有说数字的基数是多少。无论如何，log₂(n) = log₁₀(n)/log₁₀(2) 和 1/log₁₀(2) 因此是一个常数乘数，相同的原则适用于所有其他基础。这表明了两件事。首先，moonshadow 的原理适用于任何基础（尽管基础越低，估计中的“锯齿”越少）并且 O(log n) 是 O(log n)，无论导致您得出该结论的计算的基础是什么.

“成比例” ...“每个都是输入大小的一半” ??????