正如上一篇所说，我这几天都在学习《算法导论》这本书， 也终于是下定决心要好好把这本书看出个所以然来。 这几天看下来，发现最大的困扰并不是知识的难度， 而是克服自己内心的浮躁。因为这本书并不像其他的工科教材， 它讲得东西是比较偏理论一些，里面充满了各种数学公式，数学定理, 包括一个算法正确性的证明，都采取了形式化的证明手段， 力求证明的数学严格性。 如果只是需要粗粗理解各种算法是什么样的以及如何实现的话， 那么看这本书有点不太合适， 因为这方面的东西并不是这本书的重点。

而我，也是在粗粗了解了各种算法和实现的基础上学习这本书的， 一开始扫了一下书的第一章，第二章和第六章， 发现和其他的算法书还差不多嘛， 直到看到第七章快速排序， 看到作者在大概描述完快速排序算法之后 （这个快速排序的划分函数还和我以前见过的都不一样，更加容易理解和实现）， 转而开始分析快速排序的性能和随机化版本，我才明白， 我不能再这么浮躁地只是抱着了解了解算法的目的来学习这本书了。 于是我又回过去仔仔细细地从头看到了第7章， 虽然说这本书里的定理和数学公式很多，但是并不难理解， 因为作者总是把每一个步骤解释地十分细致和透彻， 每一步的证明没有很大的跨越， 每一个结论的得出都会指明依据的定理或者是前面的结论。 所以说好好看下去其实并没有很大难度， 关键是要能够静得下心。

下面是1～7章中我的几点体会：

循环不变式

循环不变式用于证明算法的正确性， 它能够保证一个算法能够终止， 而且当它终止时，得到的结果是正确的结果。 循环不变式的证明由三个部分组成：

• 初始化: 在循环的开始时，循环不变式成立。
• 保持：如果在某一轮迭代之前循环不变式成立，那么在迭代之后， 循环不变式仍然成立。
• 终止：如果保持循环不变式一直到循环的终止，那么这个算法将得到正确的结果。

循环不变式与数学归纳法十分类似，采用的也是同样的思想。 在应用循环不变式对算法的正确性进行证明时， 难点不在于上述的三个步骤，而在于循环不变式的构造， 要构造一个循环不变式能够在循环过程中始终保持， 而且能体现算法正确性，这确实需要一定的技巧。 这就类似于在应用数学归纳法时选取归纳条件。

比如书中思考题2-2：（证明冒泡排序的正确性）

for i <- 1 to length[A]
    do for j <- length[A] downto i+1
        do if A[j] < A[j-1]
            then exchange A[j] <-> A[j-1]

b)对于2-4行(内层循环)给出一个循环不变式，并证明这个循环不变式是成立的。

内层循环的作用是把A[i]到A[n]（n是length[A]）中最小元素放到A[i], 可以采用如下的循环不变式来表示：

在每一轮迭代的开始，子数组A[j..n]中最小的元素位于A[j]。

下面对这个循环不变式进行证明：

• 初始化： 在第一轮迭代开始前，j = n，A[j..n]中就只有一个元素， 最小的元素位于A[n]。
• 保持：在第k轮迭代时，
  • 如果A[j] >= A[j-1]，由循环不变式可知， A[j]是字数组A[j..n]中最小的元素，那么循环结束时A[j-1]将是字数组A[j-1..n]中的最小元素。
  • 如果A[j] < A[j-1], 那么在互换A[j]和A[j-1]之后，最小的元素仍然是A[j-1]。
• 终止: 在循环结束时j=i, 说明A[i]是字数组A[i..n]中的最小元素， 算法达到了把最小元素放到A[i]的目的。

渐进符号

渐进符号用户描述一个算法的复杂度，以前只知道 渐进符号用于描述算法的量级，比如$2n^2 = O(n^2)$ 说明 $2n^2$ 的量级是 $O(n^2)$。

书上给出了准确的定义:

$$O(g(n)) = \{f(n): \exists c,n， \forall n \geq n_0, 0 \leq f(n) \leq cg(n)\}$$

同时有：

$$f(n) = O(g(n)) \Longleftrightarrow f(n) \in O(g(n))$$

其他的符号如$\Omega$, $\Theta$都是类似的定义。 当然，我们只需要知道用$O(f(n))$来确定一个函数的上界， 用$\Omega(f(n))$来确定一个函数的下界就可以了。

递归与主定理

分治法是一种很常见的算法设计方法， 分治法的时间复杂度一般由如下的递归式给出：

$$T(n) = aT(n/b) + f(n)$$

其中$a \geq 1, b > 1$，f(n)一般用渐进函数表示。

对于这样的递归式，主定理给出了计算T(n)的方法：

• 如果存在常数$\epsilon > 0$，有 $f(n) = O(n^{\log_ba - \epsilon})$， 则 $T(n) = \Theta(n^{\log_ba})$;
• 如果 $f(n) = \Theta(n^{\log_ba})$， 则 $T(n) = \Theta(n^{\log_ba}\lg n)$;
• 如果存在常数$\epsilon > 0$，有 $f(n) = \Omega(n^{\log_ba + \epsilon})$， 且对常数$c < 1$与足够大的n,有 $af(n/b) \leq cf(n)$，则 $T(n) = \Theta(f(n))$。

运用主定理，能够很快地求出分治算法的复杂度。

指示器随机变量

指示器随机变量的定义如下:

$$X_H = I\{H\} = \begin{cases} 1 & \text{如果H发生} \\ 0 & \text{如果H没有发生} \end{cases}$$

指示器随机变量是随机变量的一种，可以求出它的期望如下： $$ E[X_H] = Pr_H $$

指示器随机变量有一个很好的性质，它只能取0或者1， 可以把它这些变量加起来求总的发生次数, 因此当它应用到重复随机试验中时, 统计重复试验某一事件发生次数的期望， 比如在随机化的快速排序中统计交换次数的期望, 可以通过如下公式得到：

$$E[X] = E[\sum_{i=1}^n X_i] = \sum_{i=1}^n E[X_i]$$

要使等式的第二步成立，不一定要保证$X_i$之间是相互独立的。

这周的读书笔记就先写到这里，下周开始写第8章开始的内容。