我正在学习大O符号的运行时间和摊销时间。我理解O(n)线性时间的概念,这意味着输入的大小成比例地影响算法的增长。。。例如,二次时间O(n2)等也是如此。甚至是通过阶乘增长的算法,如置换生成器,其O(n!)次。

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

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

类似地,如果存在嵌套循环,时间将为O(n2)。

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

我确实知道(也许不是很详细)对数是什么,从这个意义上说:log10 100=2,但我不知道如何识别具有对数时间的函数。


当前回答

我一直以来在脑海中想象运行在O(log n)中的算法的最佳方式如下:

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

将此应用于二叉树问题,这样您就有了一个很好的应用程序:如果将二叉树中的节点数加倍,则高度仅增加1(一个加法量)。如果再增加一倍,它仍然只增加了1。(显然,我假设它保持平衡)。这样,当问题规模成倍增加时,你的工作量不会加倍,而只是做了稍微多一点的工作。这就是为什么O(logn)算法非常棒的原因。

其他回答

O(logn)是衡量任何代码运行时性能的多项式时间复杂度之一。

我希望你已经听说过二进制搜索算法。

假设您必须在大小为N的数组中找到一个元素。

基本上,代码执行如下N不适用于2不适用于4N/8…等

如果你把每一级所做的所有工作相加,你将得到n(1+1/2+1/4….),等于O(logn)

你可以通过说时间与N中的位数成正比来直观地想到O(log N)。

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

如果一个操作做出一系列恒定的时间决定,每个决定将要考虑的输入的大小减半(减少3、4、5…的因子),那么整个过程将花费与输入大小N的对数基2(基3、基4、基5…)成比例的时间,而不是O(N)。

等等

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

在二进制搜索的情况下,每次迭代都会丢弃一半的输入。需要注意的是,在Big-O表示法中,log是以2为底的log。

编辑:如上所述,对数基数并不重要,但当推导算法的Big-O性能时,对数因子将来自减半,因此我认为它是基数2。

概述

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

首先,你需要对对数有一个大致的了解,你可以从https://en.wikipedia.org/wiki/Logarithm . 自然科学使用e和自然日志。工程弟子将使用log_10(对数基数10),计算机科学家将大量使用log_2(对数基数2),因为计算机是基于二进制的。有时你会看到自然log的缩写为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。注意我从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次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))-log(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(logn)是什么意思?

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

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

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

在一张普通纸上绘制对数(n)将生成曲线图,其中曲线的上升速度随着n的增加而减慢: