《算法导论》练习与思考题第1-3章 (python版)

2022/2/7 22:44:51

编程Tag： python n2 lim theta 导论 limits cfrac 思考题 lg

本文主要是介绍《算法导论》练习与思考题第1-3章 (python版)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

第一章算法在计算中的作用
- 练习
- - 1.1 算法
  - - 1.1-1
    - 1.1-2
    - 1.1-3
    - 1.1-4
    - 1.1-5
  - 1.2 作为一种技术的算法
  - - 1.2-1
    - 1.2-2
    - 1.2-3
- 思考题
- - 1-1 运行时间的比较
第二章算法基础
- 练习
- - 2.1 插入排序
  - - 2.1-1
    - 2.1-2
    - 2.1-3
    - 2.1-4
  - 2.2 分析算法
  - - 2.2-1
    - 2.2-2
    - 2.2-3
    - 2.2-4
  - 2.3 设计算法
  - - 2.3-1
    - 2.3-2
    - 2.3-3
    - 2.3-4
    - 2.3-5
    - 2.3-6
    - 2.3-7
- 思考题
- - 2-1
  - 2-2
  - 2-3
  - 2-4
第三章函数的增长
- 练习
- - 3.1 渐进记号
  - - 3.1-1
    - 3.1-2
    - 3.1-3
    - 3.1-4
    - 3.1-5
    - 3.1-6
    - 3.1-7
    - 3.1-8
  - 3.2 标准记号与常用函数
  - - 3.2-1
    - 3.2-2
    - 3.2-3
    - 3.2-6
    - 3.2-7
    - 3.2-8
- 思考题
- - 3-1 多项式的渐进行为
  - 3-2 相对渐进增长
  - 3-3 根据渐进增长率排序
  - 3-4 渐进记号的性质
  - 3-5 O O O与 Ω \Omega Ω的一些变形
  - 3-6 多重函数

第一章算法在计算中的作用

练习

1.1 算法

1.1-1

排序的例子：一个医生要接诊的病人会按照挂号时间排序。

1.1-2

热效率，衡量发动机等热能转换装置能量利用的效率

1.1-3

数据结构：链表
优势：顺序访问效率高
局限：随机访问效率低

1.1-4

相似之处：都是点与点之间的移动；都是求最短的移动路线
不同：最短路径问题有明确的解法，而旅行商问题是NP完全问题，没有有效算法。

1.1-5

必须是最佳解的例子：一个数学定理的证明
可以使用近似解的例子：手术方案的建立

1.2 作为一种技术的算法

1.2-1

应用层的例子：一个压缩软件，在应用层就会使用压缩算法。
算法的功能：应该将输入的数据无损地转换为更小的数据

1.2-2

当n的取值为2-6时插入排序优于归并排序

1.2-3

n最小为15时在同一台机器上 100 n 2 100n^2 100n2的算法优于 2 n 2^n 2n的算法

思考题

1-1 运行时间的比较

思路：先将给定时间转换为毫秒，然后用 f ( n ) f(n) f(n)的逆函数求出对应的n值

	1秒钟（1000ms）	1分钟（60000ms）	1小时（3600000ms）	1天(86400000ms)	1月(2592000000ms)	1年(31536000000ms)	1世纪(3153600000000ms)
lg ⁡ n \lg{n} lgn	1 0 1000 10^{1000} 101000	1 0 60000 10^{60000} 1060000	1 0 3600000 10^{3600000} 103600000	1 0 86400000 10^{86400000} 1086400000	1 0 2592000000 10^{2592000000} 102592000000	1 0 31536000000 10^{31536000000} 1031536000000	1 0 3153600000000 10^{3153600000000} 103153600000000
n \sqrt{n} n	100 0 2 1000^{2} 10002	6000 0 2 60000^{2} 600002	360000 0 2 3600000^{2} 36000002	8640000 0 2 86400000^{2} 864000002	259200000 0 2 2592000000^{2} 25920000002	3153600000 0 2 31536000000^{2} 315360000002	315360000000 0 2 3153600000000^{2} 31536000000002
n n n	1000 1000 1000	60000 60000 60000	3600000 3600000 3600000	86400000 86400000 86400000	2592000000 2592000000 2592000000	31536000000 31536000000 31536000000	3153600000000 3153600000000 3153600000000
n 2 n^2 n2	31 31 31	244 244 244	1897 1897 1897	9295 9295 9295	50911 50911 50911	177583 177583 177583	1 , 775 , 837 1,775,837 1,775,837
n 3 n^3 n3	10 10 10	39 39 39	153 153 153	442 442 442	1373 1373 1373	3159 3159 3159	14 , 664 14,664 14,664
2 n 2^n 2n	9 9 9	15 15 15	21 21 21	26 26 26	31 31 31	34 34 34	41 41 41
n ! n! n!	6 6 6	8 8 8	9 9 9	11 11 11	12 12 12	13 13 13	15 15 15

第二章算法基础

练习

2.1 插入排序

2.1-1

用画图绘制的插入排序过程

2.1-2

def insertionSortNonAscending(A):
	for j in range(1,len(A)):
		key = A[j]
		i = j - 1
		while i >=0 and A[i] < key:
			A[i+1] = A[i]
			i -= 1
		A[i+1] = key

2.1-3

def linearFind(A, v):
	for j in range(len(A)):
		if A[j] == v:
			return j
	return None

循环不变式：已经搜索的子数组A[0…j-1]中不存在v

初始化：迭代开始之前(当0=1时)子数组A[0…j-1]中一个元素也没有，循环不变式成立
保持：如果A[j]等于v，循环终止。反之A[0…j]中不存在v，循环不变式成立
终止：当j等于A.length时循环终止，此时已经搜索的子数组A[0…j-1]即原数组A[0…n]。而如果在循环中A[j]等于v时循环终止，此时前一次迭代已经搜索的子数组A[0…j-1]中没有v，循环不变式成立

2.1-4

二进制加法问题：
输入：n个数的两个序列， A = < a 1 , a 2 , ⋯ , a n > A=<a_1,a_2,\cdots,a_n> A=<a1,a2,⋯,an>和 B = < b 1 , b 2 , ⋯ , b n > B=<b_1,b_2,\cdots,b_n> B=<b1,b2,⋯,bn>,A和B表示两个二进制数每个数位的依次排列
输出： n+1个数的序列 C = < c 1 , c 2 , ⋯ , c n + 1 > C=<c_1,c_2,\cdots,c_{n+1}> C=<c1,c2,⋯,cn+1>，C为二进制数A与B的和

def binarySum(A, B):
	carry = 0
	C = []
	for i in range(len(A)-1,-1,-1):
		sum = A[i] + B[i] + carry
		C.insert(0, sum % 2)
		carry = sum // 2 
	C.insert(0, carry)
	return C

2.2 分析算法

2.2-1

Θ ( n 3 ) \Theta(n^3) Θ(n3)

2.2-2

def selectionSort(A):
	for i in range(len(A)-1):
		min = i
		for j in range(i+1,len(A)):
			if A[min] > A[j]:
				min = j
		A[min],A[i]=A[i],A[min]

循环不变式：A[0…i-1]为已排序好的序列
考虑最后一次循环，此时i=n-1，A[1…n-2]为已排序的序列且都小于A[n-1]和A[n]，当将A[n]和A[n-1]中最小的放到A[n-1]处时，A[n]处的数据也回到了正确的位置，所以只循环n-1次就足够。
最好情况和最坏情况都是 Θ ( n 2 ) \Theta(n^2) Θ(n2)的运行时间

2.2-3

平均情况和最坏情况运行时间均为 Θ ( n ) \Theta(n) Θ(n)。
证明：
平均情况时，假设v有n+1种情况，v等可能的出现在A中任一位置或者不出现。
所以平均的运行时间为 1 + 2 + ⋯ + n n + 1 = 1 2 n ( n + 1 ) n + 1 = 1 2 n = Θ ( n ) \cfrac{1+2+\cdots+n}{n+1}=\cfrac{\frac{1}{2}n(n+1)}{n+1}=\frac{1}{2}n=\Theta(n) n+11+2+⋯+n=n+121n(n+1)=21n=Θ(n)
最坏情况时不出现，总共循环比较n次，运行时间为 Θ ( n ) \Theta(n) Θ(n)。

