我正在学习大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)时间内运行。

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

其他回答

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

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

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

这仅仅意味着该任务所需的时间随着log(n)的增加而增加(例如:n=10时为2s,n=100时为4s,…)。请阅读维基百科关于二进制搜索算法和大O符号的文章以了解更多的精度。

我一直以来在脑海中想象运行在O(log n)中的算法的最佳方式如下:

如果您将问题大小增加一个乘法量(即将其大小乘以10),则做功仅增加一个加法量。

将此应用于二叉树问题,这样您就有了一个很好的应用程序:如果将二叉树中的节点数加倍,则高度仅增加1(一个加法量)。如果再增加一倍,它仍然只增加了1。(显然,我假设它保持平衡)。这样,当问题规模成倍增加时,你的工作量不会加倍,而只是做了稍微多一点的工作。这就是为什么O(logn)算法非常棒的原因。

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

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