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

我不知道如何用日志时间来标识函数。

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

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

或

• 执行动作的元素是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) ^二 ): 办公室发生了一个错误,每个电话簿的每个条目在电话号码的末尾都有一个额外的“0”。取出一些白色的并去掉每一个零。

• O(n·n): 我们准备把电话簿装到船坞上。不幸的是,原本要装书的机器人出了问题:它把书按随机顺序放在卡车上!更糟糕的是,它把所有的书都装到卡车上,然后检查它们的顺序是否正确,如果不正确,它就把书卸下来重新开始。(这是可怕的 bogo sort )

• O(n) ⁿ ): 你把机器人修好,使它能正确装载东西。第二天,你的一个同事在你身上恶作剧,并把装卸台机器人连接到自动打印系统上。每次机器人装载一本原版书时,工厂的打印机都会重复运行所有的电话簿!幸运的是,机器人的错误检测系统足够复杂,当机器人遇到要加载的复本时,它不会尝试打印更多的复本,但它仍然必须加载已打印的每一本原版和复本。

为了获得更多的数学解释,您可以检查时间复杂性是如何到达的 log n 在这里。 https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf

这个问题已经有很多好的答案了,但我相信我们确实遗漏了一个重要的答案——即图解的答案。

一个完整的二叉树的高度是o(log n)是什么意思?

下图描绘了一棵二叉树。请注意,与上面的级别相比,每个级别包含的节点数是上面的两倍(因此 二元的 ):

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

假设我们有一个包含32个元素的数据集。继续上面的绘图,我们现在需要5个比较来找到我们要搜索的内容,因为当我们将数据量相乘时,树的深度只有一级。因此,算法的复杂度可以用对数阶来描述。

作图 log(n) 在一张普通的纸上,会产生一个曲线上升减速的图形 n 增加:

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

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

下面的解释是使用 平衡的 二叉树帮助你理解我们如何得到对数时间复杂度。

二叉树是这样的一种情况,在我们得到大小为1的问题之前,大小为n的问题被划分为大小为n/2的子问题:

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

具有o(log n)时间复杂度的一种常见算法是二元搜索,其递归关系为t(n/2)+o(1),即在树的每个后续层次上,将问题分成一半,并做恒定量的额外工作。

概述

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

首先,你要对对数有一个大致的概念,你可以从 https://en.wikipedia.org/wiki/Logarithm . 自然科学应用 e 还有天然原木。由于计算机是二进制的,工程学的学生将使用log 10(logbase10),计算机科学家将大量使用log 2(logbase2)。有时你会看到自然对数的缩写 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(对数(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演示logu 3。通知 我 从1到3到9到27…

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

• 算法5-这就像“logu 1.02”

算法5很重要,因为它有助于证明,只要数字大于1,并且结果与自身重复相乘,就说明您正在研究对数算法。

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

o(n)-线性时间示例:

• 算法6

这个算法很简单,可以打印n次hello。

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";

总结

上面给出了几个简单的例子和变化,以帮助说明可以引入哪些细微的变化,而这些变化并不会真正改变分析。希望它能给你足够的洞察力。

如果有一个函数需要:

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.

然后它需要日志 _二 (n)时间。这个 Big O notation ,粗略地说,这意味着关系只需要对大n成立,常数因子和较小的项可以忽略。

对数运行时间( O(log n) )基本上意味着运行时间与 对数 输入大小-例如,如果10个项最多需要一些时间 x ,100个项目最多,比如, 2x ,最多可携带10000件物品 4x ,然后它看起来像 O(log n) 时间复杂性。

对数

好吧,让我们试着完全理解对数到底是什么。

假设我们有一根绳子,我们把它拴在一匹马身上。如果绳子直接系在马身上,马需要拉离的力(比如说从人身上)是1。

现在想象一下绳子绕着一根杆子。这匹马要想逃走,现在得使劲拉好几倍。次数的多少将取决于绳子的粗糙度和杆子的大小,但假设它将把一个人的力量乘以10(当绳子完全转动时)。

现在如果绳子绕一圈,马就需要使劲拉10倍。如果人类决定给马制造真正的困难,他可以把绳子再绕在一根杆子上,使它的力量再增加10倍。第三个循环将再次增加10倍的力量。

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

