我正在学习大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(ln n),因为搜索结果如下:

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

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

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

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

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

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

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

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

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

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

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

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

分而治之范式中的算法具有复杂性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/