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

Andreas Grech 2021 big-o time-complexity

我目前正在学习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,但我无法理解如何识别具有对数时间的函数.

John Feminel.. 2570

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

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

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

要么

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

有关更多数学解释,您可以log n查看时间复杂度如何到达此处.https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf

  • @cletus:巧合,我很害怕.我选择它是因为电话簿有很大的N,人们了解它们是什么以及它们做了​​什么,并且因为它是多功能的例子.另外我在解释中使用了机器人!一场全能的胜利.(另外,看起来你的回答是在我成为StackOverflow的成员之前做的!) (77认同)
  • 我花了O(long⅝n!n-55/2)时间来找到一个最终有意义的O(log n)定义.+1 (50认同)
  • O(1)不是最好的情况,而不是最坏的情况,因为它被奇怪地强调为? (48认同)
  • @Billy:在这个例子中,`N`是一本书中的人数.因为电话簿中的每个人也都有他们自己的书副本,所以有N个_identical_电话簿,每个都有"N"个人,这是O(N ^ 2). (21认同)
  • "办公室发生了一个错误,每个电话簿中的每个条目在电话号码的末尾都有一个额外的"0".取一些白色并删除每个零." < - 这不是N平方的顺序.N定义为输入的大小.输入的大小是电话号码的数量,即每本书的数量乘以书籍的数量.这仍然是线性时间操作. (12认同)
  • 很棒的例子 - 绝对值得"大多数Bizzare例子"的奖项!;-) (5认同)
  • 这个答案是否被原始问题所接受,真是难以置信?这个答案在我看来并没有解释O(log n)时间到底是什么:你只给出了很多例子(也是与问题几乎没有关系的事情),而没有完全解释(总是)为什么这些事情的复杂性操作真的很正确.难以置信! (5认同)
  • @Svip我认为它被强调为最坏情况的原因是,在页面上找到一个给定条目的天真恒定时间过程涉及按顺序扫描每个条目,直到找到目标条目.如果页面上有50个条目,则最坏的情况是50个操作,即O(1).您可能会做得更好,即如果目标在页面上是第5位.在这种情况下,做"更好"的时间是可变的和未知的,因为有49个"更好"的情况,但最坏的情况总是恒定的操作数. (4认同)
  • 大O符号的很好的例证!关于O(1)案例的一个评论:你有一个免责声明说翻到给定的页码是恒定的时间,但我认为它更像是log(n).O(1)的一个更好的例子是通过翻开电话簿中的随机页面并在该页面上选择随机数来选择随机电话号码.无论电话簿中有多少条目,这都有不间断的运行时间,并且不需要免责声明. (4认同)
  • 实际上,人们用来在电话簿中查找姓名的算法不是二元搜索.它是插值搜索,平均为O(log log n)! (3认同)
  • @BenHodgson你一般都是正确的.然而,在这种情况下,由于接收电话簿副本的客户列表被定义为电话簿中的每个人或企业,n == m. (3认同)
  • 是不是"采取一些白化并删除每个零"O(n·m),其中n是条目数,m是打印的电话簿数量? (2认同)
  • @KenB我认为O(1)意味着恒定的时间,即操作量与输入无关.进行50次操作的50个条目将是O(n).http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions (2认同)
  • @Svip O(n)意味着可变性.如果您只考虑最坏的情况,50个操作是固定的数字,因为最坏的情况总是恰好50个条目.老实说,它稍微进入了语义学. (2认同)

Jørn Schou-R.. 563

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

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

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

二叉树

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

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

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

O(log n)

  • "注意每个级别如何包含与上面的级别相比的双重节点数(因此是二进制)"这是不正确的.你所描述的是一个*平衡的*二叉树.二叉树只意味着每个节点最多有两个子节点. (57认同)
  • 实际上,它是一个非常特殊的平衡二叉树,称为完整的二叉树.我编辑了答案,但需要有人批准. (8认同)
  • 完整的二叉树不需要完全填充最后一级.我会说,'完整的二叉树'更合适. (5认同)
  • 这棵树里面有31个项目,而不是16个.为什么它被称为16项数据集?它上面的每个节点都代表一个数字,否则它将是一个效率低下的二叉树:P (2认同)

