浅谈时间复杂度的计算和主定理


前言

时间复杂度是算法的重要衡量标准。尤其在一些分治算法中,时间复杂度不是那么方便可以计算。故特写此文,简单地谈一谈复杂度的计算方法。


约定

一些相关的渐近符号,大O是最经常使用的比较函数的渐近符号。

符号 定义
f(n)=\mathrm {O} (g(n)) 渐近上限,即f(n)多项式地小于g(n)
f(n)=o(g(n)) Asymptotically negligible渐近可忽略不计( \lim {}{\frac {f(n)}{g(n)}}=0
f(n)=\Omega (g(n)) 渐近下限(当且仅当g(n)=\mathrm {O} (f(n))),即f(n)多项式地大于g(n)
f(n)=\omega (g(n)) Asymptotically dominant渐近主导(当且仅当g(n)=o(f(n))
f(n)=\Theta (g(n)) Asymptotically tight bound渐近紧约束(当且仅当f(n)=\mathrm {O} (g(n))f(n)=\Omega (g(n))

当然,对于本文,你仅需要了解第1、3、5个记号。

注意

大O符号经常被误用:有的作者可能会使用大O符号表达大\Theta符号的含义。因此在看到大O符号时应首先确定其是否为误用。


复杂度的计算

一般常用T(n)表示算法的时间复杂度和输入规模n的关系。

尤其在分治算法中,T(n)通常满足如下递推关系式:

T(n)=aT(\frac {n} {b} ) + f(n)

表示算法将当前问题分为了a个规模为\frac {n} {b}的子问题,当前层复杂度为f(n).

主定理

在分析算法复杂度时,主定理(Master Theorem, 一下简称M.T.)提供了用渐进符号表示许多由分治法得到的递推关系式的方法。

通用形式

令一个指数c_{crit}=log_ba.

形如T(n)=aT(\frac {n} {b})+f(n)的递归算法通常满足如下三种情况:

Case Discription Condition on f(n) in relation to c_{crit} M.T. bound
1 分解/重组的工作量相比子问题显得微不足道(即递归树的叶节点较重) f(n)=O(n^c), c < c_{crit} T(n)=\Theta (n^{c_{crit}})
2 分解/重组的工作量与子问题相当 \forall k\ge 0, f(n)=\Theta (n^{c_{crit}}log^kn) T(n)=\Theta (n^{c_{crit}}log^{k+1}n)
3 分解/重组的工作量主宰子问题(即递归树是根重的) f(n)=\Omega(n^c), c> c_{crit}且对于常数k < 1和一个足够大的n,满足af(\frac {n} {b})\le kf(n) T(n)=\Theta (f(n))

对于Case 2还有一些有用的拓展:

Case Condition on f(n) in relation to c_{crit} M.T. bound
2a \exists k > -1, f(n)=\Theta (n^{c_{crit}}log^kn) T(n)=\Theta(n^{c_{crit}}log^{k+1}n)
2b for k=-1, f(n)=\Theta (n^{c_{crit}}log^kn) T(n)=\Theta (n^{c_{crit}}loglogn)
2c \exists k< -1, f(n)=\Theta (n^{c_{crit}}log^kn) T(n)=\Theta (n^{c_{crit}})

本质

如何去理解主定理呢?比如,对于T(n)=aT(\frac {n} {b})+f(n),令n=b^k,则T(b^k)=aT(b^{k-1})+f(b^k),将这个式子展开,最后会得到T(b^k)=a^kT(1)+\sum\limits_{i=0}^{k}a^if(b^{k-i}).由于k=log_bn,那么a^kT(1)就可以化为n^{log_ba}(即上面记的n^{c_{crit}});对于和式\sum\limits_{i=0}^{k}a^if(b^{k-i}),我们就需要对于f(n)展开讨论了,这也就是为什么主定理会分这么多中情形。最后根据渐进时间复杂度的定义,得到结果。

例题

  1. T(n)=3(T/2)+n^2

    g(n)=n^{log_23}, g(n)=O(f(n)), Case 3, T(n)=\Theta (n^2)

  2. T(n)=7T(n/2)+n^2

    g(n)=n^{log_27}, g(n)=\Omega(f(n)), Case 1, T(n)=\Theta(n^{lg7})

  3. T(n)=4T(n/2)+n^2

    g(n)=n^2, g(n)=\Theta (f(n)), Case 2, T(n)=\Theta (n^2lgn)

  4. T(n)=3T(n/4)+nlgn

    g(n)=n^{log_43}, g(n)=O(f(n)), Case 3, T(n)=\Theta (nlgn)

  5. T(n)=4(T/2)+lgn

    g(n)=n^2, g(n)=\Omega (f(n)), Case 1, T(n)=\Theta (n^2)

  6. T(n)=4(T/2)+n^2lgn

    g(n)=n^2lgn, g(n)=\Theta (f(n)), extended Case 2, T(n)=\Theta (n^2lg^2n)

  7. T(n)=5T(n/2)+n^2lgn

    g(n)=n^{log_25}, f(n)=O(g(n)), Case 1, T(n)=\Theta (n^{lg5})

  8. T(n)=T(n/4)+lgn

    g(n)=lgn, g(n)=O(f(n)), extended Case 2, T(n)=\Theta (lg^2n)

  9. T(n)=2T(n/4)+lgn

    g(n)=n^{log_42}, g(n)=\Omega (f(n)), Case 1, T(n)=\Theta (n^{1/2})

  10. T(n)=3T(n/3)+nlgn

    g(n)=nlgn, g(n)=\Theta (f(n)), extended Case 2, T(n)=\Theta (nlg^2n)


附录


参考资料

  • Wikipedia-M.T.
  • MIT Introduction to Algorithms: Master Theorem Worksheet Solutions

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注