斯坦福算法专项课程Course1 week2习题解析

这一部分将带来Course1 week2的习题解析。

选择题

选择题1

$T(n) = 7T(n/3) + n^2$，那么$T(n)$的近似时间为

• $\theta(n^2)$
• $\theta(n^2\log n)$
• $\theta(n^{2.81})$
• $\theta(n \log n)$

应用主定理，$a= 7,b=3, d=2$，$a=7<9 = b^d$，所以时间复杂度为

$$\theta (n^d) = \theta(n^2)$$

选择题2

$T(n) = 9T(n/3) + n^2$，那么$T(n)$的近似时间为

• $\theta(n^{2})$
• $\theta(n \log n)$
• $\theta(n^{3.17})$
• $\theta(n^2 \log n)$

应用主定理，$a= 9,b=3, d=2$，$a=9 = b^d$，所以时间复杂度为

$$\theta(n^d \log n) = \theta(n^2 \log n)$$

选择题3

$T(n) = 5T(n/3) + 4n$，那么$T(n)$的近似时间为

• $\theta(n^{\log_3 5})$
• $\theta(n^{2.59})$
• $\theta(n^{\frac{\log 3}{\log5}})$
• $\theta(n^{2})$
• $\theta(n \log n)$

应用主定理，$a= 5,b=3, d=1$，$a=5>3 = b^d$，所以时间复杂度为

$$\theta (n^{\log_b a}) = \theta(n^{\log_3 5})$$

选择题4

考虑如下计算$a^b$的伪代码

FastPower(a,b) :
  if b = 1
    return a
  else
    c := a*a
    ans := FastPower(c,[b/2])
  if b is odd
    return a*ans
  else return ans
end

这里$[x]$表示向下取整函数，即小于等于$x$的最大整数。

现在假设您使用支持乘法和除法的计算器（即，您可以在恒定时间内进行乘法和除法），上述算法的整体渐近运行时间（作为b的函数）是什么？

• $\theta(b\log b)$
• $\theta(b)$
• $\theta(\sqrt b)$
• $\theta(\log b)$

设运行时间为$T(b)$，根据算法，有以下递推式

$$T(b) = T\left(\frac b 2 \right) +\theta(1)$$

利用主定理，可得

$$T(b) =\log b$$

选择题5

选择下述问题的最小上界：$T(1)=1,T(n)\le T([\sqrt n]) +1$，这里$[x]$表示向下取整函数，即小于等于$x$的最大整数。注意主定理无法使用。

• $O(\log\log n)$
• $O(\sqrt n)$
• $O(\log n)$
• $O(1)$

假设$2 ^{s-1} \le n < 2 ^s$，那么

$$\begin{aligned} T(n) &\ge T(2^{s-1}) = g(s-1)\\ T([\sqrt n]) +1 &\le T([2^{\frac s 2}] ) +1 \le T(2^{\frac s 2} ) +1=g\left(\frac s 2 \right)+1\\ g(s-1) &\le g\left(\frac s 2 \right) +1 \end{aligned}$$

那么问题可以改写为

$$g(s-1) \le g\left(\frac s 2 \right) +\theta(1)$$

对这个递推式利用主定理

$$a= 1,b=2, d=0\\ a = b^d=1\\ T(n)=g(s) =O(\log s)$$

因为$2 ^{s-1} \le n < 2 ^s$，所以

$$\begin{aligned} s-1&\le \log_2n <s\\ \log_2n& <s \le \log_2 n+1\\ s &= \theta(\log n) \end{aligned}$$

带入上式可得

$$T(n) =O(\log \log n)$$

编程题

实现这周介绍的逆序数计算方法：

def merge_sort(x):
	a = len(x)
	b = []
	if a == 1:
		return 0, x
	else:
        #前一半数量
		c = a // 2
        #后一半数量
		d = a - c
		u0, u = merge_sort(x[:c])
		v0, v = merge_sort(x[c:])
        #记录u的下标
		i = 0
        #记录v的下标
		j = 0
        #记录循环次数
		k = 1
        #记录跨组逆序的个数
		s = 0
        #merge
		while k <= a:
			if i <= c-1 and j <= d-1:
				if u[i] <= v[j]:
					b.append(u[i])
					i += 1
					k += 1
				else:
					b.append(v[j])
					j += 1
					k += 1
                    #累加放入第二个数列元素时第一个数列还剩余的元素个数
					s += c - i
			elif i == c:
				b.append(v[j])
				j += 1
				k += 1
			elif j == d:
				b.append(u[i])
				i += 1
				k += 1
		return s, b		
    
def f(x):
	a = len(x)
	if a == 1:
		return 0
	else:
		b = a // 2
		c = x[:b]
		d = x[b:]
		e, g = merge_sort(x)
		return f(c) + f(d) + e

with open(r'IntegerArray.txt') as a:
    b = []
    for i in a.readlines():
        b.append(int(i.strip()))
    print(f(b))

2407905288

思考题

思考题1

现在有$n$个元素且大小不相同的无序数组，$n$为$2$的幂，给出一个最多用$n+\log_2n-2$次比较的算法来找出第二大的元素。

设$n = 2^s$

利用淘汰赛赛制的方法，先找出最大的元素，再在和最大元素“交手”过的元素中找到最大的元素，这个元素就是第二大的元素，下面具体说明一下。

将数组中元素两两一组进行比较，大的元素获胜，进行下一轮比较，持续这个操作，最后会剩下一个元素，这个元素就是最大值，这个过程可以用以下树状图来说明。下面借助树状图来说明一下这个结论为什么是正确的：

