Analysis of Algorithms Week 1

距离上次更新已经 2037 天了，文章内容可能已经过时。

最近开始学习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\le j\le N}{A}_{j-1}\text{ for }N>0$$

解：两边乘以$N$可得

$$\begin{array}{rl}N{A}_N& =N+2\sum _{1\le j\le N}{A}_{j-1}\\ (N-1)A_{N-1}& =N-1+2\sum _{1\le j\le N-1}{A}_{j-1}\end{array}$$

相减可得

$$\begin{array}{rl}N{A}_N-(N-1)A_{N-1}& =1+2A_{N-1}\\ N{A}_N-(N+1)A_{N-1}& =1\end{array}$$

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

$$\begin{array}{rl}\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{array}$$

所以

$$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,\dots ,N$，假设主元为$k$，那么交换次数为$a[1],\dots ,a[k-1]$中大于$k$的元素数量，考虑示性函数$X_i$，其中

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

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

$$\begin{array}{rl}\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{array}$$

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

$$\begin{array}{rl}\frac{1}{N}\sum _{k=1}^N\frac{k(N+1)-N-k^2}{N-1}& =\frac{1}{N(N-1)}((N+1)\frac{N(N+1)}{2}-N^2-\frac{N(N+1)(2N+1)}{6})\\ & =\frac{1}{N-1}(\frac{(N+1{)}^2}{2}-N-\frac{(N+1)(2N+1)}{6})\\ & =\frac{1}{N-1}\frac{(N-1)(N-2)}{6}\\ & =\frac{N-2}{6}\end{array}$$

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=\{\begin{array}{ll}N+1+\frac{1}{N}\sum _{1\le j\le N}(C_{j-1}+C_{N-j})& N>M\\ \frac{1}{4}N(N-1)& N\le M\end{array}$$

Solve this recurrence.

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

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

递推可得

$$\begin{array}{rl}\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{array}$$

所以对于$N>M$

$$C_N=(N+1)(\frac{M(M-1)}{4(M+1)}+\sum _{i=M+2}^{N+1}\frac{2}{i})$$

1.18

$$\begin{array}{rl}{C}_N& =(N+1)(\frac{M(M-1)}{4(M+1)}+\sum _{i=M+2}^{N+1}\frac{2}{i})\\ & =(N+1)\frac{M(M-1)}{4(M+1)}+2(N+1)(\ln (N+1)+\gamma -\sum _{i=1}^{M+1}\frac{1}{i})\\ & \approx 2N\ln N+(\frac{M(M-1)}{4(M+1)}-2\sum _{i=1}^{M+1}\frac{1}{i}+2\gamma )N\end{array}$$

所以

$$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{array}{rl}{F}_N& =N^2+1+\frac{1}{N}\sum _{1\le k\le N}(F_{k-1}+F_{N-k})\\ F_N& =N^2+1+\frac{2}{N}\sum _{1\le k\le N}{F}_{k-1}\\ N{F}_N& =N^3+N+2\sum _{1\le k\le N}{F}_{k-1}\\ (N-1)F_{N-1}& =(N-1{)}^3+N-1+2\sum _{1\le k\le N-1}{F}_{k-1}\end{array}$$

相减可得

$$\begin{array}{rl}N{F}_N-(N-1)F_{N-1}& =3N^2-3N+1+1+2F_{N-1}\\ N{F}_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(\frac{1}{N}-\frac{1}{N+1})\\ \frac{F_N}{N+1}& =\frac{F_{N-1}}{N}+3(1-\frac{2}{N+1})+2(\frac{1}{N}-\frac{1}{N+1})\end{array}$$

累加可得

$$\begin{array}{rl}\frac{F_N}{N+1}& =\frac{F_0}{1}+3\sum _{i=1}^N(1-\frac{2}{i+1})+2\sum _{i=1}^N(\frac{1}{i}-\frac{1}{i+1})\\ \frac{F_N}{N+1}& =3N-6\sum _{i=1}^N\frac{1}{i+1}+2(1-\frac{1}{N+1})\\ F_N& =3N(N+1)-6(N+1)\sum _{i=1}^N\frac{1}{i+1}+2N\end{array}$$

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.