欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

大O

程序员文章站 2022-03-25 16:58:02
表示时间的大O符号,是用来描述算法效率的语言和度量单位。不彻底理解这个概念,不仅会影响你做出清晰的判断,还会让你无法评价算法的优劣。 常量不算在运算时间里。 例如某个O(2N)的算法实际上是O(N)。特定输入中,O(N)很有可能会比O(1)代码还要快。大O仅仅描述了增长的趋势。 丢弃不重要的项 应该 ......

表示时间的大o符号,是用来描述算法效率的语言和度量单位。不彻底理解这个概念,不仅会影响你做出清晰的判断,还会让你无法评价算法的优劣。

  • 常量不算在运算时间里。

例如某个o(2n)的算法实际上是o(n)。特定输入中,o(n)很有可能会比o(1)代码还要快。大o仅仅描述了增长的趋势。

  • 丢弃不重要的项

应该舍弃无关紧要的项。比如 o(n2+n)变成o(n2)、o(n+logn)变成o(n)、o(5*2^n+1000n^100)变成o(2^n)等。

  •  logn运行时间

元素的个数每次减半,它的运行时间很可能是o(logn)。

以二分查找为例。假设一个排序数组长度为n,目标值为x。首先比较x与中值,如果x等于中值直接返回,如果小于中值,搜索数组的左边,如果大于中值,搜索数组的右边。

开始时有n个元素的排序数组要搜索,经过一次搜索之后,还剩下n/2个元素,再一次,剩下n/4个元素,直到找到目标值或者待搜索元素个数为1时才停止搜索。

同理,在平衡二叉搜索树中查找一个元素也是o(logn),每次比较,非左即右。

  • 递归的运行时间

当一个多次调用自己的递归函数出现时,它的运行时间往往是o(分支数^数的深度),分支数即每次调用自己的次数。

例如:

int f(int n) {
  if (n <= 1) {
    return 1;
  }
  return f(n-1) + f(n-1);
}

运行时间是o(2^n)。

这个例子的空间复杂度为o(n),尽管树节点总数为o(2^n),但同一时刻只有o(n)个节点存在。