Analysis of Algorithms Week 1

最近开始学习Coursera上普林斯顿的算法分析课程，后续会记录下学习过程，这次是第一周的内容。

课程主页：https://www.coursera.org/learn/analysis-of-algorithms

Exercise

1.14

Follow through the steps given for quicksort to solve the recurrence:

$$A_{N}=1+\frac{2}{N} \sum_{1 \leq j \leq N} A_{j-1} \quad \text { for } \quad N>0$$

解：两边乘以$N$可得

$$\begin{aligned} N A_N &=N +2 \sum_{1 \leq j \leq N} A_{j-1}\\ (N-1) A_{N-1} & =N-1 +2 \sum_{1 \leq j \leq N -1} A_{j-1} \end{aligned}$$

相减可得

$$\begin{aligned} N A_N- (N-1) A_{N-1} &= 1 +2 A_{N-1}\\ NA_N -(N+1) A_{N-1} & =1 \end{aligned}$$

两边同除$N(N+1)$得到

$$\begin{aligned} \frac{A_N}{ N+1} - \frac{A_{N-1}}{N} &= \frac 1{N(N+1)}\\ \frac{A_N}{ N+1} - \frac{A_{N-1}}{N} &= \frac 1 {N} -\frac 1 {N+1}\\ \frac{A_N +1}{ N+1} &=\frac{A_{N-1} +1}{N} =\frac{A_0 +1}{1} \end{aligned}$$

所以

$$A_N = {(A_0 +1)(N+1)} -1$$

1.15

Show that the average number of exchanges used during the first partitioning stage (before the pointers cross) is $(N-2)/6$.

首先回顾源代码：

public class Quick
{
    private static int partition(Comparable[] a, int lo, int hi)
    {
        int i = lo, j = hi+1;
        while (true)
        {
            while (less(a[++i], a[lo])) if (i == hi) break;
            while (less(a[lo], a[--j])) if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
    	}
        exch(a, lo, j);
        return j;
    }
    private static void sort(Comparable[] a, int lo, int hi)
    {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }
}

题目的意思是计算exch(a, lo, j)之前的平均交换次数。

不妨设元素为$1,2,\ldots, N$，假设主元为$k$，那么交换次数为$a[1],\ldots , a[k-1]$中大于$k$的元素数量，考虑示性函数$X_i$，其中

$$X_i=\begin{cases} 1& a[i] > k\\ 0& a[i] < k \end{cases}$$

那么在主元为$k$的条件下，平均交换次数为

$$\begin{aligned} \sum_{i=1}^{k-1} \mathbb E[X_i] &= \sum_{i=1}^{k-1} \frac{N-k}{N -1}\\ &=\frac{(k-1)(N-k)}{N-1}\\ &=\frac{k(N+1)-N- k^2}{N-1} \end{aligned}$$

因为$k$可以可以等概率的取$1,2,\ldots, N$中任意的数，所以平均交换次数为

$$\begin{aligned} \frac 1 N\sum_{k=1}^{N} \frac{k(N+1)-N- k^2}{N-1} &=\frac 1 {N(N-1)} \left( (N+1) \frac {N(N+1)} 2 -N^2 -\frac{N(N+1)(2N+1)}{6}\right)\\ &=\frac 1 {N-1}\left( \frac{(N+1)^2}{2} -N-\frac{(N+1)(2N+1)}{6}\right)\\ &=\frac 1 {N-1} \frac{(N-1)(N-2)}{6}\\ &=\frac {N-2}{6} \end{aligned}$$

1.17

If we change the first line in the quicksort implementation given in the lecture to call insertion sort when the subfile size is not greater than $M$ then the total number of comparisons to sort $N$ elements is described by the recurrence

