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

time-complexity big-o


我正在了解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,但是我不明白如何用对数时间来识别一个函数。




Answer 1 John Feminella


我不明白如何用对数时间来识别一个函数。

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

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

or

  • 执行动作的元素是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):修复机器人,使其正确装载东西。第二天,您的一个同事在对您开玩笑,并将装卸台机器人连接到自动打印系统。每次机器人去装入原书时,工厂打印机都会重复运行所有电话簿!幸运的是,该机器人的错误检测系统足够复杂,以至于当机器人遇到一本重复的书本进行加载时,它不会尝试打印更多的副本,但仍然必须加载每本已印刷的原始书本和重复本。




Answer 2 fastcodejava


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

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




Answer 3 Jørn Schou-Rode


对于这个问题,已经有很多好的答案贴出来了,但我相信大家确实缺少一个重要的答案--即图解答案。

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

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

Binary tree

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

假设我们反而有一个32个元素的数据集。继续上面的画法,发现我们现在需要5次比较才能找到我们要找的东西,因为当我们乘以数据量时,树只增加了一级深度。因此,算法的复杂度可以用对数阶来描述。

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

O(log n)




Answer 4 2cupsOfTech


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

二进制树是将大小为n的问题划分为大小为n/2的子问题,直到达到大小为1的问题。

height of a binary tree

而这就是你如何得到O(log n),也就是在上面的树上需要做的工作量,以达到一个解决方案。

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




Answer 5 James Oravec


Overview

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

首先,您需要了解对数的一般概念,可以从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的上限。

enter image description here

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

这个算法显示了一个变化,它将打印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) 通过嵌套循环标准可以轻松获得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";

Summary

上面给出了几个直截了当的例子,以及变通的例子,以帮助证明可以引入哪些微妙的变化,而这些变化其实并没有改变分析结果。希望能给你足够的启示。