我正在学习大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)有点误导,更准确地说,它是O(log2n),即(以2为底的对数)。

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

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

其他回答

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

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

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

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

我可以举一个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是常数)。

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