3是1000的对数,6是1000000的对数(以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,但幸运的是,当我们讨论大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 | 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符号总是指更坏的情况。如果你幸运的话,你可以一次猜出数字,所以最好的情况是o(1),但那是另一回事。

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

o(n logn)呢?

你最终会遇到一个罕见的时刻 O(n log(n)) 算法。上面的经验法则再次适用,但这次对数函数必须运行n次,例如减小列表的大小。 n次 ,它出现在mergesort之类的算法中。

您可以很容易地确定算法时间是否为n logn。查找遍历列表(o(n))的外部循环。然后看看有没有内环。如果内环是 切割/还原 每次迭代的数据集,循环是(o(log n),因此整个算法是= O(n log n) .

免责声明:绳子对数的例子是从优秀的 Mathematician's Delight book by W.Sawyer 。

你可以直观地认为o(log n)的时间与n中的位数成正比。

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

如果一个操作作出一系列恒定的时间决定,其中每一个决定将被考虑的输入的大小减半(减少3,4,5….),整个操作将花费与输入的大小n的对数基2(基3,基4,基5….)成比例的时间,而不是o(n)。

等等。

我在脑海中想象一个在o(log n)中运行的算法的最好方法是:

如果将问题大小增加一个乘法量(即将其大小乘以10),则只会将功增加一个加法量。

把这个应用到你的二叉树问题上,这样你就有了一个很好的应用:如果你将二叉树中的节点数加倍,那么高度只会增加1(一个累加量)。如果你再加倍,它仍然只增加了1。(显然,我认为它保持平衡)。这样,当问题的规模成倍增加时,你的工作量就不会增加一倍,而只会稍微增加一点。这就是为什么o(log n)算法非常棒的原因。

日志是什么 _乙 (n)?

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

首先我建议你读下面这本书;

Algorithms (4th Edition)

这里是一些函数及其预期的复杂性。数字表明 语句执行频率 。

跟随 大O复杂度图 也取自 bigocheatsheet

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

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

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

分治算法通常有 logn 组件到运行时间。这来自于输入的重复减半。

在二进制搜索的情况下,每次迭代都会丢弃一半的输入。需要注意的是,在big-o符号中,log是log base 2。

编辑:如前所述,日志基数并不重要,但是当得到一个算法的big-o性能时,日志因子将来自减半,因此我认为它是基数2的原因。

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

我将其重新表述为“完整二叉树的高度是log n”。如果您一步一步地向下遍历,那么计算完整二叉树的高度将是o(log n)。

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

对数本质上是指数的倒数。所以,如果函数的每个“步骤”都消除了 因素 原始项目集中的元素,即对数时间算法。

对于树示例,您可以很容易地看到,当您继续遍历时,降低一级节点会减少指数数量的元素。查找按姓名排序的电话簿的流行示例实际上相当于遍历二进制搜索树(中间页是根元素,您可以在每一步推断是向左还是向右)。

这两个案例需要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);
    }

这仅仅意味着此任务所需的时间随log(n)而增长(例如:2s表示n=10,4s表示n=100,…)。阅读维基百科上的文章 Binary Search Algorithm 和 Big O Notation 为了更精确。

