主方法

主定理

设 $a >= 1$ 和 $b > 1$ 为常数，设 $f(n)$ 为一函数，$T(n)$ 由递归式 $$T(n) = aT(\frac b n) + f(n)$$ 对非负整数定义。其中 $n/b$ 指 $\lfloor n/b \rfloor$ 或 $ \lceil n/b \rceil $。那么 $T(n)$ 可能有如下的渐近界：

1. 若对于某常数 $\epsilon > 0$，有 $ f(n) = O(n^{\log_b a} - \epsilon)$，则 $ T(n) = \Theta(n^{\log_b a})$；

2. 若 $f(n) = \Theta(n^{\log_b a})$，则 $T(n) = \Theta(n^{\log_b a} \lg n)$ ；

3. 若对某常数 $\epsilon > 0$，有 $f(n) = \Omega(n^{\log_b a} + \epsilon)$ ，且对常数 $c > 1$ 与所有足够大的 $n$ ，有 $af(n/b) <= cf(n)$ ，则 $T(n) = \Theta(f(n))$ 。

直觉理解

哪个大就决定于哪个。

概率分析和随机算法

指示器随机变量

感觉讲的很厉害，但是实际上好像是比较简单的概统思想。只是将一个事件期望解释成完备事件组的期望的和。应该像是全概率公式的推广吧。

随机算法

• 概率分析 如果我们说一个输入的分布是确定的，比如是完全随机的，这样我们会分析算法得到一个期望。这个时候，我们分析的算法本身是确定的。 对任何的确定的输入，给出的结果是确定的。

• 随机算法 我们在算法内部加入随机性。比如在输入之后对输入进行随机排序。 这样，对任何的确定的输入，给出的结果也是不定的的。

  • 随机化算法

    1. PERMUTE-BY-SORTING 对每个元素给定随机的优先级，按照优先级进行排序。

    2. RANDOMIZE-IN-PLACE 从第一个元素开始依次和之后的元素进行随机交换。