文章目录

• 2 算法效率分析基础
• • 2.1 通用框架
  • • 输入规模
    • 运行时间
    • • 什么是增长次数和常数倍？
    • 不同类型输入
    • Exercise 2.1
  • 2.2 效率表示符号
  • • 三种符号
    • 利用极限比较增长次数
    • 基本效率类型
    • Exercise 2.2
  • 2.3 非递归算法的数学分析
  • • Exercise 2.3
  • 2.4 递归算法的数学分析
  • • 待完善
    • Exercise 2.4
  • 2.5 计算第n个斐波那契数
  • • Exercise 2.5
  • 2.6 算法的经验分析（重看）
  • • Exercise 2.6
  • 2.7 算法可视化

2 算法效率分析基础

算法分析主要是指算法效率分析，原因有二：算法效率可精确定量研究；算法特性中最重要的。

本章内容结构如下：

1. 算法效率分析的通用框架
2. 算法效率的符号表示
3. 非递归算法的效率分析
4. 递归算法的效率分析
5. 特殊递归算法-斐波那契：无法计算效率
6. 其余分析算法的方法(除3、4所用的数学表示)：经验分析和可视化分析

2.1 通用框架

算法效率包括时间和空间，本章主要以时间为例，空间采用类似方法。

如何衡量算法效率？

1. 算法效率受什么影响？计算机性能、输入规模
2. 用什么衡量？运行时间、运行次数
3. 对于任何输入，效率均相同？

根据以上问题依次回答。

输入规模

算法效率定义：一个以输入规模n为参数的函数

如何度量输入规模：

1. 考虑算法输入的类型：

   两个矩阵相乘的输入规模：第一种是矩阵的阶数n；第二种是矩阵（非方矩阵）中元素个数。

2. 考虑算法细节：

   拼写检查：一是英文字符个数；二是中文字符个数。

   判断一个数是否为质数：数的二进制位数？？

运行时间

基本操作的执行次数C(n)，一般为循环内层的操作。

耗时操作：除法最耗时–>乘法–>加法或减法

对于大规模输入，效率分析主要关注增长次数及其常数倍， 故算法效率公式可忽略乘法常量。

什么是增长次数和常数倍？

比如顺序查找，效率为 1 2 n 2 \frac{1}{2} n^2 21​n2，若规模增长为$m=2n$，则增长倍数为 1 2 ( 2 n ) 2 / 1 2 n 2 = 4 \frac{1}{2} (2n)^2 / \frac{1}{2} n^2 = 4 21​(2n)2/21​n2=4，或者 1 2 m 2 / 1 2 ( 1 / 2 ∗ m ) 2 = 4 \frac{1}{2} m^2 / \frac{1}{2} (1/2*m)^2 = 4 21​m2/21​(1/2∗m)2=4，增长次数为 1 2 ∗ 3 n 2 \frac{1}{2}*3n^2 21​∗3n2，或者 1 2 ∗ 3 / 4 m 2 \frac{1}{2}*3/4 m^2 21​∗3/4m2

反复领悟 ：若规模为 m = n 2 m = n^2 m=n2，则增长倍数为原来的$m$倍，增长次数为 n 4 − n 2 n^4 - n^2 n4−n2，以当前规模为参数，则增长次数为 m 2 − 1 m^2-1 m2−1，仍属于 O ( n 2 ) O(n^2) O(n2)，$n$表示当前输入规模，不是某个固定值。

综上：增长倍数比较好理解，增长次数等同于增长倍数
l o g a n = l o g a b l o g b n log_an = log_ab log_bn loga​n=loga​blogb​n
根据上述公式发现，不同的底数，对数函数的变化仅是一个常量，不影响算法效率的计算。

import math
math.log(4,2) == math.log(4,3)*math.log(3,2)

不同类型输入

算法运行时间不仅取决于输入规模，还取决于输入细节。

以顺序查找为例，在数组arr[1,…,n]中查找元素：

1. 若查找元素即arr[1]，则只需比较一次；最优效率
2. 若查找元素为arr[n]或不在数组中，则需比较n次；最坏效率
3. 若查找元素处于arr任意位置；平均效率

同一规模不同类型的输入，其效率亦不同。

摊销效率：求不相交集合并集时说明

Exercise 2.1

1 分析算法

1. 计算n个数的和

   1. 输入规模:n
   2. 基本操作：求和
   3. 不同类型的输入，效率相同

2. 计算n!

   1. 输入规模：n
   2. 基本操作：相乘
   3. 不同类型输入，效率相同

3. n个数字中最大元素

   1. 输入规模：n
   2. 基本操作：比较
   3. 不同类型输入：效率相同

