题 O(log n)究竟意味着什么?


我目前正在学习Big O Notation运行时间和摊销时间。我理解的概念 上) 线性时间,意味着输入的大小成比例地影响算法的增长...例如,二次时间也是如此 2 等等。甚至算法,例如置换生成器,用 上!) 时代,通过阶乘增长。

例如,以下功能是 上) 因为算法与其输入成比例增长 ñ

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

同样,如果有嵌套循环,则时间为O(n2)。

但到底是什么 O(log n)?例如,说完整二叉树的高度是什么意思 O(log n)

我知道(也许不是非常详细)Logarithm是什么,在某种意义上:log10 100 = 2,但我无法理解如何识别具有对数时间的函数。


1736
2018-02-21 20:05


起源


1节点二叉树具有高度log2(1)+1 = 1,2节点树具有高度log2(2)+1 = 2,4节点树具有高度log2(4)+ 1 = 3,并且等等。 n节点树的高度为log2(n)+1,因此向树中添加节点会导致其平均高度呈对数增长。 - David R Tribble
我在大多数答案中看到的一件事是它们基本上描述“O(某物)”意味着算法的运行时间与“某事物”成比例地增长。鉴于你要求“O(log n)”的“确切含义”,这不是真的。这是Big-Theta符号的直观描述,而不是Big-O。 O(log n)直观地表示运行时间增加 最多 与“log n”成比例: stackoverflow.com/questions/471199/... - Mehrdad Afshari
我总是记得分裂和征服作为O(log n)的例子 - RichardOD
重要的是要意识到它的日志基础2(不是基数10)。这是因为在算法的每个步骤中,您删除了剩余一半的选择。在计算机科学中,我们几乎总是处理日志库2,因为我们可以忽略常量。但是有一些例外(即Quad Tree运行时间是log base 4) - Ethan
@Ethan:你所在的基数并不重要,因为基本转换只是一个常数乘法,公式是log_b(x)= log_d(x)/ log_d(b)。 Log_d(b)只是一个常量。 - mindvirus


答案:


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

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

  • 选择执行某些操作的下一个元素是几种可能性之一,并且
  • 只需要选择一个。

要么

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

这就是为什么,例如,在电话簿中查找人是O(log n)。你不需要检查 一切 在电话簿中找到合适的人;相反,您可以通过基于字母顺序查看其名称来简单地分而治之,并且在您最终找到某人的电话号码之前,您只需在每个部分中探索每个部分的子集。

当然,更大的电话簿仍然会花费更长的时间,但它不会像额外的大小成比例增长那么快。


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

以下是我们可能在电话簿上执行的一些操作的运行时间,从最佳到最差:

  • O(1)(最佳情况): 给定企业名称所在的页面和企业名称,找到电话号码。

  • O(1)(平均情况): 给出一个人姓名所在的页面及其姓名,找到电话号码。

  • O(log n): 给定一个人的姓名,通过在您尚未搜索的书的部分中间选择一个随机点来查找电话号码,然后检查该人的姓名是否在该点。然后在书名中那个人姓名所在的部分中间重复这个过程。 (这是对某个人姓名的二进制搜索。)

  • 上): 查找电话号码包含数字“5”的所有人。

  • 上): 给定电话号码,找到具有该号码的个人或企业。

  • O(n log n): 打印机的办公室出现了混乱,我们的电话簿的所有页面都是以随机顺序插入的。通过查看每个页面上的第一个名称然后将该页面放在新的空白电话簿中的适当位置来修复排序以使其正确。

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

  • O(n log n): 我们想要个性化电话簿,所以我们将在指定的副本中找到每个人或企业的名字,然后在书中圈出他们的名字,并为他们的赞助写一个简短的感谢信。

  • 2): 办公室发生错误,每个电话簿中的每个条目在电话号码末尾都有一个额外的“0”。取一些白色并删除每个零。

  • O(n·n!): 我们准备将电话簿加载到运输码头。不幸的是,应该加载书籍的机器人已经变得混乱了:它正在以随机顺序将书籍放到卡车上!更糟糕的是,它将所有书籍加载到卡车上,然后检查它们是否按正确顺序排列,如果没有,则将其卸载并重新开始。 (这是可怕的 bogo sort。)

  • ñ): 您修复机器人,以便正确加载东西。第二天,你的一个同事对你进行恶作剧,并将装卸码头机器人连接到自动打印系统。每次机器人装载原始书籍时,工厂打印机都会重复运行所有电话簿!幸运的是,机器人的错误检测系统非常复杂,以至于当机器人遇到重复的书籍进行加载时,机器人不会尝试打印更多的副本,但它仍然需要加载已打印的每本原始和重复的书籍。


