算法第一次上机习题讲解

note：

• 注意到其实近几年的考题，画递归树基本没有。2022也没有需要画递归树的题目
• 较难的计算题，比如本文中指出的需要减去一个低阶项的题目，其实也不会考察，基本都是考察【主方法】，PPT上的题会就行。
  本人也觉得算法分析与设计课考察不应该重视这方面的数学考察，整张卷子最后的设计题才是应有的趋势

1.Key Point 1

常考题型判断题：

$$\Theta ,\Omega ，O$$的表示，熟悉三者的定义：

• $$\Theta$$表示渐近紧致界
• $\Omega$表示渐近下界
• O表示渐近上界

真题Example：

判断$nlgn=O(n^2)$是否正确——考察O的定义
$$\begin{gathered} 根据定义:nlgn\le c{n}^2，当c>1时恒成立 \\ 成立 \end{gathered}$$

2. Key Point 2

常考大题：

递归树求解递归式，考察方式有两种：

• 指定方法：递归树、替换法
• 任意方法

2.1 递归树的画法

$$T(n)=aT(n/b)+f(n)$$

递归树的表示：

• 树根要标对
• 最后叶子全写成T(1)。（若让证明的是O或者$\theta$，那么也可以写成$O(1)$或者$\Theta (1)$，但是写成T(1)肯定对）

扣分点：

• 树高要写上：$$lo{g}_b^n$$，可以直接写成$l{g}^n$

• 最后一层的开销：叶子数目乘以T(1)
  $$\begin{gathered} leaves=a^h=a^{lo{g}_b^n}=n^{lo{g}_b^a} \\ 最后一层的花销：n^{lo{g}_b^a}T(1) \end{gathered}$$

Example 4.4-1

• 确定上界
  $$\begin{gathered} (1+\frac{3}{2}+...+(\frac{3}{2}{)}^{l{g}^n-1})+O(n^{lg3}) \\ =\frac{1-(\frac{3}{2}{)}^{lgn}}{1-\frac{3}{2}}n+O(n^{lg3}) \\ =O(n^{l{g}^3}) \end{gathered}$$

• 证明

常见错误解法——

此题有一个小技巧，当直接证明无法得证时，减去一个低阶项，修改猜测的边界，这里是cn

预证明：$$T(n)=O(n^{l{g}^3})$$，即证$T(n)\le c{n}^{l{g}^3}-cn$

假设：$$T(n/2)\le c(n/2{)}^{l{g}^3}-c(n/2)$$成立，有
$$\begin{gathered} T(n)=3T(n/2)+n \\ \le 3(c(n/2{)}^{l{g}^3}-c(n/2))+n \\ =3c(n/2{)}^{l{g}^3}-3c(n/2)+n \\ =c{n}^{l{g}^3}-((3c-2)/2)n \\ \le c{n}^{l{g}^3}-cn \\ 上式当(3c-2)/2\ge c时成立，即c\ge 2时成立 \end{gathered}$$
最后一行是我们添加的，必须给出c的取值范围。

---

Example 4.3-2

The recurrence $$T(n)=7T(n/2)+n^2$$ describes the runing time of an algorithm A. A competing algorithm A has a running time
of $$T^{\prime }(m)=a{T}^{\prime }(n/4)+n^2$$. What is the largest integer value for a such that A’ is asymptotically faster than A?

依题意有：
$$\begin{gathered} lo{g}_4^a<lo{g}_2^7=lo{g}_4^{49} \\ 故a<49，\therefore a的最大整数取值是48 \end{gathered}$$

2.2 真题

2.2.1 真题1

Draw the recurion tree for $$T(n)=4T(\lfloor n/2\rfloor )+cn$$， where c is a constant, and provide a tight asympotic bound on its solution. Verify your bound by the substitution method.

提示：向下取整不需要画出，a = 1时不用分支

• 猜测紧致界

首先画出递归树，以得到一个较好的猜测：

---

$$\begin{gathered} 总开销=cn(1+2+2^2+...+2^{lgn}) \\ =cn\cdot \frac{1-2^{lgn+1}}{1-2}=2cn(n^{lg2}-\frac{1}{2}) \\ =2cn(n-\frac{1}{2})=O(n^2)=\Omega (n^2) \end{gathered}$$

• 替换法证明

---

先证明$$T(n)=O(n^2)$$，即证明$$T(n)\le k{n}^2-kn$$

假设$$T(n/2)\le k(\frac{n}{2}{)}^2-k\frac{n}{2}$$成立，有：
$$\begin{gathered} T(n)=4T(n/2)+cn \\ \le 4(k(\frac{n}{2}{)}^2-k\frac{n}{2})+cn \\ =k{n}^2-(2k-c)n \\ \le k{n}^2-kn \\ 上式当k\le 2k-c,即k\ge c时成立，即T(n)=O(n^2) \end{gathered}$$

---

再证明$$T(n)=\Omega (n^2)$$，即证明$$T(n)\ge k{n}^2-kn$$

假设$$T(n/2)\ge k(\frac{n}{2}{)}^2-k(\frac{n}{2})$$成立，有：
$$\begin{gathered} T(n)=4T(n/2)+cn \\ \ge 4(k(\frac{n}{2}{)}^2-k(\frac{n}{2}))+cn \\ =k{n}^2-(2k-c)n \\ \ge k{n}^2-kn \\ 上式当k\ge 2k-c,即k\le c时成立，即T(n)=O(n^2) \end{gathered}$$

---

综上所述，当 k = c 时，有$$T(n)=\Theta (n^2)$$

2.2.2 真题2

Given the following recurrence: $$T(n)=4T(n/2)+n^{2}lgn$$. Given an asymptotic upper bound for this recurrence.

（1）方法1：使用主定理的推论：

$$\begin{gathered} f(n)=n^{2}lgn,n^{lo{g}_2^4}=n^2 \\ f(n)=\Theta (n^{2}l{g}^{k}n)，其中k=1 \\ 所以T(n)=\Theta (n^{2}l{g}^{2}n)=\Theta ((nlgn{)}^2) \end{gathered}$$

（2）方法2：使用递归树

$$\begin{gathered} n^2(lgn+lg\frac{n}{2}+lg\frac{n}{2^2}+...+lg\frac{n}{n})=n^2(lgn-0+lgn-lg2+lgn-lg{2}^2+...+lgn-lgn) \\ =n^2(lgn(lo{g}_2^n+1)-lg{2}^{\frac{1+lo{g}_2^n}{2}})=n^2(1+lgn)(lgn-\frac{1}{2}lgn)=\frac{1}{2}{n}^2(1+lgn)lgn=\Theta (n^2(lgn{)}^2) \end{gathered}$$