算法复杂度求法初学

    参考：http://www.comp.nus.edu.sg/~xujia/mirror/algorithm.myrice.com/algorithm/

    有空演习了一点点。

    递归方程算法复杂性求法之：迭代法

    注：T()函数等于php中的floor()函数

    1、T(n) = n^2 + 2T(n/2)

    n^2 + 2T(n/2)

    n^2 + (n/2)^2 + 2T(n/4)

    n^2 + (n/2)^2 + (n/4)^2 + 2T(n/8)

    …

    n^2 + (n/2)^2 + (n/4)^2 + (n/8)^2 + (n/16)^2 + … + (n/2^(2i))^2 + 2T(n/2^(2i))

    n^2(1 + 1/2^2 + 1/2^4 + 1/2^6 + …)

    渐进 = n^2

    2、T(n) = n + T([n/3])+ T([2n/3])

    n + T(n/3)+ T(2n/3)

    n + n/3 + T(n/3^2) + T(2n/3^2) + 2n/3 + T(2n/3^2) + T(n(2/3)^2)

    = 2n + …(4 items)

    2n + n/3^2 + 2n/3^2 + 2n/3^2 + n(2/3)^2 + (8 items)

    = 3n + …(8 items)

    …

    in + (2^i items)

    i为递归次数，有限。items最后都趋于0。

    i是多少次？取决于每次的最大值。每次的最大值分别是：n,n(2/3),n(2/3)^2,n(2/3)3,…,1

    i=log(3/2)n

    渐进 = log(3/2)n * n