我正在学习大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个元素的列表,并从该列表中创建一个二叉树(就像在除法和征服算法中一样),您将一直除以2,直到达到大小为1的列表(树叶)。

在第一步,你除以2。然后,您有2个列表(2^1),将每个列表除以2,因此您有4个列表(2*2),然后再进行一次除法,您有8个列表(3^3),依此类推,直到列表大小为1

这给出了一个等式:

n/(2^步)=1<=>n=2^步<=>lg(n)=步

(取每边的lg,lg为对数基数2)

其他回答

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

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

因为时间复杂度取决于各种参数。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

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

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

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

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

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

首先,我建议您阅读以下书籍:;

算法(第4版)

下面是一些函数及其预期的复杂性。数字表示语句执行频率。

以下Big-O复杂性图表也取自bigocheatsheet

最后,非常简单的展示展示了它是如何计算的;

剖析程序的语句执行频率。

分析程序的运行时间(示例)。

我可以补充一些有趣的东西,很久以前我在科尔曼等的书中读过。现在,想象一个问题,我们必须在问题空间中找到解决方案。这个问题空间应该是有限的。

现在,如果你能证明,在你的算法的每一次迭代中,你都切断了这个空间的一部分,这不小于某个极限,这意味着你的算法在O(logN)时间内运行。

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