2182
2018-02-21 20:14



@cletus:巧合,我很害怕。我选择它是因为电话簿有很大的N,人们了解它们是什么以及它们做了​​什么,并且因为它是多功能的例子。另外我在解释中使用了机器人!一场全能的胜利。 (另外,看起来你的回答是在我成为StackOverflow的成员之前做的!) - John Feminella
“办公室出现了一个错误,每个电话簿中的每个条目在电话号码的末尾都有一个额外的”0“。取一些白色并删除每个零。” < - 这不是N平方的顺序。 N定义为输入的大小。输入的大小是电话号码的数量,即每本书的数量乘以书籍的数量。这仍然是线性时间操作。 - Billy ONeal
@Billy:在这个例子中, N 是一本书中的人数。因为电话簿中的每个人也都有自己的书副本,所以也有 N  相同 电话簿,每个都有 N 其中的人,是O(N ^ 2)。 - John Feminella
O(1)不是最好的情况,而不是最坏的情况,因为它被奇怪地强调为? - Svip
我花了O(long⅝n!n-55/2)时间来找到一个最终有意义的O(log n)定义。 +1 - iAteABug_And_iLiked_it


这个问题已经发布了许多好的答案,但我相信我们真的错过了一个重要的答案 - 即图解答案。

说完整二叉树的高度是O(log n)是什么意思?

下图描绘了二叉树。注意每个级别如何包含与上面的级别相比的节点数量的两倍(因此 二进制):

Binary tree

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

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

绘制 log(n) 在一张普通纸上,将产生一个图表,其中曲线的上升减速为 n 增加:

O(log n)


510
2018-02-21 22:22



“注意每个级别如何包含与上面的级别相比的双重节点数(因此是二进制的)”这是不正确的。你所描述的是一个 均衡 二叉树。二叉树只意味着每个节点最多有两个子节点。 - Oenotria
实际上,它是一个非常特殊的平衡二叉树,称为完整的二叉树。我编辑了答案,但需要有人批准。 - user21820
完整的二叉树不需要完全填充最后一级。我会说,'完整的二叉树'更合适。 - Mr. AJ
你的答案试图更具体地回应OP的原始问题,因此它比当前接受的答案(IMO)更好,但它仍然非常不完整:你只是给出一个例子和2个图像...... - nbro
这棵树有31个项目,而不是16.为什么它被称为16项数据集?它上面的每个节点都代表一个数字,否则它将是一个效率低下的二叉树:P - Perry Monschau


O(log N) 基本上意味着时间会线性上升 n 以指数方式上升。如果需要的话 1 第二个计算 10 元素,它将需要 2 计算秒数 100 元素, 3 计算秒数 1000 元素,等等。

是的 O(log n) 当我们划分和征服类型的算法,如二进制搜索。另一个例子是快速排序,每次我们将数组分成两部分,每次都需要 O(N) 时间找到一个枢轴元素。因此 N O(log N) 


464
2018-02-21 20:18



三行智慧打败了所有其他论文的答案...... :)以防万一有人错过了它,在编程环境中,日志的基数是2(不是10),所以O(log n)的缩放比例为1秒10元素,2秒20秒,40秒等3。 - nawfal
同意,简洁和明确,虽然OP的结束问题是如何识别对数函数,而不是“它是什么” - Adam
是的,对数函数是与指数函数相反的。 ((log x)基数a)与(幂x)相反。用图表对这些函数进行定性分析可以提供更多的直觉。 - overexchange
这花了我大约3次阅读,意识到这没有错。 时间 线性上升,而 元素数量 是指数的。意即 在更短的时间内更多元素。这对那些可视化的人来说是精神上的负担 log 作为图表上熟悉的对数曲线。 - Qix
我认为这是一个非常好的答案,除了它声称二元搜索是一种分而治之的算法。 事实并非如此。 - code_dredd


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

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

height of a binary tree

这就是你得到O(log n)的方法,这是在上面的树上需要完成的工作量才能达到解决方案。

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


198
2017-10-26 19:33



新手在这里。那么你能说树高是通过递归来达到n = 1的分割率吗? - Cody


如果你有一个功能:

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.

然后它需要日志2(n)时间。该 大O符号从松散的角度来说,这意味着只有大n的关系才需要,并且可以忽略常数因子和较小的项。


121
2018-02-21 20:11



