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


当前回答

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

其他回答

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

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

因为时间复杂度取决于各种参数。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)是衡量任何代码运行时性能的多项式时间复杂度之一。

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

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

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

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

在信息技术中,它意味着:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.

看来这个符号主要是从数学中提取出来的。

本文引用了一句话:D.E.Knuth,《大OMICRON、大OMEGA和大THETA》,1976年:

基于这里讨论的问题,我建议SIGACT以及计算机科学和数学期刊的编辑,采用上面定义的符号,除非有更好的替代方案很快就会发现。

今天是2016年,但我们今天仍然使用它。


在数学分析中,这意味着:

  lim (f(n)/g(n))=Constant; where n goes to +infinity

但即使在数学分析中,有时这个符号也用于表示“C*g(n)>f(n)>0”。

我从大学里就知道,这个符号是由德国数学家朗道(1877-1938)创造的

我想补充一点,树的高度是从根到叶的最长路径的长度,节点的高度是该节点到叶的最大路径的长度。路径表示在两个节点之间遍历树时遇到的节点数。为了实现O(logn)时间复杂度,树应该是平衡的,这意味着任何节点的子节点之间的高度差应该小于或等于1。因此,树并不总是保证时间复杂度O(log n),除非它们是平衡的。实际上,在某些情况下,在最坏情况下,树中搜索的时间复杂度可能为O(n)。

你可以看看平衡树,比如AVL树。这项工作是在插入数据时平衡树,以便在树中搜索时保持(logn)的时间复杂度。