我正在学习大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,但我不知道如何识别具有对数时间的函数。


当前回答

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

这就是为什么对数时间复杂度算法备受追捧的原因:即使对于真正大的n(例如,假设n=10^8),它们的性能也超出了可接受的范围。

其他回答

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

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

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

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

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

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

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

想象一下一座很高的山,它的底部也很宽。要到达山顶,有两种方式:一种是一条围绕山顶螺旋延伸的专用通道,另一种是切割出的小露台状雕刻,以提供楼梯。现在,如果第一种方式在线性时间O(n)内到达,则第二种方式是O(logn)。想象一个算法,它接受整数n作为输入,并在时间上与n成比例地完成,那么它是O(n)或θ。

对数运行时间(O(log n))本质上意味着运行时间与输入大小的对数成比例增长-例如,如果10个项目最多需要一定的时间x,100个项目最多花费2倍,10000个项目最多耗费4倍,那么它看起来像是O(log n)时间复杂性。

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

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

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

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

算法(第4版)

下面是一些函数及其预期的复杂性。数字表示语句执行频率。

以下Big-O复杂性图表也取自bigocheatsheet

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

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

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