log2(n)与o(log n)相同? - Sven van den Boogaart
是的,请参阅nawfal的评论,获取另一个答案:(复制粘贴) - 在编程上下文中,日志的基数为2(不是10),因此O(log n)对于10个元素的缩放为1秒,对于20个为2秒,40为40等 - Andrejs


概观

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

首先,您需要了解Logarithm,您可以从中获得 https://en.wikipedia.org/wiki/Logarithm 。自然科学用途 e 和自然日志。工程学徒将使用log_10(log base 10),计算机科学家将使用log_2(log base 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的上限。

enter image description here

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

O(1) - 常数时间示例:

  • 算法1:

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

print "hello";
  • 算法2:

算法2打印hello 3次,但不依赖于输入大小。即使n增长,该算法也将始终只打印3次hello。那说3,是一个常数,所以这个算法也是 O(1)

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

O(log(n)) - 对数例子:

  • 算法3 - 这就像“log_2”

算法3演示了一个在log_2(n)中运行的算法。注意for循环的post操作将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

这个算法很简单,打印你好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(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";

概要

上面给出了几个直接的例子和变体,以帮助证明可以引入哪些微妙的变化,实际上不会改变分析。希望它能给你足够的洞察力。


108
2018-04-26 22:50



真棒。我见过的最好的解释。如果更好的话 O(n^2) 被注意到的组合 O(n) 和 O(n)所以 O(n) * O(n) = O(n * n) = O(n^2)。没有这个等式,感觉有点跳跃。这是先前解释的重复,但我认为这种重复可以让读者更有信心理解。 - Eonil
@james感谢您的惊人答案 - Asthme
这是有史以来最好的解释。 - Edgar Kiljak


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


84
2018-02-21 20:10



log2或log10无关紧要。它们仅通过比例因子而不同,这使得它们具有相同的顺序,即它们仍以相同的速率增长。 - Noldorin
关于对数的有趣之处在于,在比较相对高度时,您使用的确切基数无关紧要。 log 10,000 / log 100 无论你使用什么基础,都是2。 - Anon.
为了挑剔,O(lg n)意味着运行时是 最多 与lg n成比例。你描述的是Theta(lg n)。
@rgrig:那是真的。我已经编辑了几个“最多”来表示big-O的上限性质。 - Anon.
@rgrig他描述了O和theta:Theta(lg n)暗示O(lg n) - klochner


对数

好吧,让我们试着完全理解对数实际上是什么。

想象一下,我们有一根绳子,我们把它绑在一匹马上。如果绳子直接绑在马上,那么马需要拉开的力量(例如,从一个人身上拉开)直接是1。

现在想象一下绳子环绕着一根杆子。逃跑的马现在必须更加努力。时间量取决于绳索的粗糙度和杆的大小,但我们假设它会将一个人的力量乘以10(当绳子完全转弯时)。

现在,如果绳索一圈,马将需要拉10倍。如果人类决定让这匹马变得非常困难,他可能会再次将绳子绕在杆子上,使其强度再增加10倍。第三个循环将再次将强度增加10倍。

enter image description here

我们可以看到,对于每个循环,值增加10.获得任何数字所需的回合数被称为数字的对数,即我们需要3个帖子来倍增你的力量1000倍,6个帖子来增加你的力量1,000,000。

3是1,000的对数,6是1,000,000(基数10)的对数。

那么O(log n)究竟意味着什么? 

在上面的例子中,我们的“增长率”是 O(log n)。对于每个额外的循环,我们的绳索可以处理的力是10倍:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

现在上面的例子确实使用了基数10,但幸运的是,当我们谈论大字符时,日志的基数是微不足道的。

现在让我们假设您正在尝试猜测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 | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

使用图表,我们可以看到,如果我们使用二进制搜索来猜测1-100之间的数字,那将需要我们 最多 7次尝试。如果我们有128个号码,我们也可以猜测7个尝试中的数字,但129个号码将需要我们 最多 8次尝试(与对数的关系,这里我们需要7个猜测128值范围,10个猜测1024值范围.7是对数128,10,10是1024的对数(基数2))。

请注意,我“最多”加粗。大写符号总是指更糟糕的情况。如果你很幸运,你可以在一次尝试中猜出这个数字,所以最好的情况是O(1),但这是另一个故事。

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

那么O(n log n)呢?

你最终会遇到一个线性时间 O(n log(n) 算法。上面的经验法则再次适用,但这次对数函数必须运行n次,例如减少列表的大小 n次,它发生在像mergesort这样的算法中。

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

免责声明:绳索对数的例子是从优秀的抓取 由W.Sawyer撰写的数学家的喜剧书 


55
2017-10-08 14:27