4. 欧几里得算法

   1. 输入规模：？？
   2. 基本操作：求余
   3. 效率相同

5. 埃拉托色尼筛选法

   1. 输入规模：数值n，首先会生成一个[2,…,n]的列表
   2. 基本操作：相乘
   3. 效率相同

6. 两个n位十进制数相乘的笔算算法

   1. 输入规模：十进制位数

   2. 基本操作：除以10

   3. 效率相同

   4. 代码

      def multipy(a,b):if a==0 or b==0:return 0s = 0 # 记录相乘结果l = 1 #记录a进行除法次数while a:p = a%10t = 1 #记录t进行除法次数while b:m = b%10s = s+p*m*(10**l)*(10**t)b = b/10t = t+1a = a/10l = l+1return s
      

      效率分析：

      输入规模：十进制位数

      基本操作：主要是两个数除以10，或者相加，或者相乘，根据运行时间，除法最耗时，故基本操作为除法。

      时间效率：一个数为n位十进制，则进行n次除以10，两个数则为n*n次除以10

2关于矩阵的算法

1. 矩阵相加

   基本操作：相加

   执行次数：矩阵为n阶方阵 - n*n次；矩阵元素n个 - n次

2. 矩阵相乘

   基本操作：相乘

   执行次数：矩阵为n阶方阵 - n*n次；矩阵元素n个 - n次

总结：矩阵操作次数主要依赖于元素个数。

3 查找键在列表中出现次数：

count(arr,target):
# 在arr中计算target的出现次数
# n为arr的长度
count = 0
for i=1,...,n:if arr[i] == target:count ++
return count

输入规模：数组元素个数n

基本操作：比较

不同类型的输入：效率相同

效率：比较n次

4 不同类型的输入

1. 选择手套：每次选一只手套，取出不放回，直至出现成对手套

   最好情况：选2只手套即匹配

   最差情况：3种颜色各一只，则第4只一定成对，故4只。

2. 丢失的袜子

   不懂

5 数学特性

1. 以下公式代表十进制正整数用二进制表示时的位数，二进制位数是指第一位不为0的情况
   b = ⌊ log ⁡ 2 n ⌋ + 1 b = \lfloor \log_2 n \rfloor + 1 b=⌊log2​n⌋+1
   3位二进制数代表范围为[4,7] (2^3-1​)，2位二进制数代表范围为[2,4]；

   b代表二进制位数，n表示十进制数
   2 b − 1 ≤ n ≤ 2 b − 1 ⌈ log ⁡ 2 ( n + 1 ) ⌉ ≤ b ≤ ⌊ log ⁡ 2 n ⌋ + 1 b = ⌊ log ⁡ 2 n ⌋ + 1 2^{b-1} \leq n \leq 2^b-1 \\ \lceil \log_2 (n+1) \rceil \leq b \leq \lfloor \log_2 n \rfloor +1 \\ b = \lfloor \log_2 n \rfloor +1 2b−1≤n≤2b−1⌈log2​(n+1)⌉≤b≤⌊log2​n⌋+1b=⌊log2​n⌋+1

2. 问题1已证明

3. 十进制位数
   1 0 b − 1 ≤ n ≤ 1 0 b − 1 ⌈ log ⁡ 10 ( n + 1 ) ⌉ ≤ b ≤ ⌊ log ⁡ 10 n ⌋ + 1 b = ⌊ log ⁡ 10 n ⌋ + 1 10^{b-1} \leq n \leq 10^b-1 \\ \lceil \log_{10} (n+1) \rceil \leq b \leq \lfloor \log_{10} n \rfloor +1 \\ b = \lfloor \log_{10} n \rfloor +1 10b−1≤n≤10b−1⌈log10​(n+1)⌉≤b≤⌊log10​n⌋+1b=⌊log10​n⌋+1

4. 原因：不知

6 不知，扩充什么？？

7 高斯消去法， 1 3 n 3 \frac{1}{3} n^3 31​n3次乘法运算

1. 8倍，$n=500,2n=1000$
2. 相同时间，新计算机求解方程个数为原来的10倍 n 3 ∗ 1000 = b 3 , b = 10 ∗ n n^3 * 1000 = b^3,b=10*n n3∗1000=b3,b=10∗n

8 new_n = 4*n:增长2次，增长2倍，增长4倍，增长16倍，增长64倍，增长2^n的3次方

综上，可见2^n级算法增长倍数为指数级，应避免对大规模输入用该类算法。

9 大致相同，精确来说是小；小；相同；相同；相同；小

