我正在学习大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(n)内到达,则第二种方式是O(logn)。想象一个算法,它接受整数n作为输入,并在时间上与n成比例地完成,那么它是O(n)或θ。

其他回答

对数

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

想象一下,我们有一根绳子,把它拴在一匹马身上。如果绳子直接系在马身上,那么马拉离(例如,从人身上)所需的力直接为1。

现在想象绳子绕在一根杆子上。要想脱身的马现在必须用力拉很多倍。次数取决于绳索的粗糙度和杆的大小,但我们假设它会将一个人的力量乘以10(当绳索完全转弯时)。

现在,如果绳子绕一圈,马需要用力拉10倍。如果人类决定让马变得很困难,他可以再次将绳子绕在一根杆子上,使它的力量增加10倍。第三个循环将再次将强度增加10倍。

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

3是1000的对数,6是1000000的对数(以10为底)。

那么O(log n)实际上是什么意思?

在上面的例子中,我们的“增长率”是O(logn)。每增加一圈,我们的绳子所能承受的力就会增加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次尝试(与对数相关,这里我们需要7次猜测128个值范围,10次猜测1024个值范围。7是128的对数,10是1024的对数(以2为底))。

注意,我用粗体字“最多”。大O符号总是指更坏的情况。如果你运气好,你可以一次猜出数字,所以最好的情况是O(1),但那是另一回事。

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

O(n log n)呢?

你最终会遇到一个线性时间O(n log(n))算法。上述经验法则再次适用,但这一次对数函数必须运行n次,例如,将列表的大小减少n次,这在合并排序等算法中发生。

您可以很容易地确定算法时间是否为n log n。寻找一个在列表(O(n))中迭代的外部循环。然后查看是否存在内部循环。如果内部循环在每次迭代时都在切割/减少数据集,则该循环为(O(logn)),因此整个算法为=O(n logn)。

免责声明:绳对数示例摘自W.Sawyer的《数学家的喜悦》一书。

O(logn)有点误导,更准确地说,它是O(log2n),即(以2为底的对数)。

平衡二叉树的高度是O(log2n),因为每个节点都有两个(注意log2n中的“两个”)子节点。因此,具有n个节点的树的高度为log2n。

另一个例子是二进制搜索,它的运行时间为O(log2n),因为在每一步中,您都将搜索空间除以2。

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

算法(第4版)

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

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

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

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

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

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

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

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

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

  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,《大OMICRON、大OMEGA和大THETA》,1976年:

基于这里讨论的问题,我建议SIGACT以及计算机科学和数学期刊的编辑,采用上面定义的符号,除非有更好的替代方案很快就会发现。

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


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

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

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

我从大学里就知道,这个符号是由德国数学家朗道(1877-1938)创造的