fastcodejava.. 560

O(log N)基本上意味着时间呈线性上升而n指数上升.因此,如果1计算10元素需要2秒,计算100元素需要几秒钟,计算元素需要几3秒钟1000,等等.

这是O(log n)当我们分治法如二进制搜索的类型.另一个例子是快速排序,每次我们将数组分成两部分,每次都需要O(N)时间来找到一个数据元素.因此它 N O(log N)

  • 三行智慧打败了所有其他论文的答案...... :)以防万一有人错过它,在编程环境中,日志的基数是2(不是10),所以O(log n)的缩放比例为1秒10元素,20秒2秒,40等3个 (89认同)
  • 这花了我大约3次阅读,意识到这没有错._Time_线性上升,而_number of elements_是指数的.这意味着**在更短的时间内**更多的元素**.对于那些将"log"可视化为图形上熟悉的对数曲线的人来说,这是一种精神上的负担. (7认同)
  • 是的,对数函数是与指数函数相反的.((log x)基数a)与(幂x)相反.用图表对这些函数进行定性分析可以提供更多的直觉. (4认同)
  • 同意,简洁和明确,虽然OP的结束问题是如何识别对数函数,而不是"它是什么" (2认同)

2cupsOfTech.. 236

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

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

二叉树的高度

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

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

  • 新手在这里.那么你能说树高是通过递归达到n = 1的分割率吗? (2认同)

James Oravec.. 174

概观

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

首先,您需要了解Logarithm的一般概念,您可以从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增长,该算法也将始终只打印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";

摘要

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

  • 真棒.我见过的最好的解释.如果将"O(n ^ 2)"注意为"O(n)"和"O(n)"的组合,那就更好了,所以`O(n)*O(n)= O(n*n)= O(n ^ 2)`.没有这个等式,感觉有点跳跃.这是先前解释的重复,但我认为这种重复可以让读者更有信心理解. (14认同)

Mark Byers.. 128

如果你有一个功能:

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)时间.在大O符号,严格意义上是指关系只需要为大的N真实的,而且持续性因素和更小的方面可以忽略不计.


Anon... 94

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

  • log2或log10无关紧要.它们只有比例因子不同,这使得它们具有相同的顺序,即它们仍以相同的速率增长. (58认同)
  • 关于对数的有趣之处在于,当比较相对高度时,您使用的确切基数无关紧要.无论你使用什么基数,`log 10,000/log 100`都是2. (15认同)
  • 为了挑剔,O(lg n)意味着运行时*最多*与lg n成比例.你描述的是Theta(lg n). (12认同)

benscabbia.. 78

对数

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

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

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

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

在此输入图像描述

我们可以看到,对于每个循环,值增加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是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出色的Mathematician's Delight一书中提到的.


moonshadow.. 56

您可以通过说时间与N中的位数成比例来直观地考虑O(log N).

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

如果一个操作做出一系列恒定时间决定,其中每一半都要减半(减少3,4,5 ......),要考虑的输入大小,整体将花费时间与log base 2(base 3)成比例,输入的大小为N的基数4,基数5 ...),而不是O(N).

等等.

  • 我认为,比大多数解释更准确,更容易掌握. (7认同)

DivineWolfwo.. 51

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

如果您将问题大小增加一个乘法量(即将其大小乘以10),则工作量仅增加一个附加量.

将此应用于您的二叉树问题,以便您有一个好的应用程序:如果您将二叉树中的节点数加倍,则高度仅增加1(附加量).如果你再次加倍,它仍然只增加1.(显然我假设它保持平衡等).这样,当问题大小成倍增加时,你的工作量不会增加一倍,而是只做更多的工作.这就是为什么O(log n)算法很棒的原因.


