算法设计与分析基础(三)

2023-02-16 20:12:06

算法设计与分析基础(三)

练习题

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

解答：
解答：

即，该多项式的始终值为ak*n^k,则结论成立。
考虑下面的算法：
```
算法Mystery(m)
//输入:非负整数n
S←0
for i←1 to n do
    S←S+i* i
return S
```
a.该算法求的是什么？

求的是1到n的平方和

b.它的基本操作是什么？
基本操作是：乘法 (或者，假定乘法和加法的时间相同，两者中的任何一个)
c.该基本操作执行了多少次？
n次

d.该算法的效率类型是什么？

e.试对该算法进行改进，若不行证明。

使用公式：

直接求出结果
考虑下列递归算法，该算法用来计算前n个立方和：
```
算法S(n)
//输入:正整数n
//输出:前n个立方的和
if n= 1 return 1
else return S(n - 1)+n*n*n 
```
a. 建立该算法的基本操作执行次数的递推关系并求解。

我们可以通过反向替代来解决：

b.如果这个算法和直接了当的非递归算法比较，你做何评价？

非递归的代码是：
```
// 输入：一个正整数n
// 输出： 前n个立方的和
S←1
fori←2 to n do
    S←S+i*i*i
return s
```
这种算法的乘法次数是：

这与递归操作的基本操作数相同，但非递归版本不携带与递归堆栈相关的时间和空间开销。
a.请基于公式2ⁿ=2^n-1+2^n-1设计一个递归算法。当n是任意非负整数时，该算法能够计算2ⁿ的值。
```
算法 Power(n)
// 通过公式递归计算
// 输入： 非负整数n
// 输出：2^n的值
if  n = 0  return 1
else return Power(n-1)+Power(n-1)
```
b.建立该算法所做的加法运算次数的递推关系并求解。