$$C_{N}=\left\{\begin{array}{ll}{N+1+\frac{1}{N} \sum_{1 \leq j \leq N}\left(C_{j-1}+C_{N-j}\right)} & {N>M} \\ {\frac{1}{4} N(N-1)} & {N \leq M}\end{array}\right.$$

Solve this recurrence.

对于$N > M$，递推式仍然为

$$\frac{C_{N}}{N+1}=\frac{C_{N-1}}{N}+\frac{2}{N+1}$$

递推可得

$$\begin{aligned} \frac{C_{N}}{N+1} &= \frac{C_M}{M+1} +\sum_{i=M+1}^N \frac 2 {i+1} \\ &=\frac{M(M-1)}{4(M+1)} +\sum_{i=M+2}^{N+1} \frac 2 {i} \end{aligned}$$

所以对于$N > M$

$$C_N = (N+1) \left(\frac{M(M-1)}{4(M+1)} +\sum_{i=M+2}^{N+1} \frac 2 {i}\right)$$

1.18

$$\begin{aligned} C_N &=(N+1) \left(\frac{M(M-1)}{4(M+1)} +\sum_{i=M+2}^{N+1} \frac 2 {i}\right)\\ &=(N+1)\frac{M(M-1)}{4(M+1)} +2 (N+1) \left( \ln (N+1)+\gamma -\sum_{i=1}^{M+1} \frac 1 i \right)\\ &\approx 2N \ln N +\left(\frac{M(M-1)}{4(M+1)} -2\sum_{i=1}^{M+1} \frac 1 i +2\gamma \right) N \end{aligned}$$

所以

$$f(M) =\frac{M(M-1)}{4(M+1)} -2\sum_{i=1}^{M+1} \frac 1 i +2\gamma$$

不考虑常数项，作图可得

当M= 8 时取最小值

代码如下：

import numpy as np
import matplotlib.pyplot as plt

M = np.arange(1, 100)
d1 = M * (M - 1) / (4 * (M + 1))
d2 = 2 * np.cumsum(1 / M)
f = d1 - d2

plt.plot(M, f)
plt.show()

print("当M=", M[np.argmin(f)], "时取最小值")

Problem

1

$$\begin{aligned} F_{N} &=N^{2}+1+\frac{1}{N} \sum_{1 \leq k \leq N}\left(F_{k-1}+F_{N-k}\right)\\ F_{N}&=N^{2}+1+\frac{2}{N}\sum_{1 \leq k \leq N}F_{k-1}\\ NF_N &= N^3 +N + 2\sum_{1 \leq k \leq N}F_{k-1}\\ (N-1)F_{N-1}&= (N-1)^3 +N-1+ 2\sum_{1 \leq k \leq N-1}F_{k-1} \end{aligned}$$

相减可得

$$\begin{aligned} NF_N -(N-1)F_{N-1} &=3N^2 -3N+1 +1+2F_{N-1}\\ NF_N &= (N+1)F_{N-1}+ 3N^2 -3N +2\\ \frac{F_N}{N+1}&=\frac{F_{N-1}}{N}+\frac{3N^2 -3N +2}{N(N+1)}\\ \frac{F_N}{N+1}&=\frac{F_{N-1}}{N}+ 3 \frac{N-1}{N+1} +2\left(\frac 1 N - \frac 1 {N+1}\right)\\ \frac{F_N}{N+1}&=\frac{F_{N-1}}{N}+3 \left(1-\frac 2 {N+1}\right)+2\left(\frac 1 N - \frac 1 {N+1}\right) \end{aligned}$$

累加可得

$$\begin{aligned} \frac{F_N}{N+1}&= \frac{F_0}{ 1} +3\sum_{i=1}^N \left(1-\frac 2 {i+1}\right) +2\sum_{i=1}^N\left(\frac 1 i- \frac 1 {i+1}\right)\\ \frac{F_N}{N+1}&= 3N -6\sum_{i=1}^N\frac 1 {i+1} +2 \left(1- \frac 1 {N+1}\right)\\ F_N &=3N(N+1) -6(N+1)\sum_{i=1}^N\frac 1 {i+1} +2N \end{aligned}$$

2

Which of the following is a drawback to analyzing algorithms by proving O- upper bounds on the worst case?

• Generally cannot be used to predict performance.
• Likely to be too much detail in the analysis.
• Generally cannot be used to compare algorithms.
• Input model may be unrealistic.

显然答案如下：

Generally cannot be used to predict performance.

Generally cannot be used to compare algorithms.