5

根据下列函数的增长次数按照从低到高的顺序对他们进行排序：

通过变换再参考下图

即可得出答案，按增长次数从高到低顺序排列如下：

6.a

证明当 ak>0 时，任何多项式p(n)=a_k n^k^+a_(k-1)n^(k-1)^+⋯+a_0属于集合θ(n^k^ )
证：

考虑下面的算法：

算法  Mystery(n)
      //输入：非负整数n
      s = 0
      for i = 1 to n do
          s = s + i * i
      return s

a、该算法求的什么：
1到n 的平方的和
b、它的基本操作是什么: 乘法
c、该操作执行了多少次：由循环可看出执行了n次

考虑下列递归算法

该算法用来计算前n个立方的和

算法    S(n)
        //输入：正整数n
        //输出：前n个立方的和
        if n = 1 return 1
        else return S(n-1) + n*n*n

a.建立该算法的基本操作执行次数的递归关系并求解

M(n) = M(n-1) + 2
     =[ M(n-2) + 2 ] + 2= M(n-2)+ 4
     =M(n-i) +  2i
     =M(1) + 2(n-1) = 2(n-1)

b.如果改成非递归算法，效率如何
非递归算法伪代码：

算法    NonrecS(n)
        //输入：一个正整数n
        //输出：前n个立方的和
        S = 1
        for i = 2 to n do
            S = S + i*i*i
        return S

这种算法的乘法次数为 2(n-1) 与递归算法的基本操作次数相同，但非递归算法没有堆栈相关的时间和空间的开销。

8

a.请基于公式 2^n^=2^n-1^+2^n-1^ 设计一个递归算法。当n是任意非负整数时，该算法能够计算 2^n^ 的值

算法    Power(n)
        //通过上述公式递归计算 2^n
        //输入：非负整数n
        //输出：2^n 的值
        if n = 0 return 1
        else return Power(n-1)+Power(n-1)

b.建立该算法所做的加法运算次数的递推关系式并求解

A(n) = 2A(n-1) + 1, A(0) = 0
A(n) = 2A(n-1) + 1
     =2(2A(n-2) + 1) + 1=4A(n-2) + 2 + 1
     =2^i * A(n-i) + 2^(i-1) + 2^(i-2) +……+ 1
     =2^n - 1

c.为该算法构造一个递归调用树，然后计算它所做的递归调用的次数
递归调用树如图，可看出一共调用了n次

d.算法效率如何？
这是一个非常糟糕的算法，因为它远不如简单地将累加器乘以2n倍。