一直想过一遍算法导论，查缺补漏，终于找到时间开始。算法导论原书有一千多页，熟悉的部分必须要略读。本文为略读第一部分的笔记。
算法正确性证明 Loop Invariants
实际使用中很少显式证明算法的正确性，需要进行证明时可以借助 Loop Invariants. 算法执行过程中通常会有一些循环，Loop Invariants 也即分析循环执行过程中有什么事实始终保持不变或者规模逐渐扩大。比如书中例子 (2.1 insertion sort) 插入排序执行过程中，随着循环的执行，原数组头部有序部分逐渐扩大。具体的，有序部分在循环执行前有序，循环执行后规模扩大，保持有序。
Randomized Algorithm
一般而言，我们提到「算法时间复杂度」时是指算法的最坏时间复杂度。这是因为实际应用中最坏情况常常会真实出现，或者需要保证最坏情况下算法也能有效运行。而在算法竞赛等情况下，数据机通常会尽可能给出导致算法最坏性能的数据。但有一个明显的例外：我们熟知的快排最坏时间复杂度是 $O(n^2)$, 平均时间复杂度是 $O(n \log n)$, 但我们提到快排时通常认为其时间复杂度是其平均时间复杂度 $O(n \log n)$.
在本书 5.3 节我们能够得到该问题的答案：快排是 Randomized Algorithm 的一个例子，这类算法的执行不仅依赖于输入，还依赖于随机数发生器。由于依赖随机数发生器，这类算法每次执行的具体行为（速度等）可能发生变化。快排某种意义上类似于借助随机数发生器随机打乱输入（实际的快排不是这样实现的，但与随机打乱有些相似），从而保证算法的输入是「随机」的。算法的最坏情况即使发生，也并不取决于输入，而是随机数发生器给出了一个「不幸」的随机数序列。
于是，并没有办法给出一个输入数据使得这类算法总是得到最坏时间复杂度（这类算法每次执行的性能可能是不同的）。实际使用中，快排并不会像插入排序一样在一些常见的输入（倒序输入）上出现最差性能，想要令一个实际的快排算法出现最差性能是非常困难的，在算法竞赛中也没有办法给这类算法一个对抗性数据集。所以这类算法的时间复杂度可以按照平均时间复杂度而非最坏时间复杂度计算。
散列算法（哈希算法）与此类似，尽管散列算法并不符合 Randomized Algorithm 的定义，但只要散列函数性能足够好，也能起到类似的效果，所以我们对于散列算法一般也会关心其平均时间复杂度。
分治算法的时间复杂度分析
读到分治算法一节的时间复杂度分析时有种奇妙的陌生感：分治算法很熟悉，时间复杂度分析很熟悉，但分治算法的时间复杂度分析不熟悉，这是为什么？
仔细回忆一下，算法竞赛中碰到的分治算法的时间复杂度似乎都是 $O(n log n)$, 或者作为 DP 算法推导过程的一部分使用。可以将分治算法视为 DP 的一个特例，其状态图是一棵树，不会重复计算，因此不需要保存计算结果。但其时间复杂度可以像 DP 算法一样根据状态空间大小和每个状态的计算成本进行估算，也即书中的 Recursion-Tree Method.
这类算法本身就比较少见，而且算法竞赛中时间复杂度不需要估算的非常精确，如果发现是分治算法，估计为「几乎跟最大规模的一次运行一样快，只差一个 $\log$ 项」就足够了。