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

2022/2/7 22:44:51

本文主要是介绍《算法导论》练习与思考题第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+121​n(n+1)​=21​n=Θ(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)。

b.

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∑−1​ak+n+1​xk=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+1​ak+m+1​xk,在本次迭代中
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−1​ak+m+1​xk=am​+k=0∑n−m−1​ak+m+1​xk+1=am​+k=0∑n−m−1​ak+m+1​xk+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−m​at+m​xt=t=0∑n−m​at+m​xt,令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−m​ak+m​xk=y=k=0∑n−[(m−1)+1]​ak+(m−1)+1​xk,而下一次迭代前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+1​ak+i+1​xk成立
终止:i=-1时终止,所以 y = ∑ k = 0 n a k x k y=\sum\limits_{k=0}^{n}a_{k}x^k y=k=0∑n​ak​xk

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=c2​n0​,求得 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<c2​n,又因为 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<(c2​n)b=c2b​nb
同理可得 ( c 1 n ) b < ( n + a ) b (c_1n)^b<(n+a)^b (c1​n)b<(n+a)b,所以 ( c 1 n ) b < ( n + a ) b < ( c 2 n ) b (c_1n)^b<(n+a)^b<(c_2n)^b (c1​n)b<(n+a)b<(c2​n)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) c1​g(n)<f(n)<c2​g(n)。由 n > n 0 n>n_0 n>n0​时有 f ( n ) > c 1 g ( n ) f(n)>c_1g(n) f(n)>c1​g(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)<c2​g(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)>c1​g(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)<c2​g(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) c1​g(n)<f(n)<c2​g(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)<c1​g(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)>c2​g(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)<c1​g(n)和 f ( n ) > c 2 g ( n ) f(n)>c_2g(n) f(n)>c2​g(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​,有c1​g(n,m)⩽f(n,m)⩽c2​g(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 logb​c=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} alogb​c=ax=blogb​ax=bxlogb​a=(bx)logb​a=clogb​a

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​))=21​lg2π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→∞lim​nnn!​=n→∞lim​n1​n→∞lim​n2​⋯n→∞lim​nn​=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→∞lim​2nn!​=n→∞lim​21​n→∞lim​22​⋯n→∞lim​2n​=∞,所以 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⩽c2​n即 ln ⁡ k c 2 k ⩽ n \cfrac{\ln k}{c_2}k\leqslant n c2​lnk​k⩽n,而 lim ⁡ k → ∞ ln ⁡ k c 2 > 1 \lim\limits_{k\rarr \infin}\cfrac{\ln k}{c_2}>1 k→∞lim​c2​lnk​>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 c1​n⩽klnk⩽c2​n
由 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>c1​n即 k > c 1 n ln ⁡ n k>c_1\cfrac{n}{\ln n} k>c1​lnnn​
由 ln ⁡ k < ln ⁡ n \ln k < \ln n lnk<lnn和 k ln ⁡ k ⩽ c 2 n k\ln k\leqslant c_2n klnk⩽c2​n得 k < c 2 n ln ⁡ n k<c_2\cfrac{n}{\ln n} k<c2​lnnn​
所以 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∑d​ai​ni中最高项系数 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∑d​ai​Aim​ni−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∑d​ai​Aid​ni−d=ad​d!, 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)=ad​d!>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∑d​ai​Aid−1​ni−d+1=ad−1​(d−1)!+ad​Add−1​n,令 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∑d​ai​ni的极限也趋近于无穷。
证明:首先证 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​∼ad​nd1​(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→+∞lim​p(n)=n→+∞lim​p(n)1​ad​nd1​​=n→+∞lim​ad​ndp(n)​=n→+∞lim​ad​nda0​​+n→+∞lim​ad​nd−1a1​​+⋯+n→+∞lim​ad​nad−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→+∞lim​p(n)=n→+∞lim​p(n)1​1​=n→+∞lim​ad​nd1​1​=n→+∞lim​ad​nd,所以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 ad​nd,系数 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 相对渐进增长

Ab 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 根据渐进增长率排序

a.

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)>c1​f(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版)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程