10 总共麦粒为
2 0 + 2 1 + . . . + 2 64 = ( 2 64 − 1 ) ∗ 65 2^0 + 2^1 +...+2^{64} = (2^{64}-1)*65 20+21+...+264=(264−1)∗65
下一题
$$1+3+5+...+(1+2\ast 63)=64\ast 64$$
1小时9分钟以内

2.2 效率表示符号

$t(n)$表示算法运行时间，即基本操作执行次数；$g(n)$表示与操作次数相比较的函数

三种符号

增长次数以当前规模为基准，而不是之前的规模。

$O(g(n))$表示增长次数小于等于$g(n)$的函数集合，上界由$g(n)$常数倍决定

$\Omega (g(n))$表示增长次数大于等于$g(n)$的函数集合，上界由$g(n)$常数倍决定

$\Theta (g(n))$ 表示增长次数等于$g(n)$的函数集合，上、下界由$g(n)$常数倍决定

举个栗子：
g ( n ) = n 2 O ( n ) Ω ( n 3 ) Θ ( n 2 ) g(n) = n^2 \\ O(n) \\ \Omega (n^3) \\ \Theta (n^2) g(n)=n2O(n)Ω(n3)Θ(n2)

利用极限比较增长次数

基本效率类型

效率类型：常量、对数、线性、线性对数、平方、立方、指数、阶乘

Exercise 2.2

1 顺序查找效率类型

1. 最差情况：$\Theta (n)$

2. 最优情况：$\Theta (1)$

3. 平均情况：$O(n)$

2 T;T;F;T.

3 n 20 n^{20} n20；$n$； n 2 log ⁡ n n^2\log n n2logn； 3 n 3^n 3n；对数

4 不知

5 根据顺序编号为1、2、3、4、5、6、7，从低到高顺序为2-5-6-4-7-3-1

6

1. 证明

P ( n ) ≤ ( a k + a k − 1 + . . . + a 0 ) ∗ n k P(n) \leq (a_k+a_{k-1}+...+a_0)*n^k P(n)≤(ak​+ak−1​+...+a0​)∗nk

2. 证明

   $a=3$，规模为n时，执行次数为 3 n 3^n 3n；规模为2n时，执行次数为 3 2 n 3^{2n} 32n；增长倍数为 3 n 3^n 3n

   $a=2$，同理分析得到增长倍数为 2 n 2^ n 2n；

9 预排序数组元素是否唯一

1. 预排序效率$\Theta (n\log n)$,判断元素唯一效率为$O(n)$，整个效率$O(n\log n)$；
2. 预排序使用n个额外空间，判断元素唯一不需要额外空间，整个空间效率为$\Theta (n)$；

10 范围 = 最大元素-最小元素，计算范围的效率

1. 未排序：求最大、最小元素效率为$\Theta (n)$，
2. 排序数组：排序算法效率，求最大、最小元素效率为$\Theta (1)$，总的效率为排序算法效率
3. 排序单链表：从表头遍历，效率为$\Theta (n)$
4. 二叉查找树：与二叉查找树高度相关，查找最小元素效率为$\Theta (\lfloor \log n\rfloor +1)$，最大元素效率亦是这个，故总效率为$\Theta (\lfloor \log n\rfloor +1)$

11 n个硬币和天平，其中一枚为假币，确定假币比真币轻还是重。

若n为偶数，将剩余硬币均分为2份记为a,b，每份硬币数为m；

1. 若m为偶数，再将a和b分别均分为两份，记为a1,a2,b1,b2；

   若a1 =a2，说明a均为真币且得到真币重量，b中含有假币，则衡量a1和b1，a1和b2，从而得到结果；

   若b1 = b2，同上述分析。

2. 若m为奇数，则各去掉一枚硬币记为c1,c2，将a,b中剩余硬币分别均分为两份，记为a1,a2,b1,b2;

   若a1==a2 & b1 == b2，则说明均为真币，则将替换其中一枚真币依次衡量c1、c2

   否则，按照m为偶数的情况分辨；

若n为奇数，去掉一枚硬币c1，按照上述过程可得到结果。

12 墙上的门

该题不知门在哪，也不知道需走多少步；假设门在某个方向n步处，n不知大小；只需经过门即可，无需站在门前。

方法一：

每趟比前一趟多走一步

第1躺：向右走1步，未经过门，返回原点；向左走1步，未经过门，返回原点；

第2躺：向右走2步，未经过门，返回原点；向左走2步，未经过门，返回原点；

假设第k躺经过门，则说明$k==n$

第k-1躺：向右走k-1步，未经过门，返回原点；向左走k-1步，未经过门，返回原点；

第k躺：向右走k步，未经过门，返回原点；向左走k步，经过门；(最差情况)

