我正在学习大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)。这里有一个例子,计算你自己的幂函数,

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/

其他回答

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

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

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

完整的二进制示例是O(ln n),因为搜索结果如下:

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

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

每次编写算法或代码时,我们都会尝试分析其渐近复杂性。它不同于它的时间复杂性。

渐近复杂度是算法执行时间的行为,而时间复杂度是实际执行时间。但有些人可以互换使用这些术语。

因为时间复杂度取决于各种参数。1.物理系统2.编程语言3.编码样式4.还有更多。。。。。。

实际执行时间不是一个很好的分析指标。

相反,我们将输入大小作为参数,因为无论代码是什么,输入都是相同的。因此,执行时间是输入大小的函数。

以下是线性时间算法的示例

线性搜索给定n个输入元素,要搜索数组中的元素,最多需要“n”个比较。换句话说,无论你使用什么编程语言,你喜欢什么编码风格,在什么系统上执行它。在最坏的情况下,它只需要n次比较。执行时间与输入大小成线性比例。

它不仅仅是搜索,无论是什么工作(增量、比较或任何操作),它都是输入大小的函数。

所以当你说任何算法都是O(logn)这意味着执行时间是输入大小n的log倍。

随着输入大小的增加,完成的工作(这里是执行时间)增加。(因此,比例)

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

随着输入大小的增加,所做的工作也会增加,并且与任何机器无关。如果你试图找出工作单位的价值它实际上取决于上述参数。它会根据系统和所有参数而改变。

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

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

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

O(logn)指的是一个函数(或算法,或算法中的步骤),其工作时间与输入大小的对数成正比(大多数情况下通常以2为基数,但并不总是以2为底,在任何情况下,通过big-O符号*,这都是无关紧要的)。

对数函数是指数函数的倒数。换句话说,如果您的输入呈指数增长(而不是通常认为的线性增长),则函数呈线性增长。

O(logn)运行时间在任何一种分而治之的应用程序中都很常见,因为(理想情况下)每次都会将工作减半。如果在每一个除法或征服步骤中,你都在做恒定时间的工作(或不是恒定时间的,但随着时间的增长比O(log n)慢),那么你的整个函数就是O(log)。相当常见的是,每个步骤都需要输入线性时间;这将相当于O(n log n)的总时间复杂度。

二进制搜索的运行时间复杂性是O(logn)的一个例子。这是因为在二进制搜索中,通过将数组分成两半,并且每一步只关注一半,您总是忽略后面每一步的一半输入。每一步都是恒定的时间,因为在二进制搜索中,您只需要将一个元素与关键字进行比较,就可以确定下一步要做什么,而不管您考虑的数组在任何时候都有多大。因此,大约执行log(n)/log(2)步。

合并排序的运行时间复杂性是O(n log n)的一个例子。这是因为每一步都将阵列一分为二,总共约为log(n)/log(2)步。然而,在每一步中,您都需要对所有元素执行合并操作(无论是对n/2个元素的两个子列表执行一次合并操作,还是对n/4个元素的四个子列表执行两次合并操作都是无关紧要的,因为这增加了每一步对n个元素执行合并的必要性)。因此,总复杂度为O(n log n)。

*记住,根据定义,big-O表示法并不重要。同样,通过改变对数的基数规则,不同基数的对数之间的唯一差异是一个常数因子。