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


当前回答

你可以通过说时间与N中的位数成正比来直观地想到O(log N)。

如果一个操作对输入的每个数字或位执行恒定的时间工作,则整个操作所花费的时间将与输入中的数字或位的数量成比例,而不是与输入的大小成比例;因此是O(log N)而不是O(N)。

如果一个操作做出一系列恒定的时间决定,每个决定将要考虑的输入的大小减半(减少3、4、5…的因子),那么整个过程将花费与输入大小N的对数基2(基3、基4、基5…)成比例的时间,而不是O(N)。

等等

其他回答

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

这两种情况需要O(log n)时间

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

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

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

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

你可以通过说时间与N中的位数成正比来直观地想到O(log N)。

如果一个操作对输入的每个数字或位执行恒定的时间工作,则整个操作所花费的时间将与输入中的数字或位的数量成比例,而不是与输入的大小成比例;因此是O(log N)而不是O(N)。

如果一个操作做出一系列恒定的时间决定,每个决定将要考虑的输入的大小减半(减少3、4、5…的因子),那么整个过程将花费与输入大小N的对数基2(基3、基4、基5…)成比例的时间,而不是O(N)。

等等

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

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

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

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

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