总步数为
4 ∑ i = 1 k − 1 i + 3 ∗ k = 2 k 2 + k > n 2 k 2 + k ∉ O ( n ) 4\sum_{i=1}^{k-1} i + 3*k = 2k^2+k > n \\ 2k^2 + k \notin O(n) 4i=1∑k−1​i+3∗k=2k2+k>n2k2+k∈/​O(n)
方法二：

每趟比前一躺多走一倍

第1躺：向右走1步，未经过门，返回原点；向左走1步，未经过门，返回原点；

第2躺：向右走2步，未经过门，返回原点；向左走2步，未经过门，返回原点；

第3躺：向右走4步，未经过门，返回原点；向左走4步，未经过门，返回原点；

假设第k躺经过门，则说明 2 k − 1 ≤ n 2^{k-1} \leq n 2k−1≤n

第k-1躺：向右走 2 k − 2 2^{k-2} 2k−2步，未经过门，返回原点；向左走 2 k − 2 2^{k-2} 2k−2 步，未经过门，返回原点；

第k躺：向右走 2 k − 1 2^{k-1} 2k−1步，未经过门，返回原点；向左走 2 k − 1 2^{k-1} 2k−1 步，经过门；(最差情况)

则总步数为：
4 ∑ i = 1 k − 1 2 i − 1 + 3 ∗ 2 k − 1 = 12 ∗ 2 k − 1 − 4 ≤ 12 n 12 ∗ 2 k − 1 − 4 ∈ O ( n ) 4 \sum_{i=1}^{k-1} 2^{i-1} + 3*2^{k-1} = 12*2^{k-1}-4 \leq 12n\\ 12*2^{k-1}-4 \in O(n) 4i=1∑k−1​2i−1+3∗2k−1=12∗2k−1−4≤12n12∗2k−1−4∈O(n)

2.3 非递归算法的数学分析

n为输入规模，运算执行次数记为$C(n)$

非递归算法的通用框架：

• 确定输入规模为哪个参数
• 确定基本操作是哪个
• 检查基本操作的执行次数是否只依赖于输入规模，还是依赖于输入类型
• 建立执行次数的求和表达式
• 确定其增长次数：三个符号表示

1. 例子一：求n个元素的最大元素

   max_element(arr[0,...,n-1]):
   max_val = arr[0]
   for i = 1,...,n-1if arr[i] > max_val:max_val = arr[i]
   return max_val
   

   输入规模：元素个数n

   基本操作：

   循环内有两个操作：比较和赋值；其中每次循环均进行比较，但赋值不一定；故基本操作为比较

   不同输入类型：比较次数是相同的

   求和表达式
   ∑ i = 1 n − 1 1 = n − 1 ∈ Θ ( n ) \sum_{i=1}^{n-1} 1 = n-1 \in \Theta(n) i=1∑n−1​1=n−1∈Θ(n)

2. 判断数组元素的唯一性

   方法一：每个元素与其他元素比较；

   方法二：利用辅助空间统计每个元素的频次；

   方法三：对元素排序，然后比较前一个和后一个

   方法一
   unique_element(arr[0,...,n-1]):
   for i=0,...,n-2:for j=i+1,...,n-1:if arr[i]==arr[j]:return False
   return True
   

   输入规模：元素个数n

   基本操作：比较

   比较次数还依赖于相同元素

   最差效率：最后两个元素相同或数组元素唯一时，比较次数最多
   ∑ i = 0 n − 2 ∑ j = i + 1 n − 1 1 = n ( n − 1 ) 2 ∈ Θ ( n 2 ) \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \frac{n(n-1)}{2} \in \Theta(n^2) i=0∑n−2​j=i+1∑n−1​1=2n(n−1)​∈Θ(n2)

3. 两个n阶方阵A,B相乘，C=AB，C中任一元素C[i,j] = A[i]*B[j]

   matrix_multiply(A[n,n],B[n,n]):
   #结果矩阵C也是n阶方阵
   for i=0,...,n-1for j=0,...,n-1C[i,j] = 0for k=0,..,n-1C[i,j] += A[i,k]*B[k,j]
   

   输入规模：矩阵阶数n

   基本操作：加法、乘法均可

   乘法次数只依赖于阶数

   效率
   n 3 ∈ Θ ( n 3 ) n^3 \in \Theta(n^3) n3∈Θ(n3)

4. 求十进制数的二进制位数

   binary(n):
   count = 1
   while n > 1:count ++n = n//2
   

   输入规模：十进制数

   基本操作：比较n>1

   比较次数：每比较一次，则n减小一半
   ⌊ log ⁡ 2 n ⌋ + 1 \lfloor \log_2 n \rfloor + 1 ⌊log2​n⌋+1