首先由比赛的规则我们知道，每个节点都大于等于其子节点，由这个性质，最后剩下的这个元素必然大于等于全部的元素，从而为最大值。

现在说明了这个结论的正确性，我们来计算一共需要几步。对于$2^k$个元素，需要$2^k/2=2^{k-1}$次比较来进行一轮淘汰赛，所以对于$n=2^k$，完成全部淘汰赛一共需要的比较为

$$\sum_{i=0}^{k-1} 2^i = 2^k-1=n-1$$

现在考虑和最大元素交手过的$k$个元素，下面说明，这个$k$个元素中的最大元素即为全部元素中第二大的元素。

还是借助上述树状图，和最大元素交手的元素必然大于等于其左子树以及右子树的全部元素，而我们的目标是找到除了最大元素以外的最大元素，所以只要考虑这些和最大元素交过手的元素即可。

所以现在只要找到$k$个元素的最大值即可，这个只要进行$k-1$次比较即可，所以总共的次数为

$$n-1+k-1= n+\log_2 n -2$$

思考题2

给定一个由$n$个不同元素组成的单峰数组，这意味着它的元素按递增顺序排列直到其最大元素，之后其元素按递减顺序排列。给出一个算法在$O(\log n)$时间内找到最大元素。

这个问题关键在于找到波峰在哪，可以结合二次函数的图像来考虑，假设数组的元素为$a_1,…,a_n$，将数组分为三个部分：

$$第一部分：a_1,...,a_{[\frac n 3]}，第二部分：a_{[\frac {n} 3]},...,a_{[\frac {2n} 3]}，第三部分：a_{[\frac {2n} 3]},...,a_n$$

波峰或者在$[0:[\frac{2n}{3}]]$，或者在$[[\frac{n}{3}]:n ]$，判断规则如下：

如果$a\le {[\frac n 3]}\le a_{[\frac {2n} 3]}\le a_{n}$，那么对$a[[\frac{n}{3}]:n ]$递归计算；否则对$a[:[\frac{2n}{3}]]$递归计算。

算法的递推式为

$$T(n) \le T(\frac {2n} 3) +O(1)$$

利用主定理，这个算法的时间复杂度为

$$O(\log n)$$

思考题3

现在有一个从最小到最大排好序的$n$个不同整数的数组$A$，它们可以是正数，负数或零。现在要判断是否存在索引$i$，使得$A [i] = i$。 设计最快的算法来解决这个问题。

我们考虑$A[[\frac n 2]]$这个元素：

• 如果$A[[\frac n 2]]=[\frac n 2]$，那么直接返回结果True；
• 如果$A[[\frac n 2]]>[\frac n 2]$，那么由$A$为整数数组可知，任取$k\in N$，$A[[\frac n 2]+k]\ge A[[\frac n 2]]+k>[\frac n 2]+k$，这说明$A[[\frac n 2]+1],…,A[n]$这些元素都不可能满足$A[i]=i$，所以只要递归地考虑$A[1],…, A[[\frac n 2]-1]$这些元素即可。
• 如果$A[[\frac n 2]]<[\frac n 2]$，那么由$A$为整数数组可知，任取$k\in N$，$A[[\frac n 2]-k]\le A[[\frac n 2]]-k<[\frac n 2]-k$，这说明$A[1],…,A[[\frac n 2]-1]$这些元素都不可能满足$A[i]=i$，所以只要递归地考虑$A[[\frac n 2]+1],…,A[n ]$这些元素即可。

由上述叙述知，这个算法的时间复杂度满足以下递推式

$$T(n)\le T(\frac n 2) +O(1)$$

由主定理可知，时间复杂度为

$$T(n) =\log n$$

思考题4

给你一个$n\times n$个不同数字的网格。 如果数字小于其所有邻居，则该数字是局部最小值。 （一个数字的邻居是上方，下方，左侧或右侧的一个。大多数数字有四个邻居;侧面的数字有三个;四个角有两个。）使用分而治之的算法计算局部最小值，仅对数字对进行$O(n)$次比较。（注意：因为有$n ^ 2$个元素，所以不能查看全部元素。 提示：考虑哪种类型的递归会给你所需的上限。）

结合下图进行说明

以左下角为原点，右手方向为$x$轴，竖直方向由$y$轴，那么直线$x=[\frac n 2]$以及直线$y=[\frac n 2]$将格子分为四个部分，按上图分别记为$A_1,A_2,A_3,A_4$。

我们考虑位于直线$x=0,x=[\frac n 2],x=n,y=0,y=[\frac n 2],y = n$这$6$条直线上的点，设这些点中的最小值为$a$，考虑以下几种情形：

情形1：$a\in A_i,a \notin A_j$，这种情形表示$a$不属于交界处，此时对$A_i$递归地调用该算法。（对应上图$1,2,4$）

情形2：$a\in A_i \cap A_j \cap A_k$，这种情形表示$a$属于三个区域交界处，由定义，此时$a$即为局部最小值。（对应上图$9$）

情形3：$a\in A_i \cap A_j,a\notin A_k$，这种情形表示$a$属于两个区域的交界处，但不属于三个区域的交界处，此时将$a$和其上下或者左右两个未比较过的点$b,c$进行比较，如果$a<b,a<c$，那么$a$为局部最小值，否则对最小值所在区域递归地调用该算法（对应上图$3,6,7,8$）

计算这$6$条直线上的点需要$O(n)$的时间，而每次递归，问题的规模缩小一半，所以有以下递推式

$$T(n) = T(\frac n 2 )+O(n)$$

由主定理，$a=1,b=2,d=1$，时间复杂度为

$$O(n)$$