转载

白话数据结构-时间复杂度

每一个函数/算法/数据结构都有一个数学意义上的速度(效率)上限,我们用这个渐进上限就可以描述此函数/算法/数据结构的效率。
常用的几个描述符号为,Big-O, Big-Theta,Little-ho,little-omega, Bit-Omega.
注意,在以下语境中,n的意义为“数据量”,因此默认为大于等于0且不为小数,也因此对于任意算法理论效率的极限为1(只用进行一次计算/操作就可完成任务,而不是0)


Big-O,简称大O,是用来衡量算法效率最常用的符号,可以简单的理解为当数据量趋近于无限大时此算法需要的总时长(上限,意为耗时最长最糟糕的情况)。
例如,某一个算法对于输入数组长度为n时总共要进行的代数计算的次数为:f(n)=4n²-2n+2
当n逐步增大的时候,n的次方的增速远大于2n的增速,在n趋近于无穷大时,此式子的结果可以约等于n的次方----所有的低次方和常数都小的可以忽略,同时系数也变得无关紧要了,可以理解为4乘以无穷大还是等于无穷大。(但其实我们可以忽略系数的原因是在于其定义:此函数在增长到一定程度时总小于一个特定函数的常数倍)
所以对于此式子,其时间复杂度可以写为O(n²)。
一般来说我们见到的算法时间复杂度都是由大O表示的,而大O的计算方法很简单,对于得到的函数式,只用找到次数最高的项,去掉系数以及剩下的低次与常数即可。


Little-oh,简称小o,和大O类似也是用来衡量算法效率的上限的,它和大O最主要的区别在于,对于任意(小)的n,都必须要满足f(n) <o(...),而不只是在n趋近于无穷大才成立,它俩的关系有点类似于≤和<的区别,小o是比大O更“强”的约束。
用数学语言描述的话就是,

当f(n) = o(g(n)):
lim f(n)/g(n) = 0
n→∞

重点:【当一个算法服从一个小o式,它一定服从其大O式】

例如
以下式子都是服从大O,但小o为假:

  • x² ∈ O(x²)
  • x² ∈ O(x² + x)
  • x² ∈ O(200 * x²)

以下式子则大小o都服从:

  • x² ∈ o(x³) 【x²/x³=1/x,x→∞时1/x→0】
  • x² ∈ o(x!)
  • ln(x) ∈ o(x)

很明显,对于给出的函数式,其服从的小o式不止一个。


little-omega,写作ω(),是算法耗时的下限。它和小o一样,是强约束。
数学语言描述为:

当f(n) = ω(g(n)):
lim f(n)/g(n) = ∞
n→∞

例如
4n + 6 ∈ ω(1)【4n + 6 在n→∞时 趋近于∞】


Big-omega Ω()和大O比较类似,相对较少用到,是一个算法时间效率的下限(意为用时最少的最佳情况所需的基础时间),定义类比于大O,为:此函数在增长到一定程度时总大于一个特定函数的常数倍。


Big-Theta,写作Ө(),就是上下限的渐进函数一致(大O和大Ω一样)。
意即 x1Ө(...)≤ f(n) ≤x2Ө(...)成立,其实一般常见情况算法(所有的多项式)都是服从某个Ө(...)的。


对于常见的时间复杂度函数,下面这张图可以给一个直观的大小概念:

img

渐进1

下面是一个更接近实际数值的图:

img

渐进2

下面是各种数据结构与相应操作的时间复杂度:

img

数据结构的时间复杂度

常见排序算法的时间复杂度:

img

排序算法的时间复杂度

作者:Kaidi_G
链接:https://www.jianshu.com/p/19958b6ad34a
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

正文到此结束