Teoman shipa.. 44

首先,我建议你阅读以下书籍;

算法(第4版)

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

这是一些功能及其预期的复杂性

遵循Big-O复杂性图表也取自bigocheatsheet Big-O复杂性图表

最后非常简单的展示展示了如何计算;

解剖程序的语句执行频率.

分析程序的运行时间(示例).

分析程序的运行时间

  • 我不会把O(n log n)放在*坏*的篮子里。它属于* fair *之一。 (3认同)

Chad Brewbak.. 43

什么是log b(n)?

它是在到达大小为1的部分之前,可以将长度为n的对数重复切换为b等份的次数.


David Kanare.. 18

划分和征服算法通常具有logn运行时间的组成部分.这来自重复减半的输入.

在二进制搜索的情况下,每次迭代都会丢弃一半的输入.应该注意,在Big-O表示法中,log是log base 2.

编辑:如上所述,日志基数无关紧要,但在推导算法的Big-O性能时,对数因子将来自减半,因此我将其视为基数2.

  • 为什么它是log 2?以随机快速排序为例,我不认为它是基数2.据我所知,基数没关系,因为日志基数a(n)= log2(n)/ log2(a),所以每个对数通过常量与另一个不同,并且在大写符号中忽略常量.实际上,在我看来,用big-o表示法编写日志的基础是一个错误,因为你正在编写一个常量. (2认同)

小智.. 15

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

我将其改为'完整二叉树的高度为log n'.如果您逐步向下遍历,则确定完整二叉树的高度将为O(log n).

我无法理解如何识别具有对数时间的函数.

对数基本上是取幂的倒数.因此,如果函数的每个"步骤"都消除了原始项集中的元素因子,那么这就是对数时间算法.

对于树示例,您可以轻松地看到,当您继续遍历时,降低节点级别会减少指数数量的元素.查看名称排序电话簿的流行示例基本上等同于遍历二进制搜索树(中间页面是根元素,您可以在每个步骤推断出是向左还是向右).

  • +1提及"对数基本上是指数的倒数". (3认同)

Ravi Bisla.. 12

这两种情况需要O(log n)时间

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

  • @dj_segfault,这是我的错.我想现在它确实有意义.. :) (2认同)

stmax.. 11

O(log n)有点误导,更确切地说它是O(log 2 n),即(对数为2的对数).

平衡二叉树的高度为O(log 2 n),因为每个节点都有两个(注意log 2 n中的"two" )子节点.因此,具有n个节点的树具有log 2 n 的高度.

另一个例子是二进制搜索,其运行时间为O(log 2 n),因为在每一步都将搜索空间除以2.

  • O(log n)与O(ld n)或O(LN n)的顺序相同.它们是成比例的.我理解为了学习目的,使用ld更容易. (4认同)
  • "更确切地说,它是O(ld n)" - 不,它不是:所有日志都是相同的顺序(每个日志与其他日志的区别只是一些不变的比例因子,它被忽略/忽略). (4认同)

Platinum Azu.. 10

O(log n) 是指在与对数成比例的时间内工作的函数(或算法,或算法中的步骤)(在大多数情况下通常为2,但并非总是如此,并且无论如何,这通过big-O表示法无关紧要*)输入的大小.

对数函数是指数函数的倒数.换句话说,如果您的输入呈指数级增长(而非线性增长,正如您通常所认为的那样),则您的函数会线性增长.

O(log n)在任何一种分而治之的应用程序中,运行时间都很常见,因为你(理想情况下)每次都将工作量削减了一半.如果在每个分区或征服步骤中,你正在做恒定的时间工作(或者工作不是恒定时间,但随着时间的增长而变得更慢O(log n)),那么你的整个功能就是O(log n).每个步骤在输入上需要线性时间是相当普遍的; 这相当于总的时间复杂度O(n log n).

