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

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

选择题

选择题 1

令 $0<α<0.5 $是一个常数（与输入数组长度$n$无关）。回想一下QuickSort算法采用的Partition子程序，如讲座中所述。通过随机选择的pivot，Partition分割的两个子列中较小者的长度 $≥α$ 倍于原始数组的长度的概率？

• $ 1 - 2\alpha$
• $ \alpha$
• $1-\alpha$
• $2-2\alpha$

可以画个图，要使得这个事件发生，那么$\text{pivot}\in [\alpha n, (1-\alpha)n]$，所以该事件发生的概率为

$$\frac 1 n (1-2\alpha) n = 1-2\alpha$$

选择题 2

现在假设您在每次递归调用中都实现了上面的近似平衡拆分 - 也就是说，假设当递归调用给出一个长度为$k$的数组，那么Partition后子数组的长度都介于 $\alpha k$ 和$(1-\alpha)k$之间（其中$\alpha$是一个位于$0$到$0.5$之间的常数。在遇到base case之前会发生多少次递归调用？等价地，哪层的递归树包含叶子？用$d$的范围来表达你的结果。

• $-\frac{\log(n)}{\log(1-2*\alpha)} \le d \le -\frac{\log(n)}{\log(1-\alpha)}$
• $0 \le d \le -\frac{\log(n)}{\log(\alpha)} $
• $-\frac{\log(n)}{\log(1-\alpha)} \le d \le -\frac{\log(n)}{\log(\alpha)} $
• $-\frac{\log(n)}{\log(\alpha)} \le d \le -\frac{\log(n)}{\log(1-\alpha)} $

选项中$n$为数组长度，假设经过$d$轮之后遇到base case，因为每次Partition后子数组的长度都介于 $\alpha n$ 和$(1-\alpha)n$之间，所以$d$轮后子数组的长度$l$满足

$$\alpha ^d n \le l \le (1-\alpha)^d n$$

令$l=1$，那么

$$\begin{aligned} \alpha ^d n &\le 1\\ d\log \alpha + \log n &\le 0\\ d&\ge -\frac{\log(n)}{\log(\alpha)} \\ 1& \le (1-\alpha)^d n \\ 0&\le d\log(1-\alpha) + \log n \\ d &\le -\frac{\log(n)}{\log(1-\alpha)} \end{aligned}$$

所以

$$-\frac{\log(n)}{\log(\alpha)} \le d \le -\frac{\log(n)}{\log(1-\alpha)}$$

选择题 3

将QuickSort的递归深度定义为在它到达基本情况之前的连续递归调用的最大数量 —— 等价地，相应的递归树的最后一级的数量。请注意，递归深度是一个随机变量，它取决于选择哪个pivot。QuickSort的最小可能和最大可能的递归深度分别是多少？

• $\text{Minimum: }\Theta (\log n );\text{Maximum: }\Theta (n )$
• $\text{Minimum: }\Theta (\log n );\text{Maximum: }\Theta (n \log n)$
• $\text{Minimum: }\Theta (1 );\text{Maximum: }\Theta (n)$
• $\text{Minimum: }\Theta (\sqrt n );\text{Maximum: }\Theta (n)$

由QuickSort的操作可知，每次至少能把pivot安排在正确的位置上，所以最大的操作数量为$\Theta (n )$；如果pivot每次都取的是中位数，那么QuickSort变为MergeSort，操作数量为$\Theta (\log n )$，显然最小操作数量不可能是$\Theta (1 )$，所以这题的答案为第一项。

选择题 4

考虑$k$个人。每个人的生日均匀分布在$365$天中（忽略闰年）。使得生日相同的组量的数学期望大于等于$1$的最小的$k$是多少？

[提示：为每个人定义一个示性随机变量。 使用数学期望的线性性。]

• $23$
• $27$
• $20$
• $366$
• $28$

取一个随机变量$x_{ij}$，当第$i,j$个人生日在同一天时为$1$，否则为$0$。我们计算$\mathbb P[x_{ij}=1]$，显然有

