算法导论 思考题 4-3_算法导论 4-3 答案

a. 利用主方法可得，T(n)=θ(n的log₃⁴次方)

b. n/f(n)=lgn，不能应用主方法

    共log₃ⁿ+1层，每层代价n/lg ^{n/(3的i次方)}，最后一层共n个θ(1)的结点，代价为θ(n)

    T(n)=∑n/lg ^{n/(3的i次方)}+θ(n)

           <∑n/lgn+θ(n)

           =n*log₃²+θ(n)

           =O(n)

    又因为T(n)最后一层代价为θ(n)，所以T(n)=Ω(n)

    综上，T(n)=θ(n)

c. 利用主方法可得，T(n)=θ(n ^5/2)

d. 利用主方法可得，T(n)=θ(n)

e. n/f(n)=lgn，不能应用主方法

    共lgn+1层，每层代价n/lg ^{n/(2的i次方)}，最后一层共n个θ(1)的结点，代价为θ(n)

    T(n)=∑n/lg ^{n/(2的i次方)}+θ(n)

            <∑n/lgn+θ(n)

            =O(n)

    又因为T(n)最后一层代价为θ(n)࿰