Exercise 2.3

1、2、3略过

4

1. 求n个数的平方和
2. 基本操作：加法、乘法
3. 乘法次数n次
4. 只依赖于元素个数n，效率类型$\Theta (n)$
5. 无法改进算法

5

1. 求数组范围=最大元素-最小元素
2. 基本操作：比较
3. 比较次数n-1次
4. 比较次数只依赖于数组元素个数，效率类型$\Theta (n)$
5. 无法改进算法，对数组排序，排序算法效率最好为$O(n\log n)$，不如$O(n)$

6

1. 判断n阶矩阵是否为对称矩阵

2. 基本操作：比较

3. 最多比较次数：对称矩阵或最后一对元素不相等
   ∑ i = 0 n − 2 ∑ j = i + 1 n − 1 1 = ( n − 1 ) + ( n − 2 ) + . . . + 1 = n ( n − 1 ) 2 \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \\ (n-1) + (n-2)+...+1 = \frac{n(n-1)}{2} i=0∑n−2​j=i+1∑n−1​1=(n−1)+(n−2)+...+1=2n(n−1)​

4. 比较次数依赖于不对称元素，效率类型为 Θ ( n 2 ) \Theta (n^2) Θ(n2)

5. 对称矩阵特性：转置矩阵与原矩阵相等，但需要比较 n 2 n^2 n2次

   无法改进算法

7 改进矩阵乘法：减少加法次数，使得加法运算时间减少，但是乘法次数没变，时间改变只是常数倍

8 带锁的门：所有门开关总次数

方法一：

第1次，改变1,2,…,n

第2次，改变2,4,6,…

第3次，改变3,6,9,…

测试用例：

功能测试：n=10,n=1

边界测试：n=0，n= -10

count(n):
# n: n个门
if n <= 0:return 0
c = 0 #记录开关总次数
for i=1,...,n #第i次for j =i,...,n #j号门是否开关if j%i == 0c ++

取余计算次数n(n-1)/2，效率为 Θ ( n 2 ) \Theta (n^2) Θ(n2)

方法二：

第 i 次，改变 i,2 i ,…, i * i , (i+1)i ,…p * i # 改变了p个门

需判断$p\ast i\le n$是否成立，其中$p=1,2,...$

count(n):
c = n #第1次，改变n个门
for i= 2,...,np = 1while p*i<=n:p += 1c = c+p-1

方法三：根据方法二改进

当$i>n//2$时，只有$1\ast i$号门改变状态，因为$2\ast i>n$，故改变了一个门

当$i\le n//2$时，解析如下：

第 i 次，当$i\ast i>n$时，符合$p\ast i\le n$的最大p是多少，其中$p=i-1,i-2,...,1$

m表示 i-1 次 最大p值，满足$ m * (i -1) \leq n$

则判断 $m\ast i\le n$是否成立，不成立，则m = m -1

一般 i 越大，相应p越小，故不存在p>m

count(n):
c = n + n - n//2
pre_p = n
for i = 2,...,n//2if i*i <= n:p = iwhile (p+1)*i <= n:p += 1else:p = pre_pwhile p*i > n:p = p - 1pre_p = pc += p 

9 可以发现1+n = 2 + (n-1) = 3 + (n-2)，共 n/2对 和为n+1的数，故求和公式为n(n+1)/2

10 n阶表格

n = 10时，

value = 10的有10个，value=9和11的分别有9个，value=3和17的分别有3个；总的来说，value=20的有1+2+3+…+9 = 45

value = n的有n个，value = n-1和n+1的分别有n-1个，则value=2n的有1+2+…+(n-1)=n(n-1)/2

sum(n):
s = n*n*n

11 该算法是将矩阵化为上三角矩阵，且第一个非0值为1，用于求解多元方程组

1. 以第 i 行为基准，需改变 n-i+1 行，每行需调整元素个数为n-i
   ∑ i = 0 n − 2 ( n − i ) 2 − ( n − i ) = n 2 + ( n − 1 ) 2 + . . . + 4 + n + n − 1 + . . . + 2 = n ( n + 1 ) ( 2 n + 1 ) − 1 6 + ( n + 2 ) ( n − 1 ) 2 ∈ Θ ( n 3 ) \sum_{i=0}^{n-2} (n-i)^2 - (n-i) = \\ n^2+(n-1)^2+...+4 +\\ n + n-1 +...+2 \\ = \frac{n(n+1)(2n+1)-1}{6} + \frac{(n+2)(n-1)}{2} \in \Theta(n^3) i=0∑n−2​(n−i)2−(n−i)=n2+(n−1)2+...+4+n+n−1+...+2=6n(n+1)(2n+1)−1​+2(n+2)(n−1)​∈Θ(n3)