$$\mathbb P[x_{ij}=1] = \frac 1 {365}$$

所以，生日相同的组数的数学期望为

$$\begin{aligned} \sum_{i=1}^{k-1}\sum_{j=i+1}^k \mathbb E[x_{ij}=1] &= \sum_{i=1}^{k-1}\sum_{j=i+1}^k\mathbb P[x_{ij}=1]\\ &=\sum_{i=1}^{k-1}\sum_{j=i+1}^k \frac 1 {365}\\ &=\frac{k^2 -k }{730} \end{aligned}$$

解$\frac{k^2 -k }{730}\ge 1$可得$k=28$为最小值。

选择题 5

令$X_1,X_2,X_3$为三个六面骰子的结果，令$Y = X_1 X_2,Z=X_2 X_3$，以下哪个陈述是正确的？

• $Y,Z$独立，$\mathbb E[YZ] \neq\mathbb E[Y]\mathbb E [Z]$
• $Y,Z$不独立，$\mathbb E[YZ] = \mathbb E[Y]\mathbb E[Z]$
• $Y,Z$不独立，$\mathbb E[YZ] \neq\mathbb E[Y]\mathbb E[Z]$
• $Y,Z$独立，$\mathbb E[YZ] =\mathbb E[Y]\mathbb E[Z]$

显然$Y,Z$不独立，我们来计算$\mathbb E[YZ] ,\mathbb E[Y]\mathbb E[Z]$

$$\begin{aligned} \mathbb E[YZ]&=\mathbb E[X_1 X_2^2 X_3] =\mathbb E[X_1]^2\mathbb E[X_1^2]\\ \mathbb E[Y]\mathbb E[Z]& = \mathbb E[X_1 X_2]\mathbb E[X_2 X_3] =\mathbb E[X_1]^4\\ \end{aligned}$$

因为

$$\mathbb E[X_1^2] \ne\mathbb E[X_1] ^2$$

所以

$$\begin{aligned} \mathbb E[X_1]^2\mathbb E[X_1^2] &\neq\mathbb E[X_1]^4\\ \mathbb E[YZ]&\neq\mathbb E[Y]\mathbb E[Z] \end{aligned}$$

所以这题第三个选项正确。

编程题

实现课件中的快速排序算法，计算比较的次数：

with open('data.txt') as a:
    b = []
    for i in a.readlines():
        b.append(int(i.strip()))
    
def Median(a,b,c):
    if a < b:
        if b < c:
            return b, 2
        else:
            if a > c:
                return a, 1
            else:
                return c, 3
    else:
        if c > a:
            return a, 1
        else:
            if c > b:
                return c, 3
            else:
                return b, 2
            
def Exchange(A, i, j):
    #交换元素的值
    p = A[i]
    A[i] = A[j]
    A[j] = p
        
def Quicksort(A, l, r, flag):
    if l >= r:
        return 0
    else:
        if flag == 1:
            p = A[l]
        elif flag == 2:
            #交换A[l],A[r]
            Exchange(A, l, r)
            p = A[l]
        else:
            u = A[l]
            v = A[(l + r) // 2]
            w = A[r]
            #计算中位数以及对应的位置
            m, n = Median(u, v, w)
            if n==1:
                pass
            elif n==2:
                Exchange(A, l, (l+r) // 2)
            else:
                Exchange(A, l, r)
            p = A[l]
        i = l + 1
        for j in range(l+1, r+1):
            if A[j] < p:
                #交换A[i]和A[j]
                Exchange(A, i, j)
                i += 1
        #交换A[l]和A[i-1]
        Exchange(A, l, i-1)
        #注意pivot在i-1的位置
        return Quicksort(A, l, i-2, flag) + Quicksort(A, i, r, flag) + r - l

#b= [3, 4, 1, 2]
for i in range(1, 4):
    with open('data.txt') as a:
        b = []
        for j in a.readlines():
            b.append(int(j.strip()))
    n = len(b)
    print(Quicksort(b, 0, n-1, i))

162085
164123
138382