我正在学习大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(logN)基本上意味着时间线性上升,而N指数上升。因此,如果计算10个元素需要1秒,则计算100个元素需要2秒,计算1000个元素需要3秒,依此类推。

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

其他回答

这个问题已经有了很多好的答案,但我相信我们真的错过了一个重要的答案,那就是图解的答案。

说一个完整的二叉树的高度是O(logn)是什么意思?

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

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

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

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

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

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

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

等等

如果您有一个函数需要:

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.

然后需要log2(n)时间。广义地说,大O符号意味着关系只需要对大n成立,常数因子和小项可以忽略。

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

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

搜索4个会产生3次命中:6次,3次,然后4次。而log2 12=3,这是一个很好的近似值,以多少命中需要。

我可以举一个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(n)与O(a^n)之间的区别(a是常数)。