二进制搜索的运行时复杂度就是一个例子O(log n).这是因为在二进制搜索中,通过将数组分成两半并且仅关注每一步的一半,在每个后续步骤中总是忽略输入的一半.每个步骤都是常量时间,因为在二进制搜索中,您只需要将一个元素与您的键进行比较,以便在不考虑您在任何时候考虑的数组大小的情况下确定下一步该做什么.所以你做了大约log(n)/ log(2)步骤.

合并排序的运行时复杂性就是一个例子O(n log n).这是因为您将每个步骤将数组分成两半,从而导致总共大约log(n)/ log(2)步骤.但是,在每个步骤中,您需要对所有元素执行合并操作(无论是对n/2个元素的两个子列表进行合并操作,还是对n/4个元素的四个子列表进行两次合并操作,都是无关紧要的,因为它增加了必须为每个步骤中的n个元素执行此操作).因此,总的复杂性是O(n log n).

*请记住,根据定义,大O符号并不重要.此外,通过改变对数的基本规则,不同基数的对数之间的唯一差异是常数因子.


Valentin Roc.. 9

它只是意味着此任务所需的时间随log(n)增长(例如:n = 10时为2s,n = 100时为4s,......).阅读有关二进制搜索算法Big O表示法的维基百科文章,以获得更多精确度.


Brian R. Bon.. 9

简单地说:在算法的每一步,您都可以将工作量减半.(渐近等价于第三,第四......)

  • 这个答案非常不精确.首先,你可以想到只在基数为2的对数的情况下将工作减少一半.这个答案(以及对原始问题的大多数答案)收到如此多的向上投票真是令人难以置信."(渐近相当于第三,第四,......)"?如果你没有时间,为什么回答问题呢? (2认同)

Hadewijch De.. 8

如果你在图形计算器或类似的东西上绘制对数函数,你会发现它上升得非常慢 - 甚至比线性函数慢.

这就是为什么具有对数时间复杂度的算法备受追捧的原因:即使对于非常大的n(例如,n = 10 ^ 8),它们的表现也超过了可接受的程度.


ChrisW.. 7

但究竟什么是O(log n)

它的意思恰恰是"为n走向趋于infinity时,time趋向于a*log(n)在那里a是恒定的缩放系数".

或者实际上,它并不意味着; 更可能意味着" timea*log(n)趋向于分裂1".

"趋向"具有从"分析"通常的数学含义:例如,"如果你选择任何任意小的非零常数k,然后我能找到一个对应的值X,使得((time/(a*log(n))) - 1)小于k用于的所有值n大于X".


换句话说,它意味着时间等式可能具有一些其他组件:例如,它可能具有一些恒定的启动时间; 但是这些其他成分对于大的n值而言显得微不足道,而a*log(n)是大n的主要术语.

请注意,如果等式是,例如......

time(n)= a + b log(n)+ c n + d n n

...那么这将是O(n平方),因为无论常数a,b,c和非零d的d*n*n值如何,对于任何足够大的n值,该项总是优于其他项.

这就是O符号的含义:它意味着"任何足够大的n的主导项的顺序是什么".


SPIRiT_1984.. 7

我可以添加一些有趣的东西,很久以前我在Kormen等书中读过.现在,想象一个问题,我们必须在问题空间中找到解决方案.这个问题空间应该是有限的.

现在,如果你可以证明,在你的算法的每次迭代中,你切断了这个空间的一小部分,这不小于某个限制,这意味着你的算法在O(logN)时间内运行.

我应该指出,我们在这里谈的是相对分数限制,而不是绝对限制.二分搜索是一个经典的例子.在每一步,我们都会抛弃1/2的问题空间.但二元搜索并不是唯一的例子.假设,你以某种方式证明,在每一步你扔掉至少1/128的问题空间.这意味着,您的程序仍在O(logN)时间运行,但速度明显慢于二进制搜索.这是分析递归算法的一个非常好的暗示.通常可以证明,在每一步中递归都不会使用多个变量,这会导致问题空间中某些部分的截止.


Ely.. 6

我可以给一个for循环的例子,也许一旦掌握了这个概念,也许在不同的环境下理解起来会更简单.

这意味着在循环中,步骤呈指数增长.例如

for (i=1; i<=n; i=i*2) {;}

该程序的O符号的复杂度为O(log(n)).让我们尝试手动循环(n介于512和1023之间(不包括1024):

step: 1   2   3   4   5    6    7    8     9     10
   i: 1   2   4   8   16   32   64   128   256   512

虽然n介于512和1023之间,但只发生了10次迭代.这是因为循环中的步骤呈指数增长,因此只需10次迭代即可达到终止.

x的对数(到a的基数)是^ x的反函数.

这就像说对数是指数的倒数.

现在试着这样看,如果指数增长得非常快,那么对数增长(反向)非常慢.

O(n)和O(log(n))之间的差异很大,类似于O(n)和O(a ^ n)之间的差异(a是常数).


小智.. 6

每次我们编写算法或代码时,我们都会尝试分析其渐近复杂性。它不同于时间复杂性

渐进复杂度是算法执行时间的行为,而时间复杂度是实际执行时间。但是有些人可以互换使用这些术语。

因为时间复杂度取决于各种参数,即。
1.物理系统
2.编程语言
3.编码样式
4.还有更多……

实际执行时间不是分析的好方法。


相反,我们将输入大小作为参数,因为无论代码是什么,输入都是相同的。 因此执行时间是输入大小的函数。

以下是线性时间算法的示例


线性搜索
给定n个输入元素,要搜索数组中的一个元素,您最多需要'n'比较。换句话说,无论您使用哪种编程语言,更喜欢哪种编码风格,在哪种系统上执行它。在最坏的情况下,它仅需要进行n次比较。执行时间与输入大小成线性比例关系。

而且它不仅是搜索,它的工作量(增量,比较或任何操作)都是输入大小的函数。

因此,当您说任何算法为O(log n)时,这意味着执行时间为log乘以输入大小n。

随着输入大小的增加,完成的工作(此处的执行时间)增加。

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

看到随着输入大小的增加,完成的工作也增加了,并且它独立于任何机器。而且,如果您尝试找出工作单位的价值,则实际上取决于上面指定的参数,它将根据系统和所有方面而变化。


Khaled.K.. 5

树

log x to base b = y 是反的 b^y = x

如果你有一个深度为d且大小为n的M-ary树,那么:

  • 遍历整棵树~O(M ^ d)= O(n)

  • 在树中走一条路径~O(d)= O(log n到基数M)


bruziuz.. 5

在信息技术中,这意味着:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.

蚂蚁似乎这种表示法大多来自数学。

在本文中有一个引语: DE Knuth,“大欧姆龙和大欧米茄和大THETA”,1976年

基于此处讨论的问题,我建议SIGACT的成员以及计算机科学和数学杂志的编辑采用上述定义的符号,除非可以在合理的时间内找到更好的替代方法

今天是2016年,但今天仍然使用它。


在数学分析中,这意味着:

  lim (f(n)/g(n))=Constant; where n goes to +infinity

但是即使在数学分析中,有时也会使用该符号表示“ C * g(n)> f(n)> 0”。

从大学知道,这个符号是由德国数学家Landau(1877-1938)引入的


Dinaiz.. 5

实际上,如果您有一个由n个元素组成的列表,并从该列表中创建一个二叉树(就像在分治法中一样),则将一直除以2,直到达到大小为1的列表(叶子)。

第一步,将您除以2。然后有2个列表(2 ^ 1),将每个列表除以2,因此,您有4个列表(2 ^ 2),再次除以,您有8个列表(2 ^ 3) ),依此类推,直到您的列表大小为1

那给你方程式:

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(您将每边的lg作为对数,以lg为对数2)

  • 直到某些恶意软件开始在叶子节点之前的两个级别插入一个长度为x的新列表。那么这似乎是一个无限循环... (2认同)

归档时间:

查看次数:

913926 次

最近记录:

12 月 前