2.2-4

？？？不太确定题的意思
大概是保证最好情况时循环能够直接结束程序给出答案吧。

2.3 设计算法

2.3-1

用画图绘制的归并排序过程

2.3-2

def merge(arr, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    L = arr[p:q + 1]
    R = arr[q + 1:r + 1]
    i = j = 0
    k = p
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    while i < n1:
        arr[k] = L[i]
        k += 1
        i += 1
    while j < n2:
        arr[k] = R[j]
        k += 1
        j += 1

2.3-3

首先：当k=1时 n = 2 k = 2 n=2^k=2 n=2k=2， T ( n ) = T ( 2 ) = 2 , n lg ⁡ n = 2 T(n)=T(2)=2,n\lg n=2 T(n)=T(2)=2,nlgn=2，所以 T ( n ) = n lg ⁡ n T(n)=n\lg n T(n)=nlgn
假设：k=m时等式成立， n = 2 m , T ( n ) = n lg ⁡ n = m 2 m n=2^m,T(n)=n\lg n=m2^m n=2m,T(n)=nlgn=m2m。因此k=m+1时将 n = 2 m + 1 n=2^{m+1} n=2m+1带入 T ( n ) = 2 T ( n 2 ) + n T(n)=2T(\cfrac{n}{2})+n T(n)=2T(2n)+n中，得 T ( n ) = 2 T ( 2 m ) + 2 m + 1 = m 2 m + 1 + 2 m + 1 = ( m + 1 ) 2 m + 1 T(n)=2T(2^m)+2^{m+1}=m2^{m+1}+2^{m+1}=(m+1)2^{m+1} T(n)=2T(2m)+2m+1=m2m+1+2m+1=(m+1)2m+1，而 n lg ⁡ n = 2 m + 1 lg ⁡ ( 2 m + 1 ) = ( m + 1 ) 2 m + 1 n\lg n= 2^{m+1}\lg(2^{m+1})=(m+1)2^{m+1} nlgn=2m+1lg(2m+1)=(m+1)2m+1,所以 T ( n ) = n lg ⁡ n T(n)=n\lg n T(n)=nlgn成立
综上所述，当n刚好是2的幂时，本题递归式的解为 T ( n ) = n lg ⁡ n T(n)=n\lg n T(n)=nlgn

2.3-4

T ( n ) = { Θ ( 1 ) , n = 1 T ( n − 1 ) + Θ ( n ) , n > 1 T(n)= \begin{cases} \Theta(1) ,&n=1\\ T(n-1) +\Theta(n),&n>1 \end{cases} T(n)={Θ(1),T(n−1)+Θ(n),n=1n>1

2.3-5

def binaryFind(A, v, p, q):
    if p <= q:
        r = (p + q) // 2
        if A[r] == v:
            return r
        elif A[r] < v:
            return binaryFind(A, v, r + 1, q)
        else:
            return binaryFind(A, v, p, r - 1)
    else:
        return None

最坏情况下，有如下递归式：
T ( n ) = { Θ ( 1 ) , n = 1 T ( n 2 ) + Θ ( 1 ) , n > 1 T(n)= \begin{cases} \Theta(1) ,&n=1\\ T(\cfrac{n}{2}) +\Theta(1),&n>1 \end{cases} T(n)=⎩⎨⎧Θ(1),T(2n)+Θ(1),n=1n>1
显然有：
lg ⁡ n { T ( n ) − T ( n 2 ) = Θ ( 1 ) T ( n 2 ) − T ( n 2 2 ) = Θ ( 1 ) T ( n 2 2 ) − T ( n 2 3 ) = Θ ( 1 ) ⋯ ⋯ T ( 2 ) − T ( 1 ) = Θ ( 1 ) \lg n \begin{cases} T(n)-T(\cfrac{n}{2})=\Theta(1)\\ T(\cfrac{n}{2})-T(\cfrac{n}{2^2})=\Theta(1)\\ T(\cfrac{n}{2^2})-T(\cfrac{n}{2^3})=\Theta(1)\\ \cdots\cdots\\ T(2)-T(1)=\Theta(1) \end{cases} lgn⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧T(n)−T(2n)=Θ(1)T(2n)−T(22n)=Θ(1)T(22n)−T(23n)=Θ(1)⋯⋯T(2)−T(1)=Θ(1)
所以最坏情况的运行时间为 Θ ( lg ⁡ n ) \Theta(\lg n) Θ(lgn)

2.3-6

不能，2.1节中INSERTION-SORT的while循环同时起到两个作用：找到已排序的n个数中要插入的位置和将该位置之后的元素向后移动一位，运行时间是 Θ ( n ) \Theta(n) Θ(n)。最坏情况时，找到位置的需求可以使用二分查找来降低运行时间为 Θ ( lg ⁡ n ) \Theta(\lg n) Θ(lgn)，但移动元素的运行时间还是 Θ ( n ) \Theta(n) Θ(n)，所以while循环的运行时间无法通过使用二分查找降低至 Θ ( lg ⁡ n ) \Theta(\lg n) Θ(lgn)，所以最坏情况运行时间也无法使用二分查找改进到 Θ ( n lg ⁡ n ) \Theta(n\lg n) Θ(nlgn)的运行时间。

2.3-7

使用归并排序将集合的元素排序，时间复杂度为 Θ ( n lg ⁡ n ) \Theta(n\lg n) Θ(nlgn)，假设排好序的元素组成序列 A = < a 1 , a 2 , ⋯ , a n > A=<a_1,a_2,\cdots,a_n> A=<a1,a2,⋯,an>，其中 a 1 ⩽ a 2 ⩽ ⋯ ⩽ a n a_1\leqslant a_2\leqslant\cdots\leqslant a_n a1⩽a2⩽⋯⩽an。从数列两端遍历，让left= a 1 a_1 a1,right= a n a_n an，考虑left+right和x的关系。假设此时left= a l a_l al,right= a r a_r ar
如果left+right==x，说明正好找到了题目要求的两个数。
如果left+right>x，那么right右边的所有数 a r ′ a_{r'} ar′都有left + a r ′ > +a_{r'}> +ar′>left + a r > +a_{r}> +ar>x。此时将right左移一位，重新判断。
如果left+right<x，那么left左边的所有数 a l ′ a_{l'} al′都有 a l ′ + a_{l'}+ al′+right > a l >a_{l} >al+right > > >x。此时将left右移一位，重新判断。
当left和right重叠时说明已经找遍了可能产生x的两个数的组合。
可以看出，最好情况一次找到时间复杂度为 Θ ( 1 ) \Theta(1) Θ(1)，最坏情况会遍历一遍排序完的序列，时间复杂度为 Θ ( 1 ) × n = Θ ( n ) \Theta(1)\times n=\Theta(n) Θ(1)×n=Θ(n)，但无论什么情况显然远远小于 Θ ( n lg ⁡ n ) \Theta(n\lg n) Θ(nlgn)的排序时间，所以该算法的时间复杂度为 Θ ( n lg ⁡ n ) \Theta(n\lg n) Θ(nlgn)。

思考题

2-1

a.插入排序n个元素的最坏情况时间复杂度为 Θ ( n 2 ) \Theta(n^2) Θ(n2)。所以 n k \cfrac{n}{k} kn个子表插入排序的时间复杂度为 Θ ( k 2 ) × n k = Θ ( n k ) \Theta(k^2)\times\cfrac{n}{k}=\Theta(nk) Θ(k2)×kn=Θ(nk)

b.归并两个长度为k的子表时间复杂度为 Θ ( k ) \Theta(k) Θ(k)，归并 n k \cfrac{n}{k} kn个子表时间复杂度为 Θ ( k ) × Θ ( n k ) = Θ ( n ) \Theta(k)\times\Theta(\cfrac{n}{k})=\Theta(n) Θ(k)×Θ(kn)=Θ(n)，可知每轮归并时间复杂度为 Θ ( n ) \Theta(n) Θ(n)， n k \cfrac{n}{k} kn个子表需要归并 Θ ( lg ⁡ ( n k ) ) \Theta(\lg(\cfrac{n}{k})) Θ(lg(kn))轮，所以合并子表最坏情况时间复杂度为 Θ ( n ) × Θ ( lg ⁡ ( n k ) ) = Θ ( n lg ⁡ ( n k ) ) \Theta(n)\times\Theta(\lg(\cfrac{n}{k}))=\Theta(n\lg(\cfrac{n}{k})) Θ(n)×Θ(lg(kn))=Θ(nlg(kn))

c.有等式 Θ ( n k + n lg ⁡ ( n k ) ) = Θ ( n lg ⁡ n ) \Theta(nk+n\lg(\cfrac{n}{k}))=\Theta(n\lg n) Θ(nk+nlg(kn))=Θ(nlgn)。根据 Θ \Theta Θ记号的性质，当 k > lg ⁡ n k>\lg n k>lgn时，有 Θ ( n k + n lg ⁡ ( n k ) ) ⩾ Θ ( n k ) > Θ ( n lg ⁡ n ) \Theta(nk+n\lg(\cfrac{n}{k}))\geqslant\Theta(nk)>\Theta(n\lg n) Θ(nk+nlg(kn))⩾Θ(nk)>Θ(nlgn)与等式不符，所以有 k ⩽ lg ⁡ n k\leqslant\lg n k⩽lgn。当 k = lg ⁡ n k=\lg n k=lgn， Θ ( n lg ⁡ ( n k ) ) = Θ ( n lg ⁡ ( n lg ⁡ n ) ) < Θ ( n lg ⁡ n ) \Theta(n\lg(\cfrac{n}{k}))=\Theta(n\lg(\cfrac{n}{\lg n}))<\Theta(n\lg n) Θ(nlg(kn))=Θ(nlg(lgnn))<Θ(nlgn)， Θ ( n lg ⁡ n + n lg ⁡ ( n lg ⁡ n ) ) = Θ ( n lg ⁡ n ) \Theta(n\lg n+n\lg(\cfrac{n}{\lg n}))=\Theta(n\lg n) Θ(nlgn+nlg(lgnn))=Θ(nlgn)
所以k的最大值为 lg ⁡ n \lg n lgn

d.根据c的答案，我们应该选择 k = ⌊ lg ⁡ n ⌋ k=\lfloor\lg n\rfloor k=⌊lgn⌋

2-2

a.还要证明A’和A是元素相同的序列？

b.循环不变式：A[j]是子数组A[j…A.length]的最小值
初始化：j=A.length，子数组为A[A.length…A.length]，只有A[A.length]一个元素，满足条件。
保持：假设某次迭代j=k，有A[k]为A[k…A.length]的最小值，根据3-4行。A[j-1]即A[k-1]将是A[k-1…A.length]中的最小值，则下一次迭代j=k-1前，A[k-1]是A[k-1…A.length]中的最小值。
终止：当j=i时循环终止，此时A[i]正好是数组A[i…A.length]的最小值

c.循环不变式：A[1…i-1]已经放入排序后的元素。
初始化：j=1，子数组为A[1…0]中没有元素，满足条件。
保持：假设某次迭代i=k，有A[1…k-1]已经放入排序后的元素。根据b的证明，内层循环让A[k]正好是数组A[k…A.length]的最小值，因为有A[1…k-1]已经是A的有序排列，所以A[1…k]也已经排序完毕。则在下一次迭代i=k+1前，A[1…k]已经放入排序后的元素。
终止：当i=A.length时循环终止，此时A[1…A.length-1]已经排序完毕，则剩下的A[A.length]也一定是最大的元素，所以A完成排序。

d.冒泡排序最坏情况时间复杂度为 Θ ( n 2 ) \Theta(n^2) Θ(n2)。
性能不如插入排序，因为冒泡排序最好情况时间复杂度也为 Θ ( n 2 ) \Theta(n^2) Θ(n2)，而插入排序最好情况时间复杂度为 Θ ( n ) \Theta(n) Θ(n)。

2-3

a.运行时间为 Θ ( n ) \Theta(n) Θ(n)。

y = 0
for i in range(n+1):
	mul = 1
	for j in range(i):
		mul*=x
	y += a[i]*mul

时间复杂度为 Θ ( n 2 ) \Theta(n^2) Θ(n2)。性能远不如使用霍纳规则

c.
初始化：i=n，所以 y = ∑ k = 0 − 1 a k + n + 1 x k = 0 y=\sum\limits_{k=0}^{-1}a_{k+n+1}x^k=0 y=k=0∑−1ak+n+1xk=0
保持：假设某次迭代i=m，有 y = ∑ k = 0 n − m + 1 a k + m + 1 x k y=\sum\limits_{k=0}^{n-m+1}a_{k+m+1}x^k y=k=0∑n−m+1ak+m+1xk，在本次迭代中
y = a m + x ∑ k = 0 n − m − 1 a k + m + 1 x k = a m + ∑ k = 0 n − m − 1 a k + m + 1 x k + 1 = a m + ∑ k = 0 n − m − 1 a k + m + 1 x k + 1 y=a_m+x\sum\limits_{k=0}^{n-m-1}a_{k+m+1}x^k=a_m+\sum\limits_{k=0}^{n-m-1}a_{k+m+1}x^{k+1}=a_m+\sum\limits_{k=0}^{n-m-1}a_{k+m+1}x^{k+1} y=am+xk=0∑n−m−1ak+m+1xk=am+k=0∑n−m−1ak+m+1xk+1=am+k=0∑n−m−1ak+m+1xk+1，令t=k+1，则 y = a m + ∑ t = 1 n − m a t + m x t = ∑ t = 0 n − m a t + m x t y=a_m+\sum\limits_{t=1}^{n-m}a_{t+m}x^{t}=\sum\limits_{t=0}^{n-m}a_{t+m}x^{t} y=am+t=1∑n−mat+mxt=t=0∑n−mat+mxt，令t=k，则 y = ∑ k = 0 n − m a k + m x k = y = ∑ k = 0 n − [ ( m − 1 ) + 1 ] a k + ( m − 1 ) + 1 x k y=\sum\limits_{k=0}^{n-m}a_{k+m}x^{k}=y=\sum\limits_{k=0}^{n-[(m-1)+1]}a_{k+(m-1)+1}x^{k} y=k=0∑n−mak+mxk=y=k=0∑n−[(m−1)+1]ak+(m−1)+1xk，而下一次迭代前i=m-1，等式 y = ∑ k = 0 n − i + 1 a k + i + 1 x k y=\sum\limits_{k=0}^{n-i+1}a_{k+i+1}x^k y=k=0∑n−i+1ak+i+1xk成立
终止：i=-1时终止，所以 y = ∑ k = 0 n a k x k y=\sum\limits_{k=0}^{n}a_{k}x^k y=k=0∑nakxk

d.根据c中循环不变式的证明可得结论

2-4

a.(1,5) (2,5) (3,4) (3,5) (4,5)

b.数组降序排列时逆序对最多，有 ( n − 1 ) + ( n − 2 ) + ⋯ + 1 = n ( n − 1 ) 2 (n-1)+(n-2)+\cdots+1=\cfrac{n(n-1)}{2} (n−1)+(n−2)+⋯+1=2n(n−1)个逆序对。

c.插入排序运行时间和逆序对数成线性关系。
插入排序中的位置交换全部发生在相邻的元素之间，假设A[m]、A[m+1]之间发生交换，可知A[m]相对于A[1…m-1]和A[m+2…n]的位置没有变化，同理A[m+1]也如此，所以逆序数的变化只存在于A[m]、A[m+1]之间，又因为交换只在A[m+1]<A[m]即(m,m+1)为逆序对时，所以交换后逆序数减一。
反之，如果(m,m+1)为逆序对，当外层循环遍历到m+1时，假设m移动到m’处，则一定有A[m’]是A[m’…m]中最小的元素，因为(m,m+1)为逆序对即A[m’]>A[m+1]，所以A[m+1]一定小于A[m’…m]中任一元素，所以A[m+1]一定会和A[m’…m]中所有元素依次交换。
所以插入排序的交换次数和逆序数等价。

d.由c的部分可知当归并两个子数组时只会减少子数组中的逆序对数，而子数组与子数组外的数字逆序数对不会改变，所以只需要在归并排序的Merge中统计每次的逆序对数，即可计算总逆序对数。

def mergeCount(arr, p, q):
    diff = q - p
    if diff > 0:
        half = (p + q) // 2
        a = mergeCount(arr, p, half)
        b = mergeCount(arr, half + 1, q)
        c = merge(arr, p, half, q)
        return a + b + c
    else:
        return 0


def count(arr):
    return mergeCount(arr, 0, len(arr) - 1)


def merge(arr, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    L = arr[p:q + 1]
    R = arr[q + 1:r + 1]
    i = j = 0
    k = p
    cnt = 0
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
            cnt += n1-i
        k += 1
    while i < n1:
        arr[k] = L[i]
        k += 1
        i += 1
    while j < n2:
        arr[k] = R[j]
        k += 1
        j += 1
    return cnt

第三章函数的增长

练习

3.1 渐进记号

3.1-1

因为 f ( n ) f(n) f(n)与 g ( n ) g(n) g(n)都是渐进非负函数，所以有 max ⁡ ( f ( n ) , g ( n ) ) ⩽ f ( n ) + g ( n ) \max(f(n),g(n))\leqslant f(n)+g(n) max(f(n),g(n))⩽f(n)+g(n)，而且
显然 2 ⋅ max ⁡ ( f ( n ) , g ( n ) ) ⩾ f ( n ) + g ( n ) 2\cdot \max(f(n),g(n))\geqslant f(n)+g(n) 2⋅max(f(n),g(n))⩾f(n)+g(n)，综上有 1 2 [ f ( n ) + g ( n ) ] ⩽ f ( n ) + g ( n ) max ⁡ ( f ( n ) , g ( n ) ) ⩽ f ( n ) + g ( n ) \cfrac{1}{2}[f(n)+g(n)]\leqslant f(n)+g(n)\max(f(n),g(n))\leqslant f(n)+g(n) 21[f(n)+g(n)]⩽f(n)+g(n)max(f(n),g(n))⩽f(n)+g(n)
根据渐进记号 Θ \Theta Θ的定义，所以 max ⁡ ( f ( n ) , g ( n ) ) = Θ ( f ( n ) + g ( n ) ) \max(f(n),g(n))= \Theta(f(n)+g(n)) max(f(n),g(n))=Θ(f(n)+g(n))

3.1-2

取 c 2 > 1 c_2>1 c2>1，令 n 0 + a = c 2 n 0 n_0+a=c_2n_0 n0+a=c2n0，求得 n 0 = a c 2 − 1 n_0=\cfrac{a}{c_2-1} n0=c2−1a，显然当 n > n 0 n>n_0 n>n0时有 n + a < c 2 n n+a<c_2n n+a<c2n，又因为 b > 0 b>0 b>0，所以 ( n + a ) b < ( c 2 n ) b = c 2 b n b (n+a)^b<(c_2n)^b=c_2^bn^b (n+a)b<(c2n)b=c2bnb
同理可得 ( c 1 n ) b < ( n + a ) b (c_1n)^b<(n+a)^b (c1n)b<(n+a)b，所以 ( c 1 n ) b < ( n + a ) b < ( c 2 n ) b (c_1n)^b<(n+a)^b<(c_2n)^b (c1n)b<(n+a)b<(c2n)b即可得 ( n + a ) b = Θ ( n b ) (n+a)^b=\Theta(n^b) (n+a)b=Θ(nb)

3.1-3

因为至少是一个描述下限的词，而 O ( n 2 ) O(n^2) O(n2)只代表函数上界是 n 2 n^2 n2级别的，但没有限制下界， O ( n 2 ) O(n^2) O(n2)中的函数可以任意小，用这些函数描述下限是没有意义的。

3.1-4

2 n + 1 = O ( 2 n ) 2^{n+1}=O(2^n) 2n+1=O(2n)成立，因为 2 n + 1 = 2 ⋅ 2 n < 3 ⋅ 2 n 2^{n+1}=2\cdot2^{n}<3\cdot2^{n} 2n+1=2⋅2n<3⋅2n
2 2 n = O ( 2 n ) 2^{2n}=O(2^n) 22n=O(2n)不成立。假设等式成立，则一定存在正整数 n 0 n_0 n0和正实数 c c c，当 n > n 0 n>n_0 n>n0时有 2 2 n < c 2 n 2^{2n}<c2^n 22n<c2n恒成立，即 c > 2 n c>2^{n} c>2n，显然当 n > lg ⁡ c n>\lg c n>lgc时假设不成立，所以等式不成立。

3.1-5

必要性：
f ( n ) = Θ ( g ( n ) ) f(n)=\Theta(g(n)) f(n)=Θ(g(n))的定义为存在正整数 n 0 n_0 n0和正实数 c 1 , c 2 c_1,c_2 c1,c2，使 n > n 0 n>n_0 n>n0时有 c 1 g ( n ) < f ( n ) < c 2 g ( n ) c_1g(n)<f(n)<c_2g(n) c1g(n)<f(n)<c2g(n)。由 n > n 0 n>n_0 n>n0时有 f ( n ) > c 1 g ( n ) f(n)>c_1g(n) f(n)>c1g(n)得 f ( n ) = Ω ( g ( n ) ) f(n)=\Omega(g(n)) f(n)=Ω(g(n))，由 n > n 0 n>n_0 n>n0时有 f ( n ) < c 2 g ( n ) f(n)<c_2g(n) f(n)<c2g(n)得 f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f(n)=O(g(n))。

充分性：
由 f ( n ) = Ω ( g ( n ) ) f(n)=\Omega(g(n)) f(n)=Ω(g(n))得存在正整数 n 1 n_1 n1和正实数 c 1 c_1 c1使 n > n 1 n>n_1 n>n1时有 f ( n ) > c 1 g ( n ) f(n)>c_1g(n) f(n)>c1g(n)，由 f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f(n)=O(g(n))得存在正整数 n 2 n_2 n2和正实数 c 2 c_2 c2使 n > n 2 n>n_2 n>n2时有 f ( n ) < c 2 g ( n ) f(n)<c_2g(n) f(n)<c2g(n)，取 n 0 = max ⁡ ( n 1 , n 2 ) n_0=\max(n_1,n_2) n0=max(n1,n2)，则当 n > n 0 n>n_0 n>n0时满足 c 1 g ( n ) < f ( n ) < c 2 g ( n ) c_1g(n)<f(n)<c_2g(n) c1g(n)<f(n)<c2g(n)，即 f ( n ) = Θ ( g ( n ) ) f(n)=\Theta(g(n)) f(n)=Θ(g(n))。

综上可证 f ( n ) = Θ ( g ( n ) ) f(n)=\Theta(g(n)) f(n)=Θ(g(n))当且仅当 f ( n ) = Ω ( g ( n ) ) f(n)=\Omega(g(n)) f(n)=Ω(g(n))且 f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f(n)=O(g(n))

3.1-6

因为最坏运行时间为 O ( g ( n ) ) O(g(n)) O(g(n))，而 O ( g ( n ) ) O(g(n)) O(g(n))又表示运行时间的上限，所以运行时间一定满足 O ( g ( n ) ) O(g(n)) O(g(n))，同理可得运行时间也满足 Ω ( g ( n ) ) \Omega(g(n)) Ω(g(n))，由定义3.1得运行时间为 Θ ( g ( n ) ) \Theta(g(n)) Θ(g(n))

3.1-7

根据 o o o记号的定义，存在常量 n 1 n_1 n1对任意正常量 c 1 c_1 c1，使 n > n 1 n>n_1 n>n1时有 f ( n ) < c 1 g ( n ) f(n)<c_1g(n) f(n)<c1g(n)
根据 ω \omega ω记号的定义，存在常量 n 2 n_2 n2对任意正常量 c 2 c_2 c2，使 n > n 2 n>n_2 n>n2时有 f ( n ) > c 2 g ( n ) f(n)>c_2g(n) f(n)>c2g(n)
取 n 0 = max ⁡ ( n 1 , n 2 ) n_0=\max(n_1,n_2) n0=max(n1,n2)，显然当 n > n 0 n>n_0 n>n0时无法同时满足 f ( n ) < c 1 g ( n ) f(n)<c_1g(n) f(n)<c1g(n)和 f ( n ) > c 2 g ( n ) f(n)>c_2g(n) f(n)>c2g(n)，所以 o ( g ( n ) ) o(g(n)) o(g(n))和 ω ( g ( n ) ) \omega (g(n)) ω(g(n))没有交集。

3.1-8

Ω ( g ( n , m ) ) = { f ( n , m ) : 存在正常量 c 、 n 0 和 m 0 ，使得对所有 n ⩾ n 0 或 m ⩾ m 0 ，有 f ( n , m ) ⩾ c g ( n , m ) } \Omega(g(n,m)) = \{ f(n,m) : 存在正常量 c、n_0和m_0，使得对所有n \geqslant n_0或m \geqslant m_0，有f(n,m)\geqslant cg(n,m)\} Ω(g(n,m))={f(n,m):存在正常量c、n0和m0，使得对所有n⩾n0或m⩾m0，有f(n,m)⩾cg(n,m)}
Θ ( g ( n , m ) ) = { f ( n , m ) : 存在正常量 c 1 、 c 2 、 n 0 和 m 0 ，使得对所有 n ⩾ n 0 或 m ⩾ m 0 ，有 c 1 g ( n , m ) ⩽ f ( n , m ) ⩽ c 2 g ( n , m ) } \Theta(g(n,m)) = \{ f(n,m) : 存在正常量 c_1、c_2、n_0和m_0，使得对所有n \geqslant n_0或m \geqslant m_0，有c_1g(n,m)\leqslant f(n,m)\leqslant c_2g(n,m)\} Θ(g(n,m))={f(n,m):存在正常量c1、c2、n0和m0，使得对所有n⩾n0或m⩾m0，有c1g(n,m)⩽f(n,m)⩽c2g(n,m)}

3.2 标准记号与常用函数

3.2-1

根据 f ( x ) f(x) f(x)和 g ( x ) g(x) g(x)的单调性，对任意的 x 1 < x 2 x_1<x_2 x1<x2，总有 f ( x 1 ) < f ( x 2 ) f(x_1)<f(x_2) f(x1)<f(x2)和 g ( x 1 ) < g ( x 2 ) g(x_1)<g(x_2) g(x1)<g(x2)。所以对任意的 x 1 < x 2 x_1<x_2 x1<x2一定有 f ( x 1 ) + g ( x 1 ) < f ( x 2 ) + g ( x 2 ) f(x_1)+g(x_1)<f(x_2)+g(x_2) f(x1)+g(x1)<f(x2)+g(x2)，即 f ( x ) + g ( x ) f(x)+g(x) f(x)+g(x)也单调递增。
因为 f ( x ) f(x) f(x)的单调性，对任意的 x 1 < x 2 x_1<x_2 x1<x2，总有 f ( x 1 ) < f ( x 2 ) f(x_1)<f(x_2) f(x1)<f(x2)。
又因为 g ( x ) g(x) g(x)的单调性， f ( x 1 ) < f ( x 2 ) f(x_1)<f(x_2) f(x1)<f(x2)可以得到 g ( f ( x 1 ) ) < g ( f ( x 2 ) ) g(f(x_1))<g(f(x_2)) g(f(x1))<g(f(x2))，所以 g ( f ( x ) ) g(f(x)) g(f(x))也单调递增。
如果 f ( x ) f(x) f(x)和 g ( x ) g(x) g(x)是非负的，即对任意的 x 1 < x 2 x_1<x_2 x1<x2，总有 0 ⩽ f ( x 1 ) < f ( x 2 ) 0\leqslant f(x_1)<f(x_2) 0⩽f(x1)<f(x2)和 0 ⩽ g ( x 1 ) < g ( x 2 ) 0\leqslant g(x_1)<g(x_2) 0⩽g(x1)<g(x2)，那对任意的 x 1 < x 2 x_1<x_2 x1<x2一定有 f ( x 1 ) g ( x 1 ) < f ( x 2 ) g ( x 2 ) f(x_1)g(x_1)<f(x_2)g(x_2) f(x1)g(x1)<f(x2)g(x2)，所以 f ( x ) g ( x ) f(x)g(x) f(x)g(x)也单调递增。

3.2-2

设 l o g b c = x log_{b}c=x logbc=x，即 b x = c b^x=c bx=c，则有
a l o g b c = a x = b l o g b a x = b x l o g b a = ( b x ) l o g b a = c l o g b a a^{log_{b}c}=a^x=b^{log_ba^x}=b^{xlog_ba}=(b^{x})^{log_ba}=c^{log_ba} alogbc=ax=blogbax=bxlogba=(bx)logba=clogba

3.2-3

根据斯特林公式， lg ⁡ ( n ! ) = lg ⁡ ( 2 π n ( n e ) n ( 1 + Θ ( 1 n ) ) ) = lg ⁡ 2 π n + lg ⁡ ( n e ) n + lg ⁡ ( 1 + Θ ( 1 n ) ) = 1 2 lg ⁡ 2 π n + n l g n e + lg ⁡ ( 1 + Θ ( 1 n ) ) = Θ ( lg ⁡ n ) + Θ ( n lg ⁡ n ) + Θ ( lg ⁡ n ) = Θ ( n lg ⁡ n ) \lg(n!)=\lg(\sqrt{2\pi n}(\cfrac{n}{e})^n(1+\Theta(\cfrac{1}{n})))=\lg\sqrt{2\pi n}+\lg(\cfrac{n}{e})^n+\lg(1+\Theta(\cfrac{1}{n}))=\cfrac{1}{2}\lg2\pi n+n\\lg\cfrac{n}{e}+\lg(1+\Theta(\cfrac{1}{n}))=\Theta(\lg n)+\Theta(n\lg n)+\Theta(\lg n)=\Theta(n\lg n) lg(n!)=lg(2πn (en)n(1+Θ(n1)))=lg2πn +lg(en)n+lg(1+Θ(n1))=21lg2πn+nlgen+lg(1+Θ(n1))=Θ(lgn)+Θ(nlgn)+Θ(lgn)=Θ(nlgn)
因为 lim ⁡ n → ∞ n ! n n = lim ⁡ n → ∞ 1 n lim ⁡ n → ∞ 2 n ⋯ lim ⁡ n → ∞ n n = 0 \lim\limits_{n\rarr \infin}\cfrac{n!}{n^n}=\lim\limits_{n\rarr \infin}\cfrac{1}{n}\lim\limits_{n\rarr \infin}\cfrac{2}{n}\cdots\lim\limits_{n\rarr \infin}\cfrac{n}{n}=0 n→∞limnnn!=n→∞limn1n→∞limn2⋯n→∞limnn=0，所以 n ! = o ( n n ) n!=o(n^n) n!=o(nn)
因为 lim ⁡ n → ∞ n ! 2 n = lim ⁡ n → ∞ 1 2 lim ⁡ n → ∞ 2 2 ⋯ lim ⁡ n → ∞ n 2 = ∞ \lim\limits_{n\rarr \infin}\cfrac{n!}{2^n}=\lim\limits_{n\rarr \infin}\cfrac{1}{2}\lim\limits_{n\rarr \infin}\cfrac{2}{2}\cdots\lim\limits_{n\rarr \infin}\cfrac{n}{2}=\infin n→∞lim2nn!=n→∞lim21n→∞lim22⋯n→∞lim2n=∞，所以 n ! = ω ( 2 n ) n!=\omega(2^n) n!=ω(2n)

3.2-6

ϕ 2 = ( 1 + 5 2 ) 2 = 6 + 2 5 4 = 3 + 5 2 = 1 + 5 2 + 1 = ϕ + 1 \phi^2=(\cfrac{1+\sqrt{5}}{2})^2=\cfrac{6+2\sqrt{5}}{4}=\cfrac{3+\sqrt{5}}{2}=\cfrac{1+\sqrt{5}}{2}+1=\phi+1 ϕ2=(21+5 )2=46+25 =23+5 =21+5 +1=ϕ+1
ϕ ^ 2 = ( 1 − 5 2 ) 2 = 6 − 2 5 4 = 3 − 5 2 = 1 − 5 2 + 1 = ϕ ^ + 1 {\hat\phi}^2=(\cfrac{1-\sqrt{5}}{2})^2=\cfrac{6-2\sqrt{5}}{4}=\cfrac{3-\sqrt{5}}{2}=\cfrac{1-\sqrt{5}}{2}+1=\hat\phi+1 ϕ^2=(21−5 )2=46−25 =23−5 =21−5 +1=ϕ^+1

3.2-7

当i=1时，有 F 1 = ϕ − ϕ ^ 5 = 1 F_1=\cfrac{\phi-\hat\phi}{\sqrt{5}}=1 F1=5 ϕ−ϕ^=1
假设当i=k和i=k+1时等式成立。
那么 F k + 2 = F k + F k + 1 = ϕ k − ϕ ^ k 5 + ϕ k + 1 − ϕ ^ k + 1 5 = ϕ k ( ϕ + 1 ) − ϕ ^ k ( ϕ ^ + 1 ) 5 = ϕ k ( ϕ 2 ) − ϕ ^ k ( ϕ ^ 2 ) 5 = ϕ k + 2 − ϕ ^ k + 2 5 F_{k+2}=F_{k}+F_{k+1}=\cfrac{{\phi}^k-{\hat\phi}^k}{\sqrt{5}}+\cfrac{{\phi}^{k+1}-{\hat\phi}^{k+1}}{\sqrt{5}}=\cfrac{{\phi}^k(\phi+1)-{\hat\phi}^k(\hat\phi+1)}{\sqrt{5}}=\cfrac{{\phi}^k({\phi}^2)-{\hat\phi}^k({\hat\phi}^2)}{\sqrt{5}}=\cfrac{{\phi}^{k+2}-{\hat\phi}^{k+2}}{\sqrt{5}} Fk+2=Fk+Fk+1=5 ϕk−ϕ^k+5 ϕk+1−ϕ^k+1=5 ϕk(ϕ+1)−ϕ^k(ϕ^+1)=5 ϕk(ϕ2)−ϕ^k(ϕ^2)=5 ϕk+2−ϕ^k+2
综上等式成立

3.2-8

由 k ln ⁡ k = Θ ( n ) k\ln k=\Theta(n) klnk=Θ(n)得 k ln ⁡ k ⩽ c 2 n k\ln k\leqslant c_2n klnk⩽c2n即 ln ⁡ k c 2 k ⩽ n \cfrac{\ln k}{c_2}k\leqslant n c2lnkk⩽n，而 lim ⁡ k → ∞ ln ⁡ k c 2 > 1 \lim\limits_{k\rarr \infin}\cfrac{\ln k}{c_2}>1 k→∞limc2lnk>1，所以有 k < n k<n k<n。

由 k ln ⁡ k = Θ ( n ) k\ln k=\Theta(n) klnk=Θ(n)得 c 1 n ⩽ k ln ⁡ k ⩽ c 2 n c_1n\leqslant k\ln k\leqslant c_2n c1n⩽klnk⩽c2n
由 k < n k<n k<n得 k ln ⁡ k < k ln ⁡ n k\ln k<k \ln n klnk<klnn，所以 k ln ⁡ n > c 1 n k \ln n>c_1n klnn>c1n即 k > c 1 n ln ⁡ n k>c_1\cfrac{n}{\ln n} k>c1lnnn
由 ln ⁡ k < ln ⁡ n \ln k < \ln n lnk<lnn和 k ln ⁡ k ⩽ c 2 n k\ln k\leqslant c_2n klnk⩽c2n得 k < c 2 n ln ⁡ n k<c_2\cfrac{n}{\ln n} k<c2lnnn
所以 k = Θ ( n ln ⁡ n ) k=\Theta(\cfrac{n}{\ln n}) k=Θ(lnnn)

思考题

3-1 多项式的渐进行为

引理1：当n足够大时，多项式 p ( n ) = ∑ i = 0 d a i n i p(n)=\sum\limits_{i=0}^{d}a_in^i p(n)=i=0∑daini中最高项系数 a d > 0 a_d>0 ad>0时 p ( n ) p(n) p(n)单调递增， a d < 0 a_d<0 ad<0时 p ( n ) p(n) p(n)单调递减
证明：多项式 p ( n ) p(n) p(n)的m阶导数为 p ( m ) ( n ) = ∑ i = m d a i A i m n i − m p^{(m)}(n)=\sum\limits_{i=m}^{d}a_iA_{i}^{m}n^{i-m} p(m)(n)=i=m∑daiAimni−m，则d阶导数为 p ( d ) ( n ) = ∑ i = d d a i A i d n i − d = a d d ! p^{(d)}(n)=\sum\limits_{i=d}^{d}a_iA_{i}^{d}n^{i-d}=a_dd! p(d)(n)=i=d∑daiAidni−d=add!， a d > 0 a_d>0 ad>0时d阶导数 p ( d ) ( n ) = a d d ! > 0 p^{(d)}(n)=a_dd!>0 p(d)(n)=add!>0，所以d-1阶导数单调递增
d-1阶导数为 p ( d − 1 ) ( n ) = ∑ i = d − 1 d a i A i d − 1 n i − d + 1 = a d − 1 ( d − 1 ) ! + a d A d d − 1 n p^{(d-1)}(n)=\sum\limits_{i=d-1}^{d}a_iA_{i}^{d-1}n^{i-d+1}=a_{d-1}(d-1)!+a_dA_{d}^{d-1}n p(d−1)(n)=i=d−1∑daiAid−1ni−d+1=ad−1(d−1)!+adAdd−1n，令 p ( d − 1 ) ( n ) = 0 p^{(d-1)}(n)=0 p(d−1)(n)=0，因为 p ( d − 1 ) ( n ) p^{(d-1)}(n) p(d−1)(n)单调递增，若等式无解，则 p ( d − 1 ) ( n ) > 0 p^{(d-1)}(n)>0 p(d−1)(n)>0恒成立；若有解，假设解为 n d − 1 n_{d-1} nd−1，则当 n > n d − 1 n>n_{d-1} n>nd−1时 p ( d − 1 ) ( n ) > 0 p^{(d-1)}(n)>0 p(d−1)(n)>0恒成立。综上当n足够大时 p ( d − 1 ) ( n ) > 0 p^{(d-1)}(n)>0 p(d−1)(n)>0恒成立，也即 p ( d − 2 ) ( n ) p^{(d-2)}(n) p(d−2)(n)单调递增。

以此类推，可得当n足够大时，多项式 p ( n ) p(n) p(n)单调递增

同理可证 a d < 0 a_d<0 ad<0时 p ( n ) p(n) p(n)单调递减

引理2：n趋近于无穷时，多项式函数 p ( n ) = ∑ i = 0 d a i n i p(n)=\sum\limits_{i=0}^{d}a_in^i p(n)=i=0∑daini的极限也趋近于无穷。
证明：首先证 1 p ( n ) ∼ 1 a d n d ( n → + ∞ ) \cfrac{1}{p(n)}\sim \cfrac{1}{a_dn^d}(n\rarr +\infin) p(n)1∼adnd1(n→+∞)
因为 lim ⁡ n → + ∞ p ( n ) = lim ⁡ n → + ∞ 1 a d n d 1 p ( n ) = lim ⁡ n → + ∞ p ( n ) a d n d = lim ⁡ n → + ∞ a 0 a d n d + lim ⁡ n → + ∞ a 1 a d n d − 1 + ⋯ + lim ⁡ n → + ∞ a d − 1 a d n + 1 = 1 \lim\limits_{n\rarr +\infin}p(n)=\lim\limits_{n\rarr +\infin}\cfrac{\cfrac{1}{a_dn^d}}{\cfrac{1}{p(n)}}=\lim\limits_{n\rarr +\infin}\cfrac{p(n)}{a_dn^d}=\lim\limits_{n\rarr +\infin}\cfrac{a_{0}}{a_dn^d}+\lim\limits_{n\rarr +\infin}\cfrac{a_1}{a_dn^{d-1}}+\cdots+\lim\limits_{n\rarr +\infin}\cfrac{a_{d-1}}{a_dn}+1=1 n→+∞limp(n)=n→+∞limp(n)1adnd1=n→+∞limadndp(n)=n→+∞limadnda0+n→+∞limadnd−1a1+⋯+n→+∞limadnad−1+1=1，等价无穷小证毕。
所以 lim ⁡ n → + ∞ p ( n ) = lim ⁡ n → + ∞ 1 1 p ( n ) = lim ⁡ n → + ∞ 1 1 a d n d = lim ⁡ n → + ∞ a d n d \lim\limits_{n\rarr +\infin}p(n)=\lim\limits_{n\rarr +\infin}\cfrac{1}{\cfrac{1}{p(n)}}=\lim\limits_{n\rarr +\infin}\cfrac{1}{\cfrac{1}{a_dn^d}}=\lim\limits_{n\rarr +\infin}{a_dn^d} n→+∞limp(n)=n→+∞limp(n)11=n→+∞limadnd11=n→+∞limadnd，所以n趋近于无穷时，当 p ( n ) p(n) p(n)最高项系数 a d > 0 a_d>0 ad>0时 p ( n ) p(n) p(n)趋于正无穷， a d < 0 a_d<0 ad<0时 p ( n ) p(n) p(n)趋于负无穷。

a.
取 c = a d + 1 c=a_d+1 c=ad+1，显然，对于多项式 p ( n ) − c n k p(n)-cn^k p(n)−cnk来说，当 k = d k=d k=d时，最高项为 ( a d − c ) n d (a_d-c)n^d (ad−c)nd，系数 a d − c = − 1 < 0 a_d-c=-1<0 ad−c=−1<0；当 k > d k>d k>d时，最高项为 − c n k -cn^k −cnk，系数 − c = − ( a d + 1 ) < 0 -c=-(a_d+1)<0 −c=−(ad+1)<0。所以多项式 p ( n ) − c n k p(n)-cn^k p(n)−cnk单调递减，且在n趋于无穷的极限为负无穷。所以当n足够大时 p ( n ) − c n k < 0 p(n)-cn^k<0 p(n)−cnk<0即 p ( n ) < c n k p(n)<cn^k p(n)<cnk恒成立，所以 p ( n ) = O ( n k ) p(n)=O(n^k) p(n)=O(nk)

b.
取 c = a d − 1 c=a_d-1 c=ad−1，显然，对于多项式 p ( n ) − c n k p(n)-cn^k p(n)−cnk来说，当 k = d k=d k=d时，最高项为 ( a d − c ) n d (a_d-c)n^d (ad−c)nd，系数 a d − c = 1 > 0 a_d-c=1>0 ad−c=1>0；当 k < d k<d k<d时，最高项为 a d n d a_dn^d adnd，系数 a d > 0 a_d>0 ad>0。所以多项式 p ( n ) − c n k p(n)-cn^k p(n)−cnk单调递增，且在n趋于无穷的极限为正无穷。所以当n足够大时 p ( n ) − c n k > 0 p(n)-cn^k>0 p(n)−cnk>0即 p ( n ) > c n k p(n)>cn^k p(n)>cnk恒成立，所以 p ( n ) = Ω ( n k ) p(n)=\Omega(n^k) p(n)=Ω(nk)

c.
取 c = a d − 1 c=a_d-1 c=ad−1，可得 p ( n ) = Ω ( n k ) p(n)=\Omega(n^k) p(n)=Ω(nk)；取 c = a d + 1 c=a_d+1 c=ad+1，可得 p ( n ) = O ( n k ) p(n)=O(n^k) p(n)=O(nk)，所以 p ( n ) = Θ ( n k ) p(n)=\Theta(n^k) p(n)=Θ(nk)

d.
对任意正常量c， p ( n ) − c n k p(n)-cn^k p(n)−cnk最高项系数为 − c < 0 -c<0 −c<0，所以n足够大时单调递减且趋近负无穷，所以有 0 ⩽ p ( n ) < c n k 0\leqslant p(n)<cn^k 0⩽p(n)<cnk，也即 p ( n ) = o ( n ) p(n)=o(n) p(n)=o(n)

e.
对任意正常量c， p ( n ) − c n k p(n)-cn^k p(n)−cnk最高项系数为 a d > 0 a_d>0 ad>0，所以n足够大时单调递增且趋近正无穷，所以有 p ( n ) > c n k p(n)>cn^k p(n)>cnk，也即 p ( n ) = ω ( n ) p(n)=\omega(n) p(n)=ω(n)

3-2 相对渐进增长

A	b	O O O	o o o	Ω \Omega Ω	ω \omega ω	Θ \Theta Θ
lg ⁡ k n \lg ^k n lgkn	n ϵ n^\epsilon nϵ	是	是	否	否	否
n k n^k nk	c n c^n cn	是	是	否	否	否
n \sqrt{n} n	n sin ⁡ n n^{\sin n} nsinn	否	否	否	否	否
2 n 2^n 2n	2 n / 2 2^{n/2} 2n/2	否	否	是	是	否
n lg ⁡ c n ^{\lg c} nlgc	c lg ⁡ n c^{\lg n} clgn	是	否	是	否	是
lg ⁡ ( n ! ) \lg(n!) lg(n!)	lg ⁡ ( n n ) \lg(n^n) lg(nn)	是	否	是	否	是

3-3 根据渐进增长率排序

g 1 ( n ) = 2 2 n + 1 , g 2 ( n ) = 2 2 n , g_1(n)=2^{2^{n+1}},g_2(n)=2^{2^{n}}, g1(n)=22n+1,g2(n)=22n,
g 3 ( n ) = ( n + 1 ) ! , g 4 ( n ) = n ! , g_3(n)=(n+1)!,g_4(n)=n!, g3(n)=(n+1)!,g4(n)=n!,
g 5 ( n ) = ( lg ⁡ n ) ! , g_5(n)=(\lg n)!, g5(n)=(lgn)!,
g 6 ( n ) = n lg ⁡ lg ⁡ n , g 7 ( n ) = ( lg ⁡ n ) lg ⁡ n , g_6(n)=n^{\lg\lg n},g_7(n)=(\lg n)^{\lg n}, g6(n)=nlglgn,g7(n)=(lgn)lgn,
g 8 ( n ) = n 2 n , g_8(n)=n2^n, g8(n)=n2n,
g 9 ( n ) = e n , g_9(n)=e^n, g9(n)=en,
g 10 ( n ) = 2 n , g_{10}(n)=2^n, g10(n)=2n,
g 11 ( n ) = ( 3 2 ) n , g_{11}(n)=(\cfrac{3}{2})^n, g11(n)=(23)n,
g 12 ( n ) = 2 2 lg ⁡ n , g_{12}(n)=2^{\sqrt{2\lg n}}, g12(n)=22lgn ,
g 13 ( n ) = n 3 , g_{13}(n)=n^3, g13(n)=n3,
g 14 ( n ) = 4 lg ⁡ n , g 15 ( n ) = n 2 , g_{14}(n)=4^{\lg n},g_{15}(n)=n^2, g14(n)=4lgn,g15(n)=n2,
g 16 ( n ) = n lg ⁡ n , g 17 ( n ) = lg ⁡ ( n ! ) , g_{16}(n)=n{\lg n},g_{17}(n)=\lg (n!), g16(n)=nlgn,g17(n)=lg(n!),
g 18 ( n ) = n , g 19 ( n ) = 2 lg ⁡ n , g_{18}(n)=n,g_{19}(n)=2^{\lg n}, g18(n)=n,g19(n)=2lgn,
g 20 ( n ) = ( 2 ) lg ⁡ n , g_{20}(n)=(\sqrt{2})^{\lg n}, g20(n)=(2 )lgn,
g 21 ( n ) = lg ⁡ 2 n , g_{21}(n)=\lg^2 n, g21(n)=lg2n,
g 22 ( n ) = ln ⁡ n , g_{22}(n)=\ln n, g22(n)=lnn,
g 23 ( n ) = lg ⁡ n , g_{23}(n)=\sqrt{\lg n}, g23(n)=lgn ,
g 24 ( n ) = ln ⁡ ln ⁡ n , g_{24}(n)=\ln \ln n, g24(n)=lnlnn,
g 25 ( n ) = 2 lg ⁡ ∗ n , g 26 ( n ) = lg ⁡ ∗ n , g 27 ( n ) = lg ⁡ ∗ ( lg ⁡ n ) , g 28 ( n ) = lg ⁡ ( lg ⁡ ∗ n ) , g_{25}(n)=2^{\lg^* n},g_{26}(n)={\lg^* n},g_{27}(n)={\lg^* (\lg n)},g_{28}(n)=\lg({\lg^* n}), g25(n)=2lg∗n,g26(n)=lg∗n,g27(n)=lg∗(lgn),g28(n)=lg(lg∗n),
g 29 ( n ) = 1 , g 30 ( n ) = n 1 / lg ⁡ n , g_{29}(n)=1,g_{30}(n)=n^{1/\lg n}, g29(n)=1,g30(n)=n1/lgn,

b.
2 2 x s i n ( x ) 2^{2^{xsin(x)}} 22xsin(x)

3-4 渐进记号的性质

这里假设渐进正函数不包括常量，即。

a.不成立，对 f ( n ) = n , g ( n ) = n 2 f(n) = n,g(n)=n^2 f(n)=n,g(n)=n2而言， f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f(n)=O(g(n))但 g ( n ) ≠ O ( f ( n ) ) g(n)\neq O(f(n)) g(n)=O(f(n))

b.不成立，对 f ( n ) = n , g ( n ) = n 2 f(n) = n,g(n)=n^2 f(n)=n,g(n)=n2而言， f ( n ) + g ( n ) = Θ ( n 2 ) f(n)+g(n)=\Theta(n^2) f(n)+g(n)=Θ(n2)但 min ⁡ ( f ( n ) , g ( n ) ) = n ≠ n 2 \min(f(n),g(n))=n\neq n^2 min(f(n),g(n))=n=n2

c.成立。由 f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f(n)=O(g(n))可得 f ( n ) < c g ( n ) f(n)<cg(n) f(n)<cg(n)，当n足够大时有 lg ⁡ f ( n ) < lg ⁡ ( c g ( n ) ) = lg ⁡ g ( n ) + lg ⁡ c \lg f(n)<\lg(cg(n))=\lg g(n)+\lg c lgf(n)<lg(cg(n))=lgg(n)+lgc，取 g ( n 0 ) = c g(n_0)=c g(n0)=c，则 lg ⁡ f ( n ) < lg ⁡ g ( n ) + lg ⁡ c = lg ⁡ g ( n ) + lg ⁡ g ( n 0 ) < 2 lg ⁡ g ( n ) \lg f(n)<\lg g(n)+\lg c=\lg g(n)+\lg g(n_0) <2\lg g(n) lgf(n)<lgg(n)+lgc=lgg(n)+lgg(n0)<2lgg(n)

d.不成立。对 f ( n ) = 4 n , g ( n ) = n f(n) = 4n,g(n)=n f(n)=4n,g(n)=n而言， f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f(n)=O(g(n))但 2 f ( n ) = 2 4 n = 1 6 n 2^{f(n)}=2^{4n}=16^n 2f(n)=24n=16n， 2 g ( n ) = 2 n 2^{g(n)}=2^n 2g(n)=2n，显然 2 f ( n ) ≠ O ( 2 g ( n ) ) 2^{f(n)}\neq O(2^{g(n)}) 2f(n)=O(2g(n))

e.不成立。假设成立，一定有 f ( n ) < c f ( n ) 2 f(n)<cf(n)^2 f(n)<cf(n)2，即存在c满足 f ( n ) > 1 c f(n)>\cfrac{1}{c} f(n)>c1。因为 f ( n ) f(n) f(n)是正函数，如果 f ( n ) f(n) f(n)的最小值不趋于0，则一定存在c满足条件；如果 f ( n ) f(n) f(n)的最小值趋于0，就没有确定的c满足条件，所以不成立。

f.成立。由 f ( n ) < c g ( n ) f(n)<cg(n) f(n)<cg(n)可以推出 g ( n ) > 1 c f ( n ) g(n)>\cfrac{1}{c}f(n) g(n)>c1f(n)

g.不成立。对 f ( n ) = 2 n f(n) = 2^n f(n)=2n而言， f ( n 2 ) = 2 n 2 = 2 n f(\cfrac{n}{2})=2^{\frac{n}{2}}=\sqrt{2}^n f(2n)=22n=2 n，显然 f ( n ) = ω ( f ( n 2 ) ) f(n)=\omega(f(\cfrac{n}{2})) f(n)=ω(f(2n))

h.成立。设 g ( n ) = o ( f ( n ) ) g(n)=o(f(n)) g(n)=o(f(n))，则有 f ( n ) ⩽ f ( n ) + g ( n ) < f ( n ) + c f ( n ) ⩽ ( c + 1 ) f ( n ) f(n)\leqslant f(n)+g(n) <f(n) + cf(n)\leqslant (c+1)f(n) f(n)⩽f(n)+g(n)<f(n)+cf(n)⩽(c+1)f(n)

3-5 O O O与 Ω \Omega Ω的一些变形

a.非形式化地说， O ( g ( n ) ) O(g(n)) O(g(n))的否命题是存在c使得对某些n满足 f ( n ) ⩾ c g ( n ) f(n)\geqslant cg(n) f(n)⩾cg(n)，如果这些n是有限个，取这些n的最大值 n 0 n_0 n0，当 n > n 0 n>n_0 n>n0依然会满足 f ( n ) ⩽ g ( n ) f(n)\leqslant g(n) f(n)⩽g(n)也即 O ( g ( n ) ) O(g(n)) O(g(n))。所以 O ( g ( n ) ) O(g(n)) O(g(n))的否命题一定是存在c使得对无穷多个n满足 f ( n ) ⩾ c g ( n ) f(n)\geqslant cg(n) f(n)⩾cg(n)，这正好是 Ω ∞ \Omega^\infin Ω∞的定义

b.使用 Ω ∞ \Omega^\infin Ω∞的优点是可以刻画一些震荡发散函数的总体下界，缺点是下界不精确，总会存在
摸了

3-6 多重函数

摸了

这篇关于《算法导论》练习与思考题第1-3章 (python版)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！