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

练习

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时在同一台机器上$100n^2$的算法优于$2^n$的算法

思考题

1-1 运行时间的比较

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

	1秒钟（1000ms）	1分钟（60000ms）	1小时（3600000ms）	1天(86400000ms)	1月(2592000000ms)	1年(31536000000ms)	1世纪(3153600000000ms)
$\lg n$	$10^{1000}$	$10^{60000}$	$10^{3600000}$	$10^{86400000}$	$10^{2592000000}$	$10^{31536000000}$	$10^{3153600000000}$
$\sqrt{n}$	$1000^2$	$60000^2$	$3600000^2$	$86400000^2$	$2592000000^2$	$31536000000^2$	$3153600000000^2$
$n$	$1000$	$60000$	$3600000$	$86400000$	$2592000000$	$31536000000$	$3153600000000$
$n^2$	$31$	$244$	$1897$	$9295$	$50911$	$177583$	$1,775,837$
$n^3$	$10$	$39$	$153$	$442$	$1373$	$3159$	$14,664$
$2^n$	$9$	$15$	$21$	$26$	$31$	$34$	$41$
$n!$	$6$	$8$	$9$	$11$	$12$	$13$	$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,\cdots ,a_n>$和$B=<b_1,b_2,\cdots ,b_n>$,A和B表示两个二进制数每个数位的依次排列
     输出： n+1个数的序列$C=<c_1,c_2,\cdots ,c_{n+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

$\Theta (n^3)$

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次就足够。
最好情况和最坏情况都是$\Theta (n^2)$的运行时间

2.2-3

平均情况和最坏情况运行时间均为$\Theta (n)$。
证明：
平均情况时，假设v有n+1种情况，v等可能的出现在A中任一位置或者不出现。
所以平均的运行时间为$\frac{1+2+\cdots +n}{n+1}=\frac{\frac{1}{2}n(n+1)}{n+1}=\frac{1}{2}n=\Theta (n)$
最坏情况时不出现，总共循环比较n次，运行时间为$\Theta (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$，$T(n)=T(2)=2,n\lg n=2$，所以$T(n)=n\lg n$
假设：k=m时等式成立，$n=2^m,T(n)=n\lg n=m{2}^m$。因此k=m+1时将$n=2^{m+1}$带入$T(n)=2T(\frac{n}{2})+n$中，得$T(n)=2T(2^m)+2^{m+1}=m{2}^{m+1}+2^{m+1}=(m+1)2^{m+1}$，而$n\lg n=2^{m+1}\lg (2^{m+1})=(m+1)2^{m+1}$,所以$T(n)=n\lg n$成立
综上所述，当n刚好是2的幂时，本题递归式的解为$T(n)=n\lg n$

2.3-4

$$T(n)=\{\begin{array}{ll}\Theta (1),& n=1\\ T(n-1)+\Theta (n),& n>1\end{array}$$

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)=\{\begin{array}{ll}\Theta (1),& n=1\\ T(\frac{n}{2})+\Theta (1),& n>1\end{array}$$
显然有：
$$\lg n\{\begin{array}{l}T(n)-T(\frac{n}{2})=\Theta (1)\\ T(\frac{n}{2})-T(\frac{n}{2^2})=\Theta (1)\\ T(\frac{n}{2^2})-T(\frac{n}{2^3})=\Theta (1)\\ \cdots \cdots \\ T(2)-T(1)=\Theta (1)\end{array}$$
所以最坏情况的运行时间为$\Theta (\lg n)$

2.3-6

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

2.3-7

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

思考题

2-1

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

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

c.有等式$\Theta (nk+n\lg (\frac{n}{k}))=\Theta (n\lg n)$。根据$\Theta$记号的性质，当$k>\lg n$时，有$\Theta (nk+n\lg (\frac{n}{k}))⩾\Theta (nk)>\Theta (n\lg n)$与等式不符，所以有$k⩽\lg n$。当$k=\lg n$，$\Theta (n\lg (\frac{n}{k}))=\Theta (n\lg (\frac{n}{\lg n}))<\Theta (n\lg n)$，$\Theta (n\lg n+n\lg (\frac{n}{\lg n}))=\Theta (n\lg n)$
所以k的最大值为$\lg n$

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

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.冒泡排序最坏情况时间复杂度为$\Theta (n^2)$。
性能不如插入排序，因为冒泡排序最好情况时间复杂度也为$\Theta (n^2)$，而插入排序最好情况时间复杂度为$\Theta (n)$。

2-3

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

b.

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

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

c.
初始化：i=n，所以$y=\sum _{k=0}^{-1}{a}_{k+n+1}{x}^k=0$
保持：假设某次迭代i=m，有$y=\sum _{k=0}^{n-m+1}{a}_{k+m+1}{x}^k$，在本次迭代中
$y=a_m+x\sum _{k=0}^{n-m-1}{a}_{k+m+1}{x}^k=a_m+\sum _{k=0}^{n-m-1}{a}_{k+m+1}{x}^{k+1}=a_m+\sum _{k=0}^{n-m-1}{a}_{k+m+1}{x}^{k+1}$，令t=k+1，则$y=a_m+\sum _{t=1}^{n-m}{a}_{t+m}{x}^t=\sum _{t=0}^{n-m}{a}_{t+m}{x}^t$，令t=k，则$y=\sum _{k=0}^{n-m}{a}_{k+m}{x}^k=y=\sum _{k=0}^{n-[(m-1)+1]}{a}_{k+(m-1)+1}{x}^k$，而下一次迭代前i=m-1，等式$y=\sum _{k=0}^{n-i+1}{a}_{k+i+1}{x}^k$成立
终止：i=-1时终止，所以$y=\sum _{k=0}^n{a}_k{x}^k$

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

2-4

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

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

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)$与$g(n)$都是渐进非负函数，所以有$\max (f(n),g(n))⩽f(n)+g(n)$，而且
显然$2\cdot \max (f(n),g(n))⩾f(n)+g(n)$，综上有$\frac{1}{2}[f(n)+g(n)]⩽f(n)+g(n)\max (f(n),g(n))⩽f(n)+g(n)$
根据渐进记号$\Theta$的定义，所以$\max (f(n),g(n))=\Theta (f(n)+g(n))$

3.1-2

取$c_2>1$，令$n_0+a=c_2{n}_0$，求得$n_0=\frac{a}{c_2-1}$，显然当$n>n_0$时有$n+a<c_{2}n$，又因为$b>0$，所以$(n+a{)}^b<(c_{2}n{)}^b=c_2^b{n}^b$
同理可得$(c_{1}n{)}^b<(n+a{)}^b$，所以$(c_{1}n{)}^b<(n+a{)}^b<(c_{2}n{)}^b$即可得$(n+a{)}^b=\Theta (n^b)$

3.1-3

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

3.1-4

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

3.1-5

必要性：
$f(n)=\Theta (g(n))$的定义为存在正整数$n_0$和正实数$c_1,c_2$，使$n>n_0$时有$c_{1}g(n)<f(n)<c_{2}g(n)$。由$n>n_0$时有$f(n)>c_{1}g(n)$得$f(n)=\Omega (g(n))$，由$n>n_0$时有$f(n)<c_{2}g(n)$得$f(n)=O(g(n))$。

充分性：
由$f(n)=\Omega (g(n))$得存在正整数$n_1$和正实数$c_1$使$n>n_1$时有$f(n)>c_{1}g(n)$，由$f(n)=O(g(n))$得存在正整数$n_2$和正实数$c_2$使$n>n_2$时有$f(n)<c_{2}g(n)$，取$n_0=\max (n_1,n_2)$，则当$n>n_0$时满足$c_{1}g(n)<f(n)<c_{2}g(n)$，即$f(n)=\Theta (g(n))$。

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

3.1-6

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

3.1-7

根据$o$记号的定义，存在常量$n_1$对任意正常量$c_1$，使$n>n_1$时有$f(n)<c_{1}g(n)$
根据$\omega$记号的定义，存在常量$n_2$对任意正常量$c_2$，使$n>n_2$时有$f(n)>c_{2}g(n)$
取$n_0=\max (n_1,n_2)$，显然当$n>n_0$时无法同时满足$f(n)<c_{1}g(n)$和$f(n)>c_{2}g(n)$，所以$o(g(n))$和$\omega (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)$和$g(x)$的单调性，对任意的$x_1<x_2$，总有$f(x_1)<f(x_2)$和$g(x_1)<g(x_2)$。所以对任意的$x_1<x_2$一定有$f(x_1)+g(x_1)<f(x_2)+g(x_2)$，即$f(x)+g(x)$也单调递增。
因为$f(x)$的单调性，对任意的$x_1<x_2$，总有$f(x_1)<f(x_2)$。
又因为$g(x)$的单调性，$f(x_1)<f(x_2)$可以得到$g(f(x_1))<g(f(x_2))$，所以$g(f(x))$也单调递增。
如果$f(x)$和$g(x)$是非负的，即对任意的$x_1<x_2$，总有$0⩽f(x_1)<f(x_2)$和$0⩽g(x_1)<g(x_2)$，那对任意的$x_1<x_2$一定有$f(x_1)g(x_1)<f(x_2)g(x_2)$，所以$f(x)g(x)$也单调递增。

3.2-2

设$lo{g}_{b}c=x$，即$b^x=c$，则有
$$a^{lo{g}_{b}c}=a^x=b^{lo{g}_b{a}^x}=b^{xlo{g}_{b}a}=(b^x{)}^{lo{g}_{b}a}=c^{lo{g}_{b}a}$$

3.2-3

根据斯特林公式，$$\begin{gathered} \lg (n!)=\lg (\sqrt{2\pi n}(\frac{n}{e}{)}^n(1+\Theta (\frac{1}{n})))=\lg \sqrt{2\pi n}+\lg (\frac{n}{e}{)}^n+\lg (1+\Theta (\frac{1}{n}))=\frac{1}{2}\lg 2\pi n+n \\ lg\frac{n}{e}+\lg (1+\Theta (\frac{1}{n}))=\Theta (\lg n)+\Theta (n\lg n)+\Theta (\lg n)=\Theta (n\lg n) \end{gathered}$$
因为$\underset{n\to \infty }{\lim }\frac{n!}{n^n}=\underset{n\to \infty }{\lim }\frac{1}{n}\underset{n\to \infty }{\lim }\frac{2}{n}\cdots \underset{n\to \infty }{\lim }\frac{n}{n}=0$，所以$n!=o(n^n)$
因为$\underset{n\to \infty }{\lim }\frac{n!}{2^n}=\underset{n\to \infty }{\lim }\frac{1}{2}\underset{n\to \infty }{\lim }\frac{2}{2}\cdots \underset{n\to \infty }{\lim }\frac{n}{2}=\infty$，所以$n!=\omega (2^n)$

3.2-6

${\varphi }^2=(\frac{1+\sqrt{5}}{2}{)}^2=\frac{6+2\sqrt{5}}{4}=\frac{3+\sqrt{5}}{2}=\frac{1+\sqrt{5}}{2}+1=\varphi +1$
${\hat{\varphi }}^2=(\frac{1-\sqrt{5}}{2}{)}^2=\frac{6-2\sqrt{5}}{4}=\frac{3-\sqrt{5}}{2}=\frac{1-\sqrt{5}}{2}+1=\hat{\varphi }+1$

3.2-7

当i=1时，有$F_1=\frac{\varphi -\hat{\varphi }}{\sqrt{5}}=1$
假设当i=k和i=k+1时等式成立。
那么$F_{k+2}=F_k+F_{k+1}=\frac{{\varphi }^k-{\hat{\varphi }}^k}{\sqrt{5}}+\frac{{\varphi }^{k+1}-{\hat{\varphi }}^{k+1}}{\sqrt{5}}=\frac{{\varphi }^k(\varphi +1)-{\hat{\varphi }}^k(\hat{\varphi }+1)}{\sqrt{5}}=\frac{{\varphi }^k({\varphi }^2)-{\hat{\varphi }}^k({\hat{\varphi }}^2)}{\sqrt{5}}=\frac{{\varphi }^{k+2}-{\hat{\varphi }}^{k+2}}{\sqrt{5}}$
综上等式成立

3.2-8

由$k\ln k=\Theta (n)$得$k\ln k⩽c_{2}n$即$\frac{\ln k}{c_2}k⩽n$，而$\underset{k\to \infty }{\lim }\frac{\ln k}{c_2}>1$，所以有$k<n$。

由$k\ln k=\Theta (n)$得$c_{1}n⩽k\ln k⩽c_{2}n$
由$k<n$得$k\ln k<k\ln n$，所以$k\ln n>c_{1}n$即$k>c_1\frac{n}{\ln n}$
由$\ln k<\ln n$和$k\ln k⩽c_{2}n$得$k<c_2\frac{n}{\ln n}$
所以$k=\Theta (\frac{n}{\ln n})$

思考题

3-1 多项式的渐进行为

引理1：当n足够大时，多项式$p(n)=\sum _{i=0}^d{a}_i{n}^i$中最高项系数$a_d>0$时$p(n)$单调递增，$a_d<0$时$p(n)$单调递减
证明：多项式$p(n)$的m阶导数为$p^{(m)}(n)=\sum _{i=m}^d{a}_i{A}_i^m{n}^{i-m}$，则d阶导数为$p^{(d)}(n)=\sum _{i=d}^d{a}_i{A}_i^d{n}^{i-d}=a_{d}d!$，$a_d>0$时d阶导数$p^{(d)}(n)=a_{d}d!>0$，所以d-1阶导数单调递增
d-1阶导数为$p^{(d-1)}(n)=\sum _{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)=0$，因为$p^{(d-1)}(n)$单调递增，若等式无解，则$p^{(d-1)}(n)>0$恒成立；若有解，假设解为$n_{d-1}$，则当$n>n_{d-1}$时$p^{(d-1)}(n)>0$恒成立。综上当n足够大时$p^{(d-1)}(n)>0$恒成立，也即$p^{(d-2)}(n)$单调递增。

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

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

---

引理2：n趋近于无穷时，多项式函数$p(n)=\sum _{i=0}^d{a}_i{n}^i$的极限也趋近于无穷。
证明：首先证$\frac{1}{p(n)}\sim \frac{1}{a_d{n}^d}(n\to +\infty )$
因为$\underset{n\to +\infty }{\lim }p(n)=\underset{n\to +\infty }{\lim }\frac{\frac{1}{a_d{n}^d}}{\frac{1}{p(n)}}=\underset{n\to +\infty }{\lim }\frac{p(n)}{a_d{n}^d}=\underset{n\to +\infty }{\lim }\frac{a_0}{a_d{n}^d}+\underset{n\to +\infty }{\lim }\frac{a_1}{a_d{n}^{d-1}}+\cdots +\underset{n\to +\infty }{\lim }\frac{a_{d-1}}{a_{d}n}+1=1$，等价无穷小证毕。
所以$\underset{n\to +\infty }{\lim }p(n)=\underset{n\to +\infty }{\lim }\frac{1}{\frac{1}{p(n)}}=\underset{n\to +\infty }{\lim }\frac{1}{\frac{1}{a_d{n}^d}}=\underset{n\to +\infty }{\lim }{a}_d{n}^d$，所以n趋近于无穷时，当$p(n)$最高项系数$a_d>0$时$p(n)$趋于正无穷，$a_d<0$时$p(n)$趋于负无穷。

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

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

c.
取$c=a_d-1$，可得$p(n)=\Omega (n^k)$；取$c=a_d+1$，可得$p(n)=O(n^k)$，所以$p(n)=\Theta (n^k)$

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

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

3-2 相对渐进增长

A	b	$O$	$o$	$\Omega$	$\omega$	$\Theta$
${\lg }^{k}n$	$n^{ϵ}$	是	是	否	否	否
$n^k$	$c^n$	是	是	否	否	否
$\sqrt{n}$	$n^{\sin n}$	否	否	否	否	否
$2^n$	$2^{n/2}$	否	否	是	是	否
$n^{\lg c}$	$c^{\lg n}$	是	否	是	否	是
$\lg (n!)$	$\lg (n^n)$	是	否	是	否	是

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

a.

$g_1(n)=2^{2^{n+1}},g_2(n)=2^{2^n},$
$g_3(n)=(n+1)!,g_4(n)=n!,$
$g_5(n)=(\lg n)!,$
$g_6(n)=n^{\lg \lg n},g_7(n)=(\lg n{)}^{\lg n},$
$g_8(n)=n{2}^n,$
$g_9(n)=e^n,$
$g_{10}(n)=2^n,$
$g_{11}(n)=(\frac{3}{2}{)}^n,$
$g_{12}(n)=2^{\sqrt{2\lg n}},$
$g_{13}(n)=n^3,$
$g_{14}(n)=4^{\lg n},g_{15}(n)=n^2,$
$g_{16}(n)=n\lg n,g_{17}(n)=\lg (n!),$
$g_{18}(n)=n,g_{19}(n)=2^{\lg n},$
$g_{20}(n)=(\sqrt{2}{)}^{\lg n},$
$g_{21}(n)={\lg }^{2}n,$
$g_{22}(n)=\ln n,$
$g_{23}(n)=\sqrt{\lg n},$
$g_{24}(n)=\ln \ln n,$
$g_{25}(n)=2^{{\lg }^{\ast }n},g_{26}(n)={\lg }^{\ast }n,g_{27}(n)={\lg }^{\ast }(\lg n),g_{28}(n)=\lg ({\lg }^{\ast }n),$
$g_{29}(n)=1,g_{30}(n)=n^{1/\lg n},$

b.
$2^{2^{xsin(x)}}$

3-4 渐进记号的性质

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

a.不成立，对$f(n)=n,g(n)=n^2$而言，$f(n)=O(g(n))$但$g(n)\ne O(f(n))$

b.不成立，对$f(n)=n,g(n)=n^2$而言，$f(n)+g(n)=\Theta (n^2)$但$\min (f(n),g(n))=n\ne n^2$

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

d.不成立。对$f(n)=4n,g(n)=n$而言，$f(n)=O(g(n))$但$2^{f(n)}=2^{4n}=16^n$，$2^{g(n)}=2^n$，显然$2^{f(n)}\ne O(2^{g(n)})$

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

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

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

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

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

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

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

3-6 多重函数

摸了

最后

以上就是孤独蜡烛为你收集整理的《算法导论》练习与思考题第1-3章 (python版)第一章 算法在计算中的作用第二章 算法基础第三章 函数的增长的全部内容，希望文章能够帮你解决《算法导论》练习与思考题第1-3章 (python版)第一章 算法在计算中的作用第二章 算法基础第三章 函数的增长所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。