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


当前回答

logx到基b=y是b^y=x的倒数

如果有深度为d、大小为n的M元树,则:

遍历整棵树~O(M^d)=O(n)在树中行走一条路径~O(d)=O(logn到基M)

其他回答

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

  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)创造的

logb(n)是什么?

它是指在达到尺寸为1的截面之前,可以将长度为n的原木重复切成b等份的次数。

大O符号仅供参考。这可能会有所帮助!

大O----------------排序---------------复杂性

O(log N)     -Binary search      - logarithmic

O(N)         -Simple search      - Linear

O(N*log N)   -Quicksort          - loglinear 

O(2^N)       -recursive          - Exponential

O(N2)        -Selection sort     - directly proportional to the square of the input size.

分而治之范式中的算法具有复杂性O(logn)。这里有一个例子,计算你自己的幂函数,

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

从…起http://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/

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

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

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