2. 缺陷

   1. A[i,i]为0，可能发生除0错误

12 冯诺依曼邻居问题

F(n)表示第n次的方格数

根据归纳总结，得到F(n) = F(n-1)+2n + 2(n-2)

13 页码不都是十进制数组吗？

2.4 递归算法的数学分析

待完善

递归算法的通用框架

• 确定输入规模是哪个参数
• 确定基本操作
• 基本操作是否只依赖于输入规模
• 基本操作执行次数：建立递推关系和初始条件
• 解出递推式，或者确定增长次数

例子：

例一：计算阶乘n!

F(n):
if n == 0:return 1
else return F(n-1)*n

1. 输入规模：数值n

2. 基本操作：乘法

3. 乘法次数：

   递推式

   求F(n)的乘法次数记为M(n)，F(n) = F(n-1)*n，则M(n) = M(n-1)+1;

   初始条件

   停止递归调用条件：if n==0: return 1，未进行乘法运算，故M(0) = 0；

4. 总结

   阶乘函数递推关系：

$$\begin{gathered} F(n)=F(n-1)\ast n \\ F(0)=1 \end{gathered}$$
​ 乘法执行次数递推关系：
$$\begin{gathered} M(n)=M(n-1)+1 \\ M(0)=0 \end{gathered}$$

5. 如何解该递推关系？反向替换法：

   M(n) = M(n-1)+1 = M(n-2)+2 = …

   根据该过程寻找规律，求得递推关系。

例二：汉诺塔

将n个盘子从1移到3

将n-1个盘子从1移到2；将第n个盘子从1移到3；将n-1个盘子从2移到3。

输入规模：n个盘子

基本操作：移动

移动次数M(n)：只依赖于n
M ( n ) = M ( n − 1 ) + 1 + M ( n − 1 ) = 2 M ( n − 1 ) + 1 M ( 1 ) = 1 M ( n ) = 2 n − 1 M(n) = M(n-1)+1+M(n-1) = 2M(n-1)+1 \\ M(1) = 1 \\ M(n) = 2^n-1 M(n)=M(n−1)+1+M(n−1)=2M(n−1)+1M(1)=1M(n)=2n−1

---

例三：十进制数的二进制位数

