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

我正在了解 Big O Notation 运行时间和摊销时间。我理解O(n)线性时间的概念,这意味着输入的大小会成比例地影响算法的增长... 例如,二次时间O(n 2 )等也是如此。 ,例如乘数为O(n!)的排列生成器,并通过阶乘增长。

例如,以下函数为O(n),因为该算法与输入n成正比增长:

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

同样,如果存在嵌套循环,则时间将为 O(n 2 )。

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

我确实知道(也许不是很详细)什么是对数,即:log 10 100 = 2,但是我不明白如何用对数时间来识别一个函数。

答案

我不明白如何用记录时间来识别功能。

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

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

要么

  • 执行操作的元素是 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(n 2 ):在办公室发生错误,并且每个电话簿中的每个条目在电话号码的末尾都有一个额外的 “0”。进行一些涂白,并删除每个零。

  • O(n·n!):我们已经准备好将电话簿加载到运输码头上。不幸的是,原本应该用来装书的机器人已经走到了尽头:它将书随机地放到卡车上!更糟糕的是,它将所有书籍装到卡车上,然后检查它们的顺序是否正确,如果不正确,则将其卸下并重新开始。 (这是可怕的bogo 排序 。)

  • O(n n ):修复机器人,使其正确装载东西。第二天,您的一个同事在胡闹您,并将装卸台机器人连接到自动打印系统。每次机器人去加载原书时,工厂打印机都会重复运行所有电话簿!幸运的是,该机器人的错误检测系统足够复杂,以至于当机器人遇到一本要加载的重复书本时,它不会尝试打印更多副本,但仍然必须加载每本已印刷的原始书本和重复书本。

O(log N)基本上意味着时间线性增长,而n呈指数增长。因此,如果它需要1秒到计算10的元件,这将需要2秒,以计算100的元件, 3秒,以计算1000元素,依此类推。

`` 当我们进行分治的算法(例如二进制搜索O(log n)时,它是O(log n) 。另一个例子是快速排序,其中每次我们将数组分为两部分,每次花费O(N)时间来查找枢轴元素。因此,它NO(log N)

关于这个问题,已经有很多好的答案,但是我相信我们确实缺少一个重要的答案,那就是图示答案。

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

下图描绘了一个二叉树。请注意,每个级别如何包含的节点数量是上述级别的两倍(因此, binary ):

二叉树

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

假设我们有一个包含 32 个元素的数据集。继续上面的绘图,发现我们现在需要 5 个比较来查找我们要寻找的内容,因为当我们乘以数据量时,树仅深了一层。结果,算法的复杂性可以描述为对数阶。

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

O(log n)

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

二叉树是将大小为 n 的问题分为大小为 n / 2 的子问题,直到我们遇到大小为 1 的问题的情况:

二叉树的高度

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

具有 O(log n)时间复杂度的常见算法是二进制搜索,其递归关系为 T(n / 2)+ O(1),即,在树的每个后续级别上,您都将问题分为两部分,并进行固定数量的附加工作。

总览

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

首先,您需要了解对数的一般概念,您可以从https://en.wikipedia.org/wiki/Logarithm获得。自然科学使用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 的上限。

在此处输入图片说明

各种大 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

该算法很简单,可以打出 n 次问候。

for(int i = 0; i < n; i++)
  print "hello";
  • 算法 7

该算法显示了一种变体,它将打出 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";

摘要

上面给出了几个简单的示例,并通过各种变体来说明可以引入哪些细微的更改,这些更改实际上并不会改变分析。希望它能给您足够的见识。

如果您的函数需要:

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.

然后,它需要 log 2 (n)时间。 粗略地说, Big O 表示关系仅对于大的 n 才是正确的,并且常数因子和较小的项可以忽略。

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

对数

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

想象一下,我们有一条绳索,并且已经将它绑在马上了。如果将绳索直接绑在马匹上,则马匹需要拉开的力(例如,从人身上拉开)直接为 1。

现在,想象一下绳子缠绕在一根杆子上。要逃脱的马匹现在将不得不更努力地拉很多次。时间的长短取决于绳索的粗糙度和杆子的大小,但让我们假设它会将人的力量乘以 10(绳索完全转一圈)。

现在,如果将绳子缠绕一次,则马将需要拉力十倍。如果人类决定让这匹马真正困难,他可以将绳索再次绕在一根杆子上,使其强度再增加 10 倍。第三个循环将再次使强度再提高 10 倍。

在此处输入图片说明

我们可以看到,对于每个循环,该值都会增加 10。获得任何数字所需的匝数称为该数字的对数,即,我们需要 3 个柱将您的强度乘以 1000 倍,将 6 个柱将您的强度乘以 1,000,000。

3 是 1,000 的对数,而 6 是 1,000,000(以 10 为底)的对数。

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

在上面的示例中,我们的 “增长率” 为O(log n) 。每增加一个环,我们的绳索可以承受的力就会增加十倍:

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 次尝试(与对数有关,此处对于 128 个值范围,我们将需要 7 个猜测,对于 1024 个值范围,我们将需要 10 个猜测 7 是对数 128,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从出色的数学家的 Delight 书中获得的

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

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

如果某个操作做出一系列恒定时间决策,每个决策都将要考虑的输入大小减半(减少 3、4、5 ..),则整个时间将与对数以 2 为底(以 3 为底)成比例,基数 4,基数 5 ...),其大小为输入的大小 N,而不是 O(N)。

等等。

我一直必须在心理上可视化以 O(log n)运行的算法的最佳方法如下:

如果您将问题的大小增加一个乘数(即,将其大小乘以 10),那么功只会增加一个加法数。

将其应用于您的二叉树问题,这样您就可以很好地应用:如果将二叉树中的节点数加倍,则高度仅增加 1(加法数)。如果再次将其加倍,它仍然仅增加 1。(显然,我假设它保持平衡,等等)。这样,您不会在问题规模成倍增加的情况下加倍工作,而只是做更多的工作。这就是 O(log n)算法很棒的原因。