光阴冢

We make choices and life has a way of making us pay for them.

主方法

Aug 1, 2017   # Reading  # Algorithm 

主方法

主定理

设 $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 从第一个元素开始依次和之后的元素进行随机交换。