算法|算法分析（复发）|问题6-yiteyi-C++库

算法的运行时间由以下递推关系表示：

null

    if  n <= 3  then   T(n) = n
    else T(n) = T(n/3) + cn

以下哪一项代表算法的时间复杂度？（A） $heta$ （n）（B） $heta$ （n日志n）（C） $heta$ （n^2）（D） $heta$ （n^2log n） （A） A. （B） B （C） C （D） D 答复: （A） 说明：

T(n) = cn + T(n/3)
     = cn + cn/3 + T(n/9)
     = cn + cn/3 + cn/9 + T(n/27)
Taking the sum of infinite GP series. The value of T(n) will
be less than this sum.
T(n) <= cn(1/(1-1/3))
     <= 3cn/2

or we can say 
cn <= T(n) <= 3cn/2
Therefore T(n) = (n)

这也可以通过使用主定理用于解决复发问题。给定的表达式位于案例3 关于这个定理。这个问题的小测验

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章