算法设计与分析-习题2.3

目录

1.计算下列求和表达式的值。

2.计算下列和的增长次数。用Θ(g(n))的形式给出，其中g(n)要尽可能简单。

3.x₁,…,xₙ的采样方差n可以这样计算:

4.考虑下面的算法。

a.该算法求的是什么?

b.它的基本操作是什么?

c.该基本操作执行了多少次?

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

e.对该算法进行改进，或者设计一个更好的算法，然后指出它们的效率类型。如果做不到这一点，请试着证明这是不可能做到的。

5.考虑下面的算法。

6.考虑以下算法：

7.通过减少算法所做的加法次数来改进矩阵乘法算法的实现(参见例3)。这种变化会给算法的效率带来什么影响?

8.针对“带锁的门”谜题中所有门的开关总次数(习题 1.1的第12题)，确定其渐近增长次数。

9.证明下面的公式：

10.心算术 如下图所示，在一个10×10的表格中，用相同数字在对应的对角线上填满，心算表格中所有数字之和([Cra07]，|问题1.33)。

11.以下是某重要算法的一个版本，我们会在本书的后面研究这个算法：

a.求该算法的时间效率类型。

b.该算法在效率方面有哪些重要的缺陷？我们如何弥补这个缺陷，来提高该算法的运行速度？

12.冯·诺依曼邻居问题 考虑下列算法：从一个1×1的方格开始，每次都会在上次图形的周围再加上一圈方格，在第n次的时候要生成多少个方格?([Gar99]，根据元胞自动机理论的说法，问题的答案等于n阶冯·诺依曼邻居中的元胞数。)下图给出了n=0,1,2时的结果。

13.页面编号 假设页面从 1 开始连续编号，共有 1000 页。计算所有页码中十进制数字的总个数。

1.计算下列求和表达式的值。

a. 1+3+5+7+…+999=

b. 2+4+8+16+…+1024:2046

:n-1

:(3+n+1)*(n-1)/2=

=

=

=

=

2.计算下列和的增长次数。用Θ(g(n))的形式给出，其中g(n)要尽可能简单。

:

:

：

=

3.x₁,…,xₙ的采样方差n可以这样计算:

其中

或者

根据每个公式，对求方差中需要用到的除法、乘法和加/减运算(加法和减法常常被捆绑在一起)的次数进行计算和比较。

• 公式 1：加减 3n−1，乘 n，除 2
• 公式 2：加减 2n，乘 n+1，除 2
• 比较：公式 2加减更少，整体更高效。

4.考虑下面的算法。

算法 Mystery(n) //输入：非负整数n S←0 fori← 1 to n do S←S+i*i return S

a.该算法求的是什么?

求1到n的平方和

b.它的基本操作是什么?

基本操作是乘法

c.该基本操作执行了多少次?

执行了n次

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

属于Θ(n)

e.对该算法进行改进，或者设计一个更好的算法，然后指出它们的效率类型。如果做不到这一点，请试着证明这是不可能做到的。

改用公式计算，效率提升为Θ(1)

5.考虑下面的算法。

算法 Secret(A[0..n-1]) 输入：n个实数的数组 minval ← A[0] maxval ← A[0] for i ← 1 to n-1 do if A[i] < minval minval ← A[i] if A[i] > maxval maxval ← A[i] return maxval - minval

a. 求数组最大值与最小值的差

b. 基本操作：元素比较

c. 执行2 (n-1) 次

d. 效率：Θ(n)

e.无法改进，因为必须遍历所有元素才能确定最大 / 最小值，已是最优 Θ(n)

6.考虑以下算法：

算法 Enigma(A[0..n-1, 0..n-1]) 输入：n×n 实数矩阵 A for i ← 0 to n-2 do for j ← i+1 to n-1 do if A[i,j] ≠ A[j,i] return false return true

a. 判断矩阵是否对称

b. 基本操作：比较 A [i,j] 和 A [j,i]

c. 最坏执行n (n-1)/2 次

d. 效率：Θ(n²)

e.无法改进，因为要判断是否对称，必须检查所有上三角元素，已是最优 Θ(n²)

7.通过减少算法所做的加法次数来改进矩阵乘法算法的实现(参见例3)。这种变化会给算法的效率带来什么影响?

将矩阵乘法的循环顺序改为i → k → j，利用缓存局部性减少加法开销。

效率影响：渐进时间复杂度仍为 Θ(n3)，但常数因子减小，实际运行更快。

8.针对“带锁的门”谜题中所有门的开关总次数(习题 1.1的第12题)，确定其渐近增长次数。

门 i 被切换的次数 = i 的正因子个数

这个和等于：

因此答案为Θ(nlogn)

9.证明下面的公式：

可以使用数学归纳法，也可以像10岁的高斯(1777—1855)一样，用洞察力来解决该问题。这个小学生长大以后成为有史以来最伟大的数学家之一。

10.心算术 如下图所示，在一个10×10的表格中，用相同数字在对应的对角线上填满，心算表格中所有数字之和([Cra07]，|问题1.33)。

算不来，硬算不丢人

11.以下是某重要算法的一个版本，我们会在本书的后面研究这个算法：

算法 GE(A[0..n-1,0..n]) //输入：一个n行n+1列的实数矩阵A[0..n-1,0..n] for i←0 to n-2 do for j←i+1 to n-1 do for k←n downto i do A[j,k]←A[j,k]-A[i,k]*A[j,i]/A[i,i]

a.求该算法的时间效率类型。

Θ(n^3)

b.该算法在效率方面有哪些重要的缺陷？我们如何弥补这个缺陷，来提高该算法的运行速度？

对于计算中A[j,i]/A[i,i]这一步操作，实际上不需要在最内层循环中重复计算，仅需要在第二层用临时变量存储即可，将除法提到 k 循环外只算一次，可显著提高速度。

12.冯·诺依曼邻居问题 考虑下列算法：从一个1×1的方格开始，每次都会在上次图形的周围再加上一圈方格，在第n次的时候要生成多少个方格?([Gar99]，根据元胞自动机理论的说法，问题的答案等于n阶冯·诺依曼邻居中的元胞数。)下图给出了n=0,1,2时的结果。

13.页面编号 假设页面从 1 开始连续编号，共有 1000 页。计算所有页码中十进制数字的总个数。

9+180+2700+4=2893