bin_rec(n):
if n==1 : return 1
else: return bin_rec(n//2)+1

假设n与 2 k 2^k 2k具有相同增长次数
M ( 2 k ) = M ( 2 k − 1 ) + 1 M ( 1 ) = 0 M ( 2 k ) = k M ( n ) = log ⁡ 2 n M(2^k) = M(2^{k-1})+1 \\ M(1) = 0 \\ M(2^k) = k \\ M(n) = \log_2 n M(2k)=M(2k−1)+1M(1)=0M(2k)=kM(n)=log2​n

---

Exercise 2.4

1 解递推关系-反向替换法

1. x(n) = 5(n-1)

2. x(n) = 4 * 3^(n-1)
   x ( n ) = 3 x ( n − 1 ) = 3 2 x ( n − 2 ) = 3 3 x ( n − 3 ) = . . . = 3 i x ( n − i ) x ( 1 ) = 4 , n − i = 1 , i = n − 1 x ( n ) = 3 n − 1 x ( 1 ) = 4 ∗ 3 n − 1 x(n) = 3x(n-1) = 3^2x(n-2) = 3^3x(n-3) = ... = 3^ix(n-i)\\ x(1) = 4,n-i=1,i=n-1\\ x(n) = 3^{n-1}x(1) = 4*3^{n-1} x(n)=3x(n−1)=32x(n−2)=33x(n−3)=...=3ix(n−i)x(1)=4,n−i=1,i=n−1x(n)=3n−1x(1)=4∗3n−1

3. x(n) = n(n+1)/2

4. x(n) = 2n-1

5. x(n) = log ⁡ 3 n \log_3 n log3​n + 1

2 计算n!的递归算法F(n)，其递归调用次数的递推关系并求解

计算F(n)的递归调用次数为A(n),F(n) = F(n-1)*n

A(n) = A(n-1)+1

A(0) = 1

求得A(n) = 1+n

3 立方和

1. 输入规模为n，基本操作为乘法或加法，且只依赖于n；记乘法操作次数为A(n)
   $$\begin{gathered} A(n)=A(n-1)+1 \\ A(1)=0 \\ A(n)=n-1 \end{gathered}$$

2. 递归算法：需要额外的空间和时间使用递归栈，保存返回信息；

   非递归算法：乘法操作次数为n-1，不用额外时间和空间维护递归栈；

   相比较而言，非递归算法时间效率和空间效率更高。

4 递归算法

1. 函数的递推关系
   Q ( n ) = Q ( n − 1 ) + 2 ∗ n − 1 Q ( 1 ) = 1 Q ( n ) = n 2 Q(n) = Q(n-1)+2*n-1 \\ Q(1) = 1 \\ Q(n) = n^2 Q(n)=Q(n−1)+2∗n−1Q(1)=1Q(n)=n2
   计算平方

2. 乘法运算次数递推关系，计算Q(n)需M(n)次乘法
   $$\begin{gathered} M(n)=M(n-1)+1 \\ M(1)=0 \\ M(n)=n-1 \end{gathered}$$

3. 加减运算次数递推关系，计算Q(n)需A(n)次乘法
   $$\begin{gathered} A(n)=A(n)+1 \\ A(1)=0 \\ A(n)=n-1 \end{gathered}$$

5

8 2 n = 2 n − 1 + 2 n − 1 2^n = 2^{n-1} + 2^{n-1} 2n=2n−1+2n−1，分析同汉诺塔

1. F ( n ) = 2 n F(n) = 2^n F(n)=2n，F(n) = F(n-1) + F(n-1)

f(n):
if n==0: return 1
else: return f(n-1)+f(n-1)

2. 加法运算次数记为A(n)
   A ( n ) = A ( n − 1 ) + A ( n − 1 ) + 1 = 2 A ( n − 1 ) + 1 A ( 0 ) = 0 A ( n ) = 2 n − 1 A(n) = A(n-1) + A(n-1) + 1 =2A(n-1)+1 \\ A(0) = 0 \\ A(n) = 2^n - 1 A(n)=A(n−1)+A(n−1)+1=2A(n−1)+1A(0)=0A(n)=2n−1

3. 递归调用树：计算F(1)时还调用F(0)，故可以修改递归终止条件，减少调用次数

   树高度为n+1，层数为n层，则调用次数即树的节点数为
   ∑ i = 0 n 2 i = 2 n + 1 − 1 \sum_{i=0}^n 2^i = 2^{n+1}-1 i=0∑n​2i=2n+1−1

4. 需维护递归栈

9 pass

1. 求数组A[0,…,n-1]的最小元素

   R(n)表示n个元素的最小值，R(n-1)表示n-1个元素的最小值

   if A[n-1]

   else R(n) = R(n-1)

   求R(n)时需比较A[n-1]与R(n-1)

2. 输入规模为n，基本操作为比较，比较次数只依赖于n，比较次数记为C(n)
   $$\begin{gathered} C(n)=C(n-1)+1 \\ C(1)=0 \\ C(n)=n-1 \end{gathered}$$

10 最坏情况下，最后一个元素为0，或该图为完全图

11 计算n阶方阵行列式，记为D(n)，计算D(n)需计算n个D(n-1)

1. M(n)表示计算D(n)的乘法运算次数，
   $$\begin{gathered} M(n)=n\ast M(n-1)+n \\ M(1)=0 \\ M(n)=n!+n!/2+n!/3!+n!/4!+...+n(n-1)(n-2)+n(n-1)+n \end{gathered}$$

2. $\Omega (n!)$

12 n阶冯诺依曼邻居：递归算法

def neighbor(n):
if n==1: return n
else: return neighbor(n-1)+4*(n-1)

13 烤汉堡：

1. T(n)表示烤n个汉堡所需时间
   $$\begin{gathered} T(n)=T(n-2)+2,n>2 \\ T(n)=2,n\le 2 \\ ifn\%2==0,T(n)=n \\ elseT(n)=n+1 \end{gathered}$$

2. 3个汉堡分别为1、2、3，首先1,2一起烤一面，然后2，3一起烤一面，最后1，3一起烤，共用3分钟

3. n个汉堡，共2n个面，则第一次烤1,2，第二次烤2,3，第三次烤3,4，依次下去，最后烤n,1

   time(n):
   # n：汉堡的面数，n/2个汉堡
   if n == 2:return 1
   else : return time(n-2)+1
   

14 名人问题方法

2.5 计算第n个斐波那契数

斐波那契递推关系和初始条件
$$\begin{gathered} F(n)=F(n-1)+F(n-2) \\ F(0)=0,F(1)=1 \end{gathered}$$
如何计算第n个斐波那契数？

方法一：递归算法

Fibonacci(n):
if n < 2:return n
else: return Fibonacci(n-1)+Fibonacci(n-2)

输入规模为数值n，基本操作为加法，只依赖于n

记计算F(n)需A(n)次加法，计算F(0)和F(1)不需要加法，直接返回数值，故得到加法运算次数的递推关系以及初始条件：
$$\begin{gathered} A(n)=A(n-1)+A(n-2)+1 \\ A(0)=0,A(1)=0 \end{gathered}$$
如何求解该递推公式后面再说。

方法二：循环算法

Fibonacci(n):
# F: 一个数组，用以记录斐波那契数列F(0),F(1),...,F(n)，长度为n+1
F(0) = 0,F(1) = 1
for i=2,...,n:F(i) = F(i-1)+F(i-2)

可以推出加法运算次数为n-1，时间效率为$O(n)$

该算法可改进：若只求第n个斐波那契数，则可不用数组保存每个结果，只用两个变量保存

方法三：数学公式

斐波那契数递推关系为F(n) = F(n-1)+F(n-2)，该式为齐次二阶线性递推式F(n)-F(n-1)-F(n-2)，可用数学方法求解，最后的结果
F ( n ) = C ϕ n 取整为最近的整数,C为常数 F(n) = C \phi^n \text{取整为最近的整数,C为常数} F(n)=Cϕn取整为最近的整数,C为常数
F(n)呈指数增长。

同理可得到方法一中A(n)亦是呈指数增长，效率较差；同时分析递归调用树发现，递归算法重复计算多次。

方法四：矩阵
[ F ( n − 1 ) F ( n ) F ( n ) F ( n + 1 ) ] = [ 0 1 1 1 ] n , n ≥ 1 \begin{bmatrix} F(n-1) & F(n) \\ F(n) & F(n+1) \\ \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix}^n,n \geq 1 [F(n−1)F(n)​F(n)F(n+1)​]=[01​11​]n,n≥1
上述等式是计算矩阵乘方的高效方法。