O(log n) 指一个函数(或算法,或算法中的步骤),其工作时间与输入大小的对数成正比(在大多数情况下通常是以2为基数,但并不总是以2为基数,在任何情况下,用大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符号, by definition ,常数无关紧要。也由 change of base rule 对于对数,不同底的对数之间的唯一区别是一个常数因子。

简单地说:在你算法的每一步,你都可以把工作减半。(渐近等价于第三,第四,…)

o(log n)有点误导,更确切地说是o(logn _二 n),即(以2为底的对数)。

平衡二叉树的高度是o(log _二 n),因为每个节点都有两个(注意日志中的“2 _二 n)子节点。所以,一棵有n个节点的树有一个 _二 n.名词

另一个例子是二进制搜索,它的运行时间是o(log _二 n)因为每一步你都要把搜索空间除以2。

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

这就是为什么具有对数时间复杂度的算法受到高度追捧:即使对于真正的大n(例如n=10^8),它们的性能也比可接受的要高。

但O到底是什么(log n)

它的确切意思是 n 倾向于 infinity , time 倾向于 a*log(n) 在哪里? a 是一个恒定的比例因子。

或者事实上,它并不完全是这个意思;更可能的是,它的意思是 时间 除以 a*log(n) 倾向于 1 “。

“倾向”在“分析”中具有通常的数学含义:例如,“如果你选择 任何 任意小非零常数 k ,然后我可以找到相应的值 X 这样 ((time/(a*log(n))) - 1) 小于 K 所有的价值观 n 大于 X ."

从广义上讲,它意味着时间方程可能有一些其他的组成部分:例如,它可能有一些恒定的启动时间;但是这些其他的组成部分对于n的大值来说是微不足道的,而a*log(n)是n的主要项。

注意,如果方程是,例如…

时间(n)=A+B log(n)+c n+d n n

…那么这就是o(n的平方),因为无论常数a,b,c和非零d的值是多少, d*n*n 对于任何足够大的n值,项总是支配其他项。

这就是位o表示法的意思:它的意思是“任何足够大的n的主导项的顺序是什么”。

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

现在,如果你能证明,在你的算法的每次迭代中,你截断了这个空间的一小部分,这不小于某个极限,这意味着你的算法运行在o(logn)时间内。

我应该指出,我们在这里讨论的是相对分数极限,而不是绝对分数极限。二进制搜索是一个典型的例子。每走一步,我们就扔掉1/2的问题空间。但二进制搜索并不是唯一的例子。假设,你以某种方式证明了,在每一步,你至少扔掉了问题空间的1/128。这意味着,您的程序仍在O(logn)时间运行,尽管比二进制搜索慢得多。这在分析递归算法时是一个很好的提示。通常可以证明,在每一步递归都不会使用几个变量,这会导致问题空间中某些分数的截断。

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

如果您有一个深度为d、大小为n的m元树,则:

• 遍历整棵树~o(m^d)=o(n)

• 在树上走一条路~o(d)=o(log n到base m)

我可以举一个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的底)是a^x的反函数。

就像说对数是指数的倒数。

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

o(n)和o(log(n))之间的差别很大,类似于o(n)和o(a^n)(a是常数)之间的差别。

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

  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.

似乎这个符号大部分是从数学中取出来的。

本文引用了一句话: D.E. Knuth, "BIG OMICRON AND BIG OMEGA AND BIG THETA", 1976 :

根据这里讨论的问题,我建议 以及计算机科学和数学期刊的编辑, 采用上述符号,除非 更好的选择是 很快就找到了 。

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

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

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

但即使在数学分析中,有时这个符号也被用来表示“c*g(n)>f(n)>0”。

我从大学里就知道这个符号是由德国数学家兰道(1877-1938)提出的。

实际上,如果您有一个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)

每次我们写一个算法或代码时,我们都试图分析它的渐近复杂性。 它不同于它的 时间复杂性 .

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

因为时间复杂度取决于各种参数。
1。物理系统
2。程序设计语言
三。编码风格
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

当输入大小增加时,所做的工作也会增加,并且它独立于任何机器。 如果你想找出工作单位的价值 它实际上依赖于上面指定的参数,它会根据系统和所有的参数而改变。

完整的二进制示例是o(ln n),因为搜索如下:

1 2 3 4 5 6 7 8 9 10 11 12

搜索4会产生3次点击:6次,3次,然后4次。log2 12=3,这是一个很好的近似值,用来表示需要点击的次数。

如果你正在寻找一个基于直觉的答案,我想为你提出两种解释。

1. 想象一下一座很高的山,它的底部也很宽。要到达山顶有两种方法:一种是一条专用的小径,沿着山顶螺旋形延伸,另一种是小露台状的雕刻,用来提供楼梯。现在,如果第一种方法是在线性时间o(n)内到达,那么第二种方法是o(logn)。

2. 想象一下一个接受整数的算法, n 作为输入并按时间比例完成 n 那么它是o(n)或θ(n),但如果它与 number of digits or the number of bits in the binary representation on number 然后算法在o(log n)或θ(logn)时间内运行。

我想补充一点,树的高度是从根到叶的最长路径的长度,节点的高度是从该节点到叶的最长路径的长度。路径是指在两个节点之间遍历树时遇到的节点数。为了达到o(log n)的时间复杂度,树应该是平衡的,即任何节点的子节点之间的高度差应该小于或等于1。因此,树并不总是保证时间复杂度o(log n),除非它们是平衡的。实际上,在某些情况下,在树中搜索的时间复杂度在最坏情况下可能为o(n)。

你可以看看平衡树,比如 AVL tree . 这个方法在插入数据时平衡树,以便在树中搜索时保持(log n)的时间复杂性。