Exercise 2.5

1 研究斐波那契(以后)

2 兔子问题

分析问题：假设3月出生一对新兔子，记为new，则new在4月修养，5月生兔子，并且之后每个月均生兔子。从而可得知当月出生新兔子数为上上月兔子数目，而老兔子则为上个月兔子数。

记F(n)表示第n个月的兔子数，得到F(n) = F(n-1) + F(n-2)，且F(1) = 1,F(2) = 1，第一月只有新出生的一对兔子。F(12) = 144

3 爬梯子：爬n格梯子共F(n)种方法，第一步有两种选择：

第一步爬1格，则剩余n-1格有F(n-1)种方法；

第一步爬2格，则剩余n-2格有F(n-2)种方法。

故F(n) = F(n-1)+F(n-2)

4 记A(n)表示前n项中偶数个数，根据斐波那契数列的偶奇性：

偶奇奇偶奇奇偶奇奇偶

第1,4,7,10为偶数，A(1)=1,A(4)=2,A(7)=3,A(10)=4,A(n) = A(n-3)+1,解得A(n) = (n+2)/3(向下取整)

5 验证数学方法的结果符合递归式

6

7 斐波那契

1. C(n)是F(n)调用F(1)的次数，则
   $$\begin{gathered} C(n)=C(n-1)+C(n-2) \\ C(0)=0,C(1)=1 \end{gathered}$$
   上式类似于斐波那契递推公式，则C(n) = F(n)

2. Z(n)是F(n)调用F(0)的次数，则
   $$\begin{gathered} Z(n)=Z(n-1)+Z(n-2) \\ Z(0)=1,Z(1)=0,Z(2)=1 \end{gathered}$$
   可看出，Z(n)序列较F(n)序列提前一位，即F(n) = Z(n+1)，Z(n) = F(n-1)

8 改进循环版斐波那契

Fibonacci(n):
# F: 一个数组，用以记录斐波那契数列F(0),F(1),...,F(n)，长度为n+1
f1 = 0,f2 = 1
for i=2,...,n:f = f1 + f2f1 = f2f2 = f
return f

9 证明矩阵版斐波那契，未做

10

11

12

---

2.6 算法的经验分析（重看）

思想：程序代码实现算法，设计输入样本并运行代码，对基本操作计数或计算运行时间度量效率。

设计样本需考虑：

• 样本的规模

• 样本的取值范围

• 同一规模不同类型的实例

Exercise 2.6

1 计数器，插入排序

不正确

基本操作为while处比较，当A[j]

2

3

4 经验分析表格

规模翻番，增长倍数大约为2倍，$\Theta (n)$

5 对数散点图变为线性散点图，纵坐标设置为指数函数。

6 通过题5方法即可分辨

7 经验分析欧几里得算法

8 欧几里得

9 埃拉托色尼筛选法

10 3种求最大公约数算法，经验分析效率类型

---

2.7 算法可视化

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！