算法导论(Analysis of Algorithms)

相关链接

1 概述

简述

算法分析

算法分析是关于计算机程序性能和资源利用的研究，主要关注性能(How to make things fast)。

  • 在程序设计领域，有什么比性能更重要？

正确性 功能性 模块化 安全性 用户友好

  • 为什么研究算法和性能？

例如：性能经常决定是否可用，

预备课程

  • 计算机科学与数学基础
  • 离散数学
  • 概率论

算法复杂度

时间复杂度

在计算机科学中， 算法的时间复杂度是一个函数。用以定量的描述算法的运行时间。用大 O 符号表示，不包括这个函数的低阶项和首项系数，时间复杂度可被称为是渐近的。因为其考察的是当输入值大小趋近无穷时的情况。如：5n^3 + 3n 的时间复杂度，所以其渐近时间复杂度为 O(n^3)

空间复杂度

2 排序

问题 a.

Input sequence <a1, a2, …, an> of number

Output permutation <a1’, a2’, …, an’>

$ a1’ <= a2’ <= … <= an’

2.1 插入排序(Insertion Sort)

代码和执行顺序

python
Insrertion.Sort(A, n) // Sorts A[1...n]
	for j <- 2 to n
		do key <- A[j]
		i <- j - 1
		while i > 0 and A[i]] > key
			do A[i+1] <- A[i]
				i <- i - 1
	    A[i+1] <- key

粗体表示要插入的数，^表示要插件的位置

^ 8 2 4 9 3 6
2 ^ 8 4 9 3 6
2 ^ 4 8 9 3 6
2 3 4 ^ 8 9 6
2 3 4 6 8 9

运行时间

运算时间取决于:

  • 输入参数(eg, 已被 sort， 最坏是被逆序 sort)
  • 输入数组的长度
    • 输入规模参数化
  • 通常想知道运时时间的上界
    • 对用户的保证

分析算法的方法

  • 最坏情况分析
    T(n) = max time on any input of size in.

  • 平均情况分析
    T(n) = The expected time over all inputs of size n, 各种 n 输入的期望情况。
    (需要有关输入统计分布的统计假设，比如均匀分布，所有可能的概率相同，取加权的平均值)

    weighted average - 加权平均

    uniform distribution - 均匀分布

  • 最好情况分析(bogus)

插入排序的最坏时间

  • 计算机性能
    • 相对速度(一般比较相同性能，或同一台计算机上)
    • 绝对速度(在任何不同的计算机上）

渐进分析法(Asymptotic analysis)：

  1. 忽略依赖机器的常量
  2. 关注运行时间的增长 当 T(n)中的 n 趋近于无穷大

θ 符号(notation):
去除低阶项，
去除其前面的常数因子

Ex 3n^3 + 90n^2 - 5n + 6046 = θ(n^3)

一个 θ(n^3) 的算法一定会占胜一个 θ(n^2) 的算法

  • 插入排序最坏的情况

逆序数组n T(n) = ∑ θ(j) = θ(n^2) j=2

插入排序快吗？n 比较小的时候，插入排序还是挺快的。但 n 的数字变大的时候，插入排序就变显得并不那么快了。

2.2 归并排序

merge sort A[1…n]

  1. if n = 1, done Time: time θ(1)
  2. recursively sort A from A[1] up to A[n/2], and A[n/2+1] to A[n] Time: 2T(n/2)
  3. Merge 2 sorted lists. Time: θ(n)

Key subroutine Merge(关键子程序-merge)

20 12 13 11 7 9 2 1

比较两个序列未取的最小 index 的两个数，哪个最小，则是两个序列当前的最小值。

Time = θ(n) on n total elem S Linear time

Recurrence(递归关系)

​ | θ(1), if n=1
T(n) = | 2T(n/2) + θ(n), if n > 1

Recursion Tree
T(n) = 2T(n/2) + cn, const c > 0
T(n) = logn * θ(n) = θ(n*logn)

3 渐进符号，递归和解法

3.1 渐进符号

大 O 符号(Big-O notation)

f(n) = O(g(n))

假设 f(n)非负，在适当的常数，c, n0, 使得 0 <= f(n) <= c*g(n), 对于充分大的 n 成立。

Ex: 2n^2 = O(n^3)

大 O 公式的等号不对等，

再定义: f(n)属于 g(n)构成的函数集，

O(g(n)) = { f(n) | 存在常数 n0 > 0, C > 0, 使得 n >= n0 时 0 <= f(n) <= C*g(n) ｝

所以写说 f(n) ∈ O(n)， 例如：2n^2 ∈ O(n^3)

宏(Macro convention)

A set in a formula represents an anonymous function in that set.

Ex: f(n) = n^3 + O(n^2)

There is a function h(n) < O(n^2) such that f(n) = n^3 + h(n)

有低阶项，以某个常数乖以 n2n^2 即 C×n2C\times n^2 为上界

Ex: n^2 + O(n) = O(n^3) _注意，大 O 在等号不同侧代表含意是相同的，但是等号代表的涵意不同，equal sign is asymmetric _

means for any f(n) ∈ O(n) there is an h(n) ∈ O(n^3) such that n^2 + f(n) = h(n)

总的来说： 大 O 符号很好定义了上界（通常在算法里表示最坏情况），但我们还需要下界（一般在算法里面表示最小值）。

大 Ω 符号(Big Omega-notation)

Ω(g(n)) = {f(n): there exist consts c > 0, n0 > 0 Such that 0 <= c*g(n) <= f(n) for all n >= n0 }

Ex: √n = Ω(logn)

对于充分大的 n, 根号 n 至少是 logn 的常数倍大 Ω 基本对应了大于等于。

大 θ 符号

θ(g(n)) = O(g(n)) ∩ Ω(g(n))

有点像 = 号，但其实不尽然，表示>= 和 <= 之间的渐近

小 o 符号和小 ω

小 o 相当于<
o(g(n)) = { f(n) | 存在常数 n0 > 0,
对于任意 C > 0, 使得 n >= n0 时 0 <= f(n) <= C*g(n) }

Ex: 2n^2 = o(n^3) -> (n0 = 2/c)

小 ω 相当于>
Ω(g(n)) = {f(n):
对于任意c > 0, there exist consts n0 > 0
Such that 0 <= c*g(n) <= f(n)
for all n >= n0 }

Analogies:

OΩθ
<=>==

3.2 Solving recurrences

代换法(substituion method)

  1. 猜测其大概的形式
  2. 试着验证满足数学归纳
  3. 找出常数

Ex: T(n) = 4T(n/2) + n
[T(1) = θ(1)]
T(n) - n = 4T(n/2) = 16T(n/4) = m^2T(n/m) = n^2*T(1) = T(n^2)

注意归纳法在无穷归纳中的应用，大 O 符号不能用于无穷序列

  • Guess: T(n) = O(n^3)

  • Assume T(K) <= c*k^3 for k <= n

  • Tn = 4T(n/2) + n
    <= 4c(n/2)^3 + n
    = 1/2    cn^3 + n
    <= cn^3 (根据 Assume，T(n) = cn^3 ) cn^3 - 1/2    cn^3 -n >= 0
    1/2    cn^3 - n >= 0
    1/2    c*n^2 >= 1 n^2 >= 2/c

    $ 当 n >= sqrt(2/c) 时，T(n) = O(n^3) 成立。

下面证明紧界(tight bound)

  • Assume: T(k) = c*k^2 for k < n
  • T(n) = 4(n/2) + n <= 4c(n/2)^2 + n = cn^2 + n

为了使 cn^2 + n < cn^2，必需使得 n 小于零，然而这显然不可能，证明失败！

再次假设：

  • Assume T(k) <= c1k^2 - c2k for k < n
  • T(n) = 4T(n/2) + n = 4(c1*(n/2)^2) -c2*(n/2) + n = c1n^2 + (1-2c2)n <= c1n^2 - c2*n

c1n^2 - c2n - c1n^2 - (1 - 2c2)*n = (c2 - 1)*n >= 0

​ $ c2 > 1 时，T(n) = O(n^2) 成立。

还有一点需要考虑到的是 base 情况，当 n = 1 时，

T(1) = c1 - c2，所以 c1 必须大于 c2

递归树(recursion-tree)

Ex: T(n)=T(n/4)+T(n/2)+n2T(n) = T(n/4) + T(n/2) + n^2 =T(n/16)+T(n/8)+T(n/8)+T(n/4)+n2/16+n/4+n2= T(n/16) + T(n/8) + T(n/8) + T(n/4) + n^2 / 16 + n^ / 4 + n^2

plaintext
         T(n) = n^2          =     n^2               =                    n^2
             |       |        |        |                            |             |
            T(n/4)  T(n/2)   (n/4)^2  (n/2)^2                 (n/4)^2           (n/2)^2
                            |      |   |        |             |      |        |         |
                        T(n/16) T(n/8) T(n/8)   T(n/4)   (n/16)^2  (n/8)^2  (n/8)^2  (n/4)^2
                        ......................节点数小于n

一层一层求和

T(n)=n2+5/16∗n2+25/256∗n2<=((5/16)0+(5/16)2+...)n2<=2n2=O(n2)=Ω(n2)T(n) = n^2 + 5/16*n^2 + 25/256*n^2 <= ((5/16)^0 + (5/16)^2 + ...) _ n^2 <= 2 _ n^2 = O(n^2) = Ω(n^2)

以上结论是怎么得出的，对于几何级数：

T(n)=(516)0×n2+(516)1×n2...(516)k×n2<=(12)0×n2+(12)1×n2...(12)k×n2<2n2=O(n2)\begin{align*} T(n) &=(\frac{5}{16})^0 \times n^2 + (\frac{5}{16})^1 \times n^2...(\frac{5}{16})^k \times n^2 \\ &<= (\frac{1}{2})^0 \times n^2 + (\frac{1}{2})^1 \times n^2...(\frac{1}{2})^k \times n^2 \\ &< 2n^2 \\ &=\mathbf{O}(n^2) \end{align*}

主方法(Master method)

是一个递归树的应用，但更加精准，但只能用于特定的递归式:

T(n) = a*T(n/b) + f(n)​ a >= 1, b > 1 f(n) 渐近需要趋正

主要思路：对比 非递归函数 f(n) 和 函数 nlog⁡ban^{\log_ba}

**Case 1: **

f(n) = O(nlogb(a−ε)n^{log_b(a - ε)}) for some ε > 0. (即 f(n)<O(nlogba)f(n)<O(n^{log_ba}) 指数级小于)

=> T(n)=θ(nlogba)T(n) = θ(n^{log_ba)}

**Case 2: **

f(n)=θ(nlogba∗logkn)f(n) = θ(n^{log_ba}*log^kn) for k >= 0 注意 k 的限制条件，若 k < 0 则主方法不适用。(即 f(n) 和 θ(nlogba∗logkn)θ(n^{log_ba}*log^kn) 在指数级上一样，但是系数上是一个 log 函数) => T(n)=θ(nlogba×lgk+1n)T(n) = θ(n^{log_ba} \times lg^{k+1}n)

Case 3: f(n)=Ω(nlogb(a+ε))f(n) = Ω(n^{log_b(a+ε)}) for ε > 0 & af(n/b) <= (1-ε’)f(n) for some ε’ > 0. (即 f(n) 指数级大于 O(nlogba)O(n^{log_ba}), 后面的条件是为了保证在缩小问题规模时，af(n/b)是渐进趋小的) => T(n)=θ(f(n))T(n) = θ(f(n))

Ex: T(n) = 4T(n/2) + n

n^logb(a) = n^2 >= n = f(n)

满足 case 1, 所以 T(n) = θ(n^logb(a)) = θ(n^2)

Ex: T(n) = 4T(n/2) + n^2 f(n) = n^2 = n^logb(a)_log^k(n) = n^2 _ log^k(n) -> k = 0

n^logb(a) = n^2 = n^2lg^0(n) = f(n) k = 0 满足 case 2: T(n) = θ(n^logb(a)lg^k+1(n)) = = θ(n^2lg^k+1(n)) 因为 k = 0 = θ(lgnn^2)

Ex: T(n) = 4T(n/2) + n^3 f(n) == n^3 满足 case 3: T(n) = θ(n^3)

Ex: T(n) = 4T(n/2) + n^2/lgn = θ(n^2 * lglgn) try prove:

plaintext
                n^2/lgn
                (n/2)^2/lg(n/2) * 4 = n^2/log(n/2)
                (n/4)^2/log(n/4) * 16 = n^2/log(n/4)
                (n/8)^2/log(n/8) * 64 = n^2/log(n/8)
                ......
                                      = n^2*log(n/n) = n^2*lg1

T(n) = n^2*(lgn + lg(n/2) + lg(n/4) + … + lg(1)) = n^2*(lgnlgn - (lg1 + lg2 + lg4 + lg8 + …+ lgn)) = n^2(lgn*lgn - (1+lgn)*lgn/2) = n^2(lgn*l gn/2 - lgn/2) =

主方法的证明

​ f(n) f(n/b) f(n/b) f(n/b) f(n/b) 有 a 个

aθ(1)\theta(1) aθ(1)\theta(1) aθ(1)\theta(1) aθ(1)\theta(1) aθ(1)\theta(1) aθ(1)\theta(1) aθ(1)\theta(1) 有 alogbna^{log_bn}个

共有 logb(n) 层，所以最后一层是，alogbn=nlogbaa^{log_bn} = n^{log_ba} 各层级的时间为 f(n) af(n/b) 注意这里结合 case3 中要求 af(n/b) <= (1-ε’)f(n/b) f(n)要求余项处于一个收敛的状态 a2(n/b2)a^2(n/b^2) … θ(nlogba)θ(n^{log_ba})

将以上各层级结合，看谁占主导，in case3 f(n) 占主导，以下各层以几何级数递减 in case1, θ(n^logba) 占主导，以上各层几何级数递减 **in case2, **f(n) 与 θ(n^logba) 相接近，所以 T(n)=f(n)∗h=f(n)∗logbn=θ(nlogba∗lgk(n))∗logbn=θ(nlogba∗lg(n))T(n) = f(n) * h = f(n) * log_bn = θ(n^{log_ba}*lg^k(n)) * log_bn=\theta(n^{log_ba}*lg(n)) (因为logbnlog_bn 中 b 是一个常数，所以 logbn=θ(lgn))log_bn = θ(lgn) )

$: =θ(nlogba∗lgk+1n)= θ(n^{log_ba}*lg^{k+1}n)

be careful! root n^logb(a) == af(n/b)

so when we compare n^logb(a) and f(n) is actually compare af(n/b) and f(n)‘s residue, so in case you 1: if f(n)‘s residue = O(n^logb(a)), we ignore the residue -> T(n) = n^logb(a)

in case 2: if f(n)‘s residue is very close to af(n/b) = n^logb(a) then find out a constant lg^kn, so that (log^k(n)_f(n)‘s residue) = n^logb(a) -> T(n) = (1 + (lg^k(n))^lg^n) _ n^logb(a) = //TODO

Divide and Conquer

Steps

  1. Divide the problem (instance) into one or more sub problems.

  2. Conquer each sub problem recursively

  3. Combine solutions

Merge sort

Merge sort Running time:

T(n) = 2T(n/2) + θ(n)

使用主方法：nlogba=n=n∗lgkn=n∗lg0n(k等于0)=>f(n)=>θ(n)n^{log_ba} = n = n * lg^kn = n * lg^0n (k等于0) => f(n) => θ(n)

case 2: → T(n)=nlgnT(n) = nlgn

Binary search (find value x in a sorted array)

  1. Divide: compare x with middle
  2. Conquer: recurse in one subarray
  3. Combine: trivial

以下是我自己预先的推导过程：nlogba=nlog21=n0对比f(n)=1 n^{log_ba} = n^{log_21} = n^0 对比 f(n) = 1 所以此时处理 case 2: nlogba\*logkn=f(n)  {when k=0}n^{log_ba}\*log^kn = f(n)\ \ \{when\ k=0\}

⇒T(n)=nlogba×logk+1n=n0\*logn=logn \Rightarrow T(n) = n^{log_ba} \times log^{k+1}n = n^0 \* logn = logn

Powering a number

定义: give number x, integer n >= 0, compute x^n

T(n) = T(n/2) + θ(1) = θ(lgn)

Fibonacci numbers

plaintext
  0 if n = 0

Fn = 1 if n = 1 Fn-1 + Fn-2 if n >= 2

F(n) = F(n-1) + F(n-2) = F(n-2) + F(n-3) + F(n-3) + F(n-4) = 2F(n-2) + F(n-3) = 3F(n-3) + 2F(n-4) = 5F(n-4) + 3F(n-3) = 8F(n-5) + 5F(n-4)

形成等比数列，最终证明斐波那契函数为F(n) = 1/sqrt(5) * (((1 + sqrt(5))/2)^2 - ((1 - sqrt(5)/2)^2) = φ^n/sqrt(5) - (1 - φ)^n/sqrt(5)

事实上只需要 n 次笨拙的计算即可得到斐波那契函数的值。然而此处我们要计算算法递归的算法复杂度， 而它使用了自上而下的递归算法，所以非常复杂如下

Naive recursive alg: Time: Ω（φ^n) （φ = (1 + sqrt(5)) / 2）指数级的时候非常差，非常不好。(polynomial)多项式时间算法相对较好

所以我们接下来使用由下至上的方法

Bottom-up algorithm Compute For F1, F2, F3 … Fn

Time: θ(n)

naive recursive squaring

Fn = φ^n/sqrt(5) - (1-φ)^n/sqrt(5) = φ^n/sqrt(5) 这样的话，就可以使用之前所述的使用 lgn 复杂度的方式求,φ^n，然后再除以 sqrt(5)即可。但是：真实计算机中浮点数是缺乏精度的，如果进行近似取整，将得不到正确答案。引出下面的内容

平方递归算法

Thm: (Fn+1 Fn ) = (1 1)^n (Fn Fn-1) (1 0)

=> θ(logn)算法

证明：

Base (1 1)^1 = (F2 F1) (1 0) (F1 F0)

Step: (Fn+1 Fn ) = (Fn Fn-1 )(1 1) (Fn Fn-1) (Fn-1 Fn-2)(1 0) = (Fn + Fn-1, Fn) (Fn-1 + Fn-2, Fn-1) = (Fn+1, Fn) (Fn, Fn-1) = (1 1)^n (1 0)

Matrix multiplications

Input: A = [aij] B = [bij] (i,j = 1…n) Output: C = [cij] = A*B n Cij = ∑ a_ik * b_kj k=1

for i<- 1 to n do for j<-1 to n do for k <- 1 to n cij <- 0 do cij <- cij + aik + bjk

Divide-and-conquer alg: Idea: nn matrix = 22 block matrix of n/2 * n/2 sub matrix.

但这种分法并不会更快，而且会有下标问题。

Strassen’s algorithm(施特拉森) Idea: reduce # musts -> 7 p1 = a(f-h) p2 = (a+b)h p3 = (c+d)e p4 = d(g-e) p5 = (a+d)(e+h) p6 = (b-d)(g+h) p7 = (a-c)(e+f) r = p5 + p4 - p2 + p6 s = p1 + p2 t = p3 + p4 u = p5 + p1 - p3 - p7

u = ae + ah + de + dh

  • af - ah

  • ce -de

  • ae - af + ce +cf

    = dh + cf

Strassen.

  1. Divide A,b compute terms for products θ(n^3)

  2. Pi p1 p2 …p3 recursively

  3. calculate r s t u θ(n^2)

T(n) = 7T(n/2) + θ(n^2) = θ(n^lg7) = θ(n^2.81) case 1

但这还不是最快的目前最快的约为 θ(n^2.376)

VLSI(very large scale integrated) layout

Problem: Embed a complete binary tree on n leaves in a grid with minimum area

md
<!--[tree](images/vlsi_tree2.png)-->

高度和宽度H(n) ~ logn W(n) ~ n

H(n) = H(n/2) + θ(1) = logn case 2

W(n) = 2W(n/2) + θ(1) = θ(n)
n^logb(a) = n > f(n) case 3

Area = H(n) * W(n) = n*logn

不够好，要进化 Goal:* W(n) = θ(sqrt(n)) H(n) = θ(sqrt(n))

Area = W(n)*H(n) = θ(n)

这种形式必须使用 W(n) 和 H(n) 的 n^logb(a)或者 f(n)为 1/2 指数，并且另一个可忽略：假设一种形式：

W(n) = 2T(n/4) + O(n^(1/2-ε))

如图

tree2

L(n) = 2l(n/4) + θ(1) = 0(sqrt(n)) case 1

​

4 快排和随机算法

快速排序 - Tony Hoare in 1962

  • Divide and conquer
  • Sorts “in place”
  • very practical(with tuning)

Divide and conquer

  1. Divide: Partitioning array into 2 subarrays around pivot x $ element in lower subarray <= x <= elements in upper subarray.

  2. Conquer: Recursively sort 2 subarrays.

  3. Combine: Trivial

Key Linear-time (θ(n)) partitioning subroutine

python
partition (A, p, q) // A[p-q]
    x <- A[p]       // pivot = A[p]
    i <- p
    for j <- p + 1 to q
        do if A[j] <= x
            then i <- i + 1
                exch a[i] <-> a[j]
    exch A[p] <-> A[i]
    return i

p:0 q:5 x:8 i:0 j:1 8 2 4 9 3 6 p:0 q:5 x:8 i:1 j:2 8 2 4 9 3 6 p:0 q:5 x:8 i:2 j:3 8 2 4 9 3 6 p:0 q:5 x:8 i:2 j:4 8 2 4 9 3 6 p:0 q:5 x:8 i:3 j:5 8 2 3 9 4 6 p:0 q:5 x:8 i:4 j:6 8 2 3 6 4 9 end for exch A[p] <-> A[i] 4 2 3 6 8 9

Time = θ(n) for n-element subarray

Ex. 6 10 13 5 8 3 2 11 x=6 i j 6 5 13 10 8 3 2 11 i j 6 5 3 10 8 13 2 11 i j 6 5 3 2 8 13 10 11 i j end for exch x <-> A[i] 2 5 3 6 8 13 10 11

Quicksort(A, p, q) if p < q then r <- Partiion(A, p, q) Quicksort(A, p, r-1) Quicksort(A, r+1, q)
Init call quicksort(A, 1, n)

Analysis - assume all elements distinct

(有重复的无素，这个算法就变得不那么好了，最初的分划方法对相同元素有优化)

T(n) = worst-case time

  • input sorted or reverse sorted
  • one side of partition has no elements T(n) = T(0) + T(n-1) + θ(n) = θ(1) + T(n-1) + θ(n) = θ(1) + T(n-2) + θ(n-1) + θ(n) = θ(1) + θ(2) + … + θ(n) = θ(n*(n-1/2)) = θ(n^2) (arith series[等差数列], like insertion sort)

快排的重点在于其平均情况非常好

Recursion tree T(n) = T(0) + T(n-1) + cn T(n) = cn = cn T(0) T(n-1) T(0) c(n-1) T(0) T(n-2) = cn T(0) c(n-1) T(0) c(n-2) T(0) c(n-3) .
. . θ(1) 这种递归树是一种高度不平衡的递归树n θ(∑ ck) = θ(n) k=1

Best-case analysis(intuition only)

If we’re really lucky, Partition splits the array n/2 : n/2

T(n) = 2T(n/2) + θ(n) = θ(n*logn)

n^logb(a) = n = (logn)^0 _ n {k = 0} so we are in case 2: T(n) = n _ (logn)^(k+1) = n * logn

Supose split is always 1/10:9/10:

T(n) = T(n/10) + T(9n/10) + θ(n)

T(n) = θ(n) = θ(n) T(n/10) T(9n/)10 θ(n/10) θ(9n/10) T(n/10^2) T(9n/10^2) T(9n/10^2) T(9^2n/10^2)

= θ(n) θ(n/10) θ(9n/10) θ(n/10^2) θ(9n/10^2) θ(9n/10^2) θ(9^2n/10^2)

即时我们发现，树的各分支高度不一，左边最矮为 log10(n), 右边最高为 log(10/9)(n)

然后我们开始，从上至下的求和，会发现，前 log10(n)层之和都为 cn，然后开始有一些层的和小于 cn

T(n) <= cn*log(10/9)(n) + θ(n)

supose we alterrate lucky, unlucky:

L(n) = 2U(n/2) + θ(n) Lucky U(n) = L(n-1) + θ(n) Unlucky

=> L(n) = 2(L(n/2-1) + θ(n/2)) + θ(n) = 2L(n/2 -1) + θ(n) = θ(nlogn) Lucky

Randomized quicksort

  • the running time is independent of input ordering.

  • no assumptions about input distribution

  • no specific input elicit the worse behavior

  • the worst-case is determined only by a random-number generator

**by pivot on round element **

Analysis

T(n) = r. v. for running time assuming the random numbers are independence

For k = 0, 1, …, n-1, let

X_k = 1 if partition generate a k:n-k-1 split 0 otherwise

指示器随机变量（indicator random variable）

X_k 的期望

E[X_k] = 0Pr{X_k=0} + 1Pr{X_k=1} = Pr{X_k=1} = 1/n

T(n)={T(0)+T(n−1)+θ(n)  ∣  if 1:n−1 splitT(1)+T(n−2)+θ(n)  ∣  if 1:n−2 split...T(n−1)+T(0)+θ(n)  ∣  if n−1:1 split}T(n)=\begin{Bmatrix} T(0)+T(n-1)+\theta(n)\ \ | \ \ if\ 1:n-1 \ split \\ T(1)+T(n-2)+\theta(n)\ \ | \ \ if\ 1:n-2 \ split \\ ...\\ T(n-1)+T(0)+\theta(n)\ \ | \ \ if\ n-1:1 \ split \\ \end{Bmatrix}

引入指示器随机变量，表达式T(k)+T(n-k-1)+θ(n)的累加，直接 X_k = 1 这种分化出现时才有值 n-1
= ∑ X_k(T(k)+T(n-k-1)+θ(n)) k=0

E[T(n)]= E[∑..] n-1 = ∑ E[X_k(T(k)+T(n-k-1)+θ(n))] (期望的和等于和的期望) k=0 n-1 = ∑ E[X_k]*E[T(k)+T(n-k-1)+θ(n)] k=0 = (1/n)∑ E[T(k)]+ (1/n)∑E[T(n-k-1)]+(1/n)∑θ(n) = (2/n)∑ E[T(k)] + θ(n) Absorb k = 0, 1 terms into the θ(n) for tech convenience E[T(n)]=(2/n)∑k=2n−1E[T(k)]+θ(n)E[T(n)] = (2/n) \sum\limits_{k=2}^{n-1}E[T(k)] + θ(n)

Prove E[T(n)]<=anlg(n)E[T(n)] <= anlg(n) {a > 0} Choose a big enough so that anlogn >= E[T(n)] for small n
n-1 Use fact ∑ klogk <= 1/2 n^2logn - 1/8n^2 k=2

用推导法证明：

  1. 假设 ∑ klogk <= 1/2 n^2logn - 1/8n^2 成立，则有：n-2 ∑ klogk <= 1/2 (n-1)^2log(n-1) - 1/8(n-1)^2 k=2 n-1 n-2 ∑ klogk = ∑ klogk + (n-1)log(n-1) <= 1/2 (n-1)^2log(n-1) - 1/8(n-1)^2 + nlogn k=2 k=2
    欲证明 => 0<= 1/2 (n^2 - 2n +1)log(n-1) - 1/8 (n^2 - 2n + 1) + nlogn - nlog(n-1) - n 0<= 1/2n^2log(n-1) - nlog(n-1) + 1/2log(n-1) - 1/8n^2 + 1/4n - 1/8 + nlogn - nlog(n-1) + logn = 1/2n^2log(n-1) + 1/2log(n-1) - 1/8n^2 + 1/4n - 1/2log(n-1) - 1/8 - nlog(n-1) + logn = 1/2n^2*log(n-1) + 1/4n - 1/2log(n-1) - 1/8n^2 - 1/8

​ n-1 E[T(n)] <= 2/n ∑ aklogk + θ(n) ​ k=1 ​ <= 2a/n∑(1/2n^2logn - 1/8n^2) + θ(n)
​ <= anlogn - an/4 + θ(n) ​ <= anlogn { if a is big engough so that an/4 dominate θ(n) }

快速排序是一个很不错的算法，其通常比归并排序快三倍以上，虽不然能归并排序那样提供可靠的保证(其在最坏的情况下不是 nlogn，但如果应用 randomdized quicksort)，总体来说会快出三倍以上。

besides， 要可能需要在基础规模上做一些优化(coarsen the base cases)，还有一些别的技巧，但几乎所有的好的排序算法，都是基于快排的。

它的另一个优势是，在虚拟内存的缓存中运行良好。

5 堆排序

堆排序的时间复杂度是 θ(nlogn)，但不同于归并排序，只需要常数个额外存储空间。

5.1 二叉树

二叉树是指每个节点最多有两个子树的树结构，通常称左子树(left subtree)和右子树(right subtree)，常被用于二叉查找树和二叉堆。二叉树的每个节点至多只有二棵子树(不存在度大于 2 的节点)，二叉树子树有左右之分，次序不能颠倒。二叉树的第 i 层至多有 2^(i-1) 个节点，深度为 k 的二叉树至多有 2^k - 1 个节点。另外，对于任意二叉树，其度为 0 的结点数为 n0（即终端结点数），那么其度为 2 的结点数为 n2，则一定有 n0 = n2 + 1。

满二叉树： 深度为 k，节点数为 2^(k-1)的二叉树即被称为满二叉树。

完全二叉树： 深度为 k 的二叉树，前 k - 1 层节点数达到最大，只在第 k 层不满，但 k 层结点全连续集中在左边。

对于深度为 k 的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号 1 至 n 结点一一对应时才称之为完全二叉树。

完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法，Dijkstra 算法，Prim 算法都要用堆才能优化。二叉排序树的效率也需要借助平衡性来提高，而平衡性基于完全二叉树。

5.2 堆

算法中的堆是指一种数据结构，而非”垃圾收集存储机制”。

二叉堆是一个近似完全二叉树以数组的方式存储起来，除了底层，树是完全充满的。且从左至右填充，如下所示： heap_array

如上，根据这样的结构，很容易得到某个元素的父节点，左节点，右节点，这种结构寻找节点，有几个比较固定的方法，在大多计算器中，只需要要通过将下标值移位就能比较简单的得到父、左、右节点的索引，某些语言中，这样的函数通常以”宏”或”内联函数”的方式实现。

最大堆 除根节点外： A[Parent(i)] >= A[i]

最小堆 除根节点外, A[Parent(i)] <= A[i]

堆排序中使用最大堆，最小堆通常 用来构造优先队列。

几个重要结论：MAX_HEAPIFY 过程，其时间复杂度为 O(logn), 它是维护最大堆性质的关键。BUILD_MAX_HEAP 过程，其具有线性时间复杂度，功能是从无序输入数据数组中构造一个最大堆。HEAPSORT 过程，其时间复杂度为 O(n*logn)，功能是对一个数组进行原址排序。MAX_HEAP_INSERT,HEAP_EXTRACT_MAX,HEAP_INCREASE_KEY 和 HEAP_MAXIMUM 过程: 时间复杂度为 O(lgn)， 功能是利用堆实现一个优先队列。

5.3 维护堆的性质

MAX-HEAPIFY(A, i) l = LEFT(i) r = RIGHT(i) if l < A.heap-size and A[l] > A[i] largest = l else largest = i if r <= A.heap-size and A[r] > A[largest] largest = r if largest != i exchange A[i] with A[largest] MAX-HEAPIFY(A, largest)

MAX_HEAPIFY 时间代价：调整 A[i] A[LEFT(i)] 和 A[RIGHT(i)] 的关系的时间代价 θ(1)，加上一棵以 i 的孩子为根结点的子树上运行 MAX_HEAPIFY 的时间代价，一般为 1n/2，最坏的情况为 2n/3，最在最后一层会发生。

T(n) = T(2n/3) + θ(1) n^logb(a) = n^(log(2/3)(1)) = n^0

in Main method case 2: T(n) = θ(logn) 所以当深度为 h 时，其时间复杂度就为 θ(h)

5.4 建堆

BUILD_MAX_HEAP(A): A.heap-size = A.length for i = [A.length/2] downto 1 MAX-HEAPIFY(A, i)

MAX_HEAPIFY 的时间复杂度是 O(lgn)， BUILD_MAX_HEAP 需要 O(n)次这样的调用，因些总的时间复杂度是 O(n*lgn)。

进一步求得其紧确界，以下 h 高度从下到上，从 0 开始：

logn logn ∑ (n/2^(h+1))O(h) = O(n ∑ (h/2^h)) h=0 h=0 logn ∞ => n ∑ (h/2^h) = O(∑) C*(1/2)^h = O(n)
h=0 h=0于是我们可以得到 其时间复杂度为

T(n) = O(n)

5.5 堆排序算法

HEAPSORT(A) BUILD_MAX_HEAP(A) for i = A.length downto 2 exchange A[1] with A[i] A.heap-size = A.heap-size - 1 MAX-HEAPIFY(A, 1)

很容易看出 T(n) = θ(nlogn)

5.6 优先队列

堆排序是一个优秀的算法，但在实际应用中，第 7 章将要介绍的快速排序的性能一般会优于堆排序。但，堆这种数据结构仍然有很多应用，高效的优先队列就是其中之一。优先队列也有优先最大队列和优先最小队列两种。

优先队列(Priority queue)是一种用来维护由一组元素构成的集合 S 的数据结构，每个元素有一个相关的的值，key，最大优先队列支持以下操作。INSERT(S，x)，S = S U {x} MAXIMUM(S) EXTRACT-MAX(S) 去掉并返回 S 中具有的最大键字元素 INCREASE-KEY(S, x, k) 将元素 x 的关键值增加到 k，这里假设 k 的值不小于 x 的原关键字值。

这个数据结构的应用十分广泛，例 如共享计算机系统的作业高度。最大优先队列记录记录将要执行的各个作业及他们的相对优先级。当一个作业完成或中断后，调 EXTRA_MAX 从所有等待作业选出具最高优先级的作业来执行。

相应的，最小优先队列支持的操作包括：INSERT, MINIUM, EXTRACT_MIN 和 DECREASE_KEY,而这种可能被用于事件驱动的模拟器。

HEAP_MAXIMUM(A): return A[1]

HEAP_EXTRACT_MAX(A): if A.heap-size < 1 error “heap underflow” max = A[1] A[1] = A[A.heap-size] A.heap-size = A.heap-size - 1 MAX-HEAPIFY(A, 1) return max

显然 HEAP_EXTRACT_MAX 的时间复杂度 O(lgn)

HEAP_INCREASE_KEY(A, i, key) if key < A[i] error “new key is smaller than current key” A[i] = key while i > 1 and A[PARENT(i)] < A[i] exchange A[i] with A[PARENT(i)] i = PARENT[i]

HEAP_INCREASE_KEY 的时间复杂度为 O(logn)

MAX_HEAP_INSERT(A, key) A.heap-size = A.heap-size + 1 A[A.heap-size] = - ∞ HEAP_INCREASE_KEY(A, A.heap-。, key) 在包含 n 个元素的最大堆上，MAX_HEAP_INSERT 的运行时间为 O(lgn)

6 速度研究

排序算法能有多快？It depends on what we call the computational model of what you can do with the elements

Quicksort θ(nlogn) randomized Heapsort θ(nlogn) Merge sort θ(nlogn) Insertion sort θ(n^2)

Can we do better than θ(nlogn)?

以上算法，都有一个同样的运算模式，即一次比较 2 个的元素。

6.1 Comparison Sorting(model)

Only use comparisons to determine relative order of elements

如果我们能证明两个元素的比较算法，是不可能慢于 θ(nlogn)，那样就比较完美了。

6.2 Decision-tree

Ex: sort <a1, a2, a3> 1:2 2:3 1:3 123 1:3 132 312

In general: <a1, a2 … an> — each internal node has label i:j i,j {1,2,3…n} means: compare a1 vs aj

  • left subtree gives subsequent comparisons if ai <= aj
  • right subtree ai >= aj each leaf gives permutation

Decision tress comparison sort

— one tree for each n — view algorithm as splitting whenever if makes a comparison — tree lists comparisons along all possible instruction traces

-running time(#comparisions) = length of path

-worst case run time = height of the tree

因此，我们只需要证明决策树的深度为最小为 nlogn 即可。

Lower bound on decision-tree sorting Any decision tree sorting n elements has height 欧米茄(nlogn)

Proof: # leaves must be >= n!

  • height h -> n! <= leaves <= 2^h => n! <= 2^h h >= lg n! h >= lg (n/e)^n

    = n lg(n/e) = n (logn - loge) = omega (nlogn)

决策树的下界问题，基于比较的排序算法的下界问题。归并排序和堆排序是渐进最优的（这俩都是非随机算法）快速排序在理想情况下也是渐进最好优的

6.3 Sorting in linear time

Counting sort: Input: A{1, n] each A[i] belong {1, ..k } Output: B[1…n] = sorting of A

Auxiliary(辅助) storage: C[1…k] K 是输入序列的范围长度

Counting sort for i <- 1 to k // 初始化长度 k 的数组，每个元素值为 1 do C[i] <- 0 for j <- 1 to n // 将 A[i]的值映射为 C 的坐标 j，并使用相应坐标 j 的值 C[j]为表示 A[i]值出现的次数（频率）do C[A[j]] <- C[A[j]] + 1 // C[i] = |{key = i}|

// 将 C[j]进行转换，表示为 A 中小于等于当前坐标 j 为值的数的个数 // C[j]即成为最后一个值为 j 的元素坐标 for i <- 2 to k
do C[i] <- C[i] + C[i-1] // C[i] = |{ key <= i }|

for j <- n downto 1 // 将 A[j]的值分别放入到对应的座标do B[C[A[j]] <- A[j] C[A[j]] <- C[A[j]] - 1 // 已放置后，将坐标减 1，对于下一个同样值为 A[j]的元素，坐标将减 1

Example:

plaintext
1 2 3 4 5        1 2 3 4

A = 4 1 3 4 3 C = |0|0|0|0| 1 0 2 2 1 1 3 5 -> 做加法，使得 C[A[j]] 表示在 B 中的下标

plaintext
1 2 3 4 5

B = 0 0 0 0 0 1 1 3 5
0 0 0 0 4 1 1 3 4 B[C[A[1]] = A[1] C[A[1]] = C[A[1]] - 1
1 0 0 0 4 0 1 3 4 B[C[A[2]] = A[2] C[A[2]] = C[A[2]] - 1 1 0 3 0 4 0 1 2 4 B[C[A[3]] = A[3] C[A[3]] = C[A[3]] - 1 1 0 3 4 4 0 1 2 3 B[C[A[4]] = A[4] C[A[4]] = C[A[4]] - 1 1 3 3 4 4 0 1 1 3 B[C[A[5] = A[5] C[A[5]] = C[A[5]] - 1

​

Time: T(n) = O(n + k) k = O(n) then O(n)

Stable sort preserves the relative order of equal elements 即，原数组中，即使是相同元素之前的相对顺序，也没有被改变，因为从 n -> 1 进行放置，第一个遇到的相同元素始终下标最大，然后再对其下标减 1

Exercise: figure out which other sorts are stable?

6.4 Radix sort （Herman Hollerith ~1890）

用以解决在线性时间内对大范围数据进行排序的问题

Example 3 2 9
4 5 7 6 5 7 8 3 9 -> 4 3 6 7 2 0 3 5 5

Sort least digit Sort second digit Sort first digit

Correctness induction on digit position t -assume by induction sorted on low-order t-1 digits - sort on digit t |- if the two elements have same t^th digit,stability => same order 根据刚才的归纳法假设 t-1 是有序的 => 保持不变仍然是有育的 sorted order |- different t^th digit => sorted order.

Analysis - use counting sort for each digit - say n integers each b bits (range = 0 - (2^b - 1) ) - split into b/r “digits” each r bits(2^r)

plaintext
T(n) = O(b/r) * O(n+k) = O(b/r*(n+2^r))
   对r 求导，求导数等于0的解，数学解是最好的

   r 越大越好        >=1 时越小越好
   b/r * n    +      b*2^r/r
   当 n >= 2^r 时，我们才使用计数算法，取满足这种情况时的r的最大值 r = lgn

将 r = lgn 代入

T(n) = O(bn/logn) if numbers in range 0 - 2^b and 0 - n^d -1

then time = O(dn)

计算排序可以处理某个常数乘以 d 范围内的数，但用下面这种方式，可以处理 0 到某个常数次方范围内的数如果 d=O(1) 这就是一个线性时间的算法，所以在 n^logn 范围内，就可能击败 n*logn 的算法

假如有一系列 32 位数，我们把它拆分为 8 位的段，即 r=8 那么会经过 4 个 8 位的 n 次循环，需要 2^8 即 256 位的辅助空间，

但是，计数排序在缓存上有更多的要求，除非数据确实很小。

还有：美好的假设，如果有计算机能在常数时间内对任意整数做计算，那么目前最好的算法的运行时间是 n*sqrt(lglgn) expected

7. 顺序统计、中值

7.1 Order statistics

give n elements in array find kth smallest element (elements of rank k)

传统的方法是直接排序，然后取出第 k 个元素，

但我们希望能不使用排序的方式，并且在线性的时间内完成

k = 1 minimum k = n maximum k = ceil(n+1/2) or floor(n+1/2)

Randomized divide&conquer:

Rand-select(A, p, q, i) // i^th smallest in A[p,q] if p=q then return A[p] r <- Rand-Partition(A, p, q) k <- r - p + 1 // k = rank(A[r]) if i = k then return A[r] if i < k then Rand-select(A, p, r-1, i) if i > k then Rand-select(A, r+1, q, i - k)

intuition for analysis (assume the elements are distinct)

Lucky case: 1/2 : 1/2 | 1/10 : 9/10

T(n) = T(9n/10) + θ(n)

in case 3: T(n) = θ(n)

Unlucky case: 0:n-1 T(n) = T(n-1) + θ(n) T(n) = θ(n^2)

7.2 Analysis of expected time

  • let T(n) be the random variable for running time of Rand-selected on input of size n. assuming random number are independently

  • define indicator random invariable X_k for all k = 0,1…n-1 1 if partition generates a k:n-k-1 split X_k =
    0 otherwise

    plaintext
          T(max{0, n-1}) + θ(n) if 0, n-1 split

    T(n) <= T(max{1, n-2}) + θ(n) if 1, n-2 split … T(max{n-1, 0}) + θ(n) if n-1, 0 split n-1 = ∑ X*k(T(max{k, n-k-1})) + 0(n) k=0 n-1 E[T(n)] <= E[∑ X_k(T(max{k, n-k-1})) + 0(n)]
    k=0 n-1 <= ∑ E[X_k(T(max{k, n-k-1}))} + 0(n)]
    k=0 n-1 <= ∑ E[X_K] * E[T(max{k, n-k-1}) + 0(n)]
    k=0 n-1 <= ∑ (1/n) _ E[T(max{k, n-k-1}) + 0(n)]
    k=0 n-1 n-1 <= 1/n ∑ E[T(max{k, n-k-1})] + 1/n ∑ 0(n)
    k=0 k=0 n-1
    <= 1/n ∑ E[T(max{k, n-k-1})] + 0(n)
    k=0
    n-1
    <= 2/n ∑ E[T(k))] + 0(n) k=floor(n/2)

不知道怎么证明，想想我们的需要的结论？

需要: T(n) <= 0(n)

不妨设 T(k) <= ck {c 为 >0 的足够大的常数}，则有

Proof substitution method Assume true for <n n-1
T(n) <= 2/n ∑ E[ck] + 0(n) k=floor(n/2) n-1 <= 2c/n ∑ k + 0(n) k=floor(n/2) <= 3c*n/4 - c/2 + n

plaintext
    = cn - 3c*n/4 - c/2 - n > 0 for c sufficiently large

Rand-Select has 0(n) expected ranging time 0(n^2) worst case

7.3 Worst-case linear-time order statistics

plaintext
[Blum, Floyd, Proatt, Rivest, Tarjan]
- idea generate good pivot recursively

Select(i, n): 1. Divide the n elements into floor(n/5) groups of 5 elements each Find the median of each group use 0(n) 2. Recursively select median x of the (n/5) group medians use T(n/5) 3. Partition with x as pivot, let k = rank(x) 4. if i=k then return x if i<k then recursively Select(i, n-k-1) if i>k then recursively Select(i+k, n)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 高度为 5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 　　宽度为 n/5

把以上的矩阵都画上箭头
b ^ | a < b a

= 3 _ floor(n/5)/2 elements <= x and >= x = 3 _ floor(n/10) = 3*n/10

Simplification for n >= 50 3*n/10 >= n/4

So: T(n) <= 0(n) + T(n/5) + T(3n/4) = 0(n) + T(19n/20)

in case 3: T(n) = 0(n) 这种证明方式是错的，T(n/5) + T(3n/4)不能合并，上式已经假设了 T(n) 为线性，即 T(n) = cN，然后将两式合并。

使用代换法： 假设 T(n) <= cn T(n) = cn/5 + c3n/4 + 0(n) = c19/20n + 0(n) <= cn即需要： cn/20 > 0(n) 只需要 c 大于 0(n)的常数的 20 倍即可。

试想一下上方的 5 变为 3

T(n) = cn/3 + c2*floor(n/3) + 0(n) 显然不行

8 Hashing I

8.1 Symbol-table problem

Table s holding n records

key[x] and satellite data

Operations

  • Insert(S, x): S <- S u {x}
  • Delete(S, x): S <- S - {x}
  • Search(S, k): return x $ key[x] = k or nil if no such x

8.2 Direct access table

Suppose keys are drawn from a set of U = {1, 2, 3, 4, …, m-1}

Assume the keys are distinct

Set up array T[0, …, m-1] to represent dynamic set S

plaintext
     x if x ∈ S and its key[x] is k

$ T[k] = nil otherwise

Operations take 0(1) in worst case

以上的问题是有大量的空单元，空索引

8.3 Hashing

Hash function h maps keys “randomly” into slots table T

when a record to be inserted maps to an already occupied slots a collision occurs

tree

如果是 cache 的话，把冲撞处的值替换掉即可，

resolving collisions by chaining Idea: link records in same slot into list

EX: slot i -> s1 -> s2 -> s3

plaintext
independent of where other keys are hashed.

Define: The load factor of a hash table with n keys and m slots is α = n/m = average # keys per slots

Expected unsuccessful search time = 0(1 + α) hash search list accessing Expected search time = 0(1) if α = O(1) or if n = O(m)

[8.4 Choosing a hash function]

  • Should distribute keys uniformly into slots.
  • Regularity in key distribution should not affect uniformity

Division method: h(k) = k mod m don’t pick m with small divisor

Ex: d = 2 and all keys even

=>odd slots never use

Ex: m = 2^r

=>hash doesn’t depend on all bits of k

k = 1011000111011010 如果 r = 6 m = 2^6

在这种情况下，对 k 进行 2^6 取余，只和二进制数的后 6 位有关，这不符合 hash 函数的意图。

pick m to be a prime not too close to a power of two or ten.

因为这是两个最常用的底，很可能在需要处理的数据里面出现规律。

Multiplication method

m = 2^r computer has w-bit words, 32 位或 64 位等

A is an odd integer 2^(w-r) < A < 2^w

rsh is “right shift”

h(k) = (A*k mod 2^w) rsh (w-r)

  • Don’t pick A too close to a power of two
  • Fast method multiplication mod 2^w is faster than division right shift is fast

Ex: m = 8 = 2^3, w = 7

plaintext
           1 0 1 1 0 0 1 = A
           *
           1 1 0 1 0 1 1 = K

1 0 0 1 0 1 0 0 1 1 0 0 1 1 mod 2^w

plaintext
           0 1 0 1 0 1 1   rsh w-r = 7 - 3 = 4

                   0 1 0

想像 A 是一个小数，A*K 的操作是 K 在乘以一个小数，mod 2^w 以后，得到小数部分(假设小数点在最高位前，实质是没有)，所以最后把其右移 w-r 位，使其被限制到 2^r 的槽数中来。

想像一个车轮：Modular wheel 如果把 A 视为一个小数，实质上就是把 A 视为(A/2^8),所以 A 取质数最好，否则也要取奇数，不要接近 2^n K 与 A 相乘实质就会成为 A 的 K 倍，即 2^w 的某倍加一定的余数 1-2^w，再右移 w-r 位回归到 1-2^r 指定插槽的位置。

8.4 Resolving collisions by open addressing

No storage for links

Probe table systematically until an empty slot is found

h 就变为了含有两个参数的函数，key 和 探查序列 h： U X {0, 1, …, m-1} -> {0, 1, …, m-1} universe probe slots key number

Probe seq should be permutation， {0, 1, …, m-1} 的随机排列 Table may fill up so number of elements n <= m Deletion is difficult, but not impossible

Ex: insert k = 496

null null 586 133 null 204 null 481 null

  1. Probe(496, 0) -> 已有 204 这是随意假设的
  2. Probe(496, 1) -> 已有 584
  3. Probe(496, 2) -> 204 与 4l81 之间

Search use same sequence

  • successful: find record
  • unsuccessful: return nil

Probing strategies

  • Linear probing: h(k, i) = (h(k, 0) + i) mod m “primary clustering” long runs of filled slots key 的映射在一段上集中，并且探查就变成了类似于依次查找，个人认为脱离了与 key 值的相关性。
  • Double hash只需要预先计算好，h_1(k)和 h_2(k)的值即可h(k, i) = (h_1(k) + i*h_2(k)) mod m excellent method usually pick m = 2^r(因为做 mod 非常好计算) and h_2(k) force to be odd, 否则奇数槽就使用不到了

8.5 Analysis open addressing

Assumption of uniform hashing: each key is equally likely to have any one of the m! permutation as its probe sequence independent of other keys Theorem E[# probes] <= 1/(1-α) α 的值与目前 n 的值与 m 的比例相关
if α < 1 (mean number of keys/elements in the table < m, n < m)

Prove（unsuccessful search）1 probe always necessary with probability n/m, collision -> 2nd probe necessary with probability (n-1)/(m-1), collision -> 3nd probe necessary (n-2)/(m-2) (n-i)/(m-i)<n/m = α

E[# probes] = 1 + n/m(1+(n-1)/(m-1)(1+(n/2)/(m-2)(…(1+1/(m-n))))) <= 1+α(1+α(1+α(1+α(…)))) <= 1+α+a^2+…+ infinity ∞ <= Σ a^i i=0 = 1/(1-a)

  • α < 1 const => O(1) probes
  • if table 50% full => less than 2 probes
  • 90% => less than 10 probes

9. Hashing II

Weakness of hashing For any choice for hash function, there is a bad set of keys that all hash to same slot.

比如，对于已知的 Hash 函数，设定对应的数据输入，就可以使所有的数据都在同一个糟。

Idea: choose hash function at random independently from the keys.

9.1 Universal hashing

Define. Let U be a universe of keys let H be a finite collection of hash function mapping U to slots {0, 1 … m-1} H is universal if all x,y ∈ U where x != y such that: |{h∈H : h(x) = h(y) }| = |H|/m 表示整个 hash function set 中，h(x) = h(y) 的个数期望

Ie. if h is chosen randomly form H, the probability of collision between x and y is ? 1/m 第一数是任意的，第二个数映射到相同 slot 的概率为 1/m 所以，简单来说，每个函数碰撞的概率是 1/m, |H| 个函数里期望有 |m|/H 个函数导致 h(x) = h(y)

theorem: choose h randomly from set, suppose hashing n keys to m slots in table T, then for given keys x, expected number of collision with x E[# collisions with x]< n/m (alpha -> load factor)

prove

Let C_x be random variable denoting the total # of collisions of keys in T with x

let 1 (if h(x) = h(y)) C_xy = 0 (otherwise)

Note: E[C_xy] = 1/m and C_x = ∑ C_xy y∈T-{x}

E[C_x] = E[∑ C_xy] y∈T-{x} = ∑ E[C_xy] (Linearity of expectation) y∈T-{x}

plaintext
   = ∑ 1/m
     y∈T-{x}
   = (n-1)/m

Constructing a universal hash function

Let m be prime, decompose key k into r+1 digits:

K = <k0, k1…, kr> where 0 <= ki <= m-1 , k0 假定为低位，事实上没有关系

上式太复杂，用程序员语言解释就是，把 k 变成 base m (m 进制)的数

Pick a = <a0, a1, …, ar> each ai chosen randomly from {0, 1,…, m-1}

plaintext
                 r
Define h_a(k) = (∑ ai*ki) mod m
                 0

每一位的 k 将会被一个 randomized ai 相乘

How big is H=|h_a| ? -> m^(r+1)

Theorem: H is universal

Proof Let x = <x0, x1, …, xr> y = <y0, y1, …, yr> be distinct keys

They differ at least one digit, without lost of generality

position 0 For how many h_a ϵ H hash function do x and y collide.

Must have h_a(x) = h_a(y)

r r => ∑ aixi Ξ ∑ aiyi (mod m) i=0 i=0 r => ∑ ai(xi-yi) Ξ 0 (mod m) i=0 r => a0(x0-y0) + ∑ ai(xi-yi) Ξ 0 (mod m) i=i r => a0(x0-y0) Ξ - ∑ ai(xi-yi) (mod m)
i=1

Number theory fact Let m be prime For any z ϵ Z_m (integers mod m) -> {0, 1, …, m-1}, if z !Ξ 0, there exists a unique z^(-1) ϵ Z_m $ z*z^(-1) Ξ 1 (mod m)

另外的，如果 m 是非质数，这样的性质就不成立了，想像一个，如果 m 等于 10，就找不出这样的数。

而实质上我们通过数论可以知道，如果 z 和 m 不互质(即其 gcd != 1, 或者说有大于 1 的公约数)，z 是没有半法求出倒数的。

since x0 != y0, there exists inverse (x0-y0) r => a0 Ξ (- ∑ ai(xi-yi))*(x0-y0)^(-1)
i=0

这是一个很厉害的证明，结论是：当我们假设 distinct x, y 在 h_a(x) = h_y(y) 时，a0 是一个与 ai, xi, yi， 相关的固定值 (mod m)

Thus for any choice of a1, a2, … ar, exactly 1 of the m choices for a0 causes x and y to collide, and no collision for other m-1 choices for a0.

number of h_a’s cause x, y to collide = 1*m^r = |H|/m

9.2 Perfect Hashing

Give n keys, construct a static hash table of size m = O(n), $ search takes O(1) time in the worst case.

Idea: 2-level scheme with universal hashing at both level, No collisions at level 2.

perfect hashing

level 1:
h(14) = h(27) = 1

level 2:
h_31(14) = 1 h_31(27) = 2

if n_i items that hash to level 1 slot i, then use m_i = n_i^2 slots to level-2 table s_i

Level-2 analysis

Theorem:

Hash n keys into m = n^2 slots using random h in universal set H => E[#collisions] < 1/2

Prove:

Probability 2 given keys collide under h is 1/m = 1/n^2

in this case we have n chose 2(Cn2 n 在下 2 在上) pair

E[#collisionse] = (n chose 2) 1/n^2 = n*(n-1)/2n^2 < 1/2

Markov inequality

For random variable x >= 0, Probability {x >= t} <= E[x]/t ∞ Pf. E[X] = ∑ xPr{X=x} x=0 ∞ >= ∑ xPr{X=x} x=t ∞ >= ∑ tPr{X=x} x=t
= tPr{x>=t}

Corollary:

Pr{no collisions} >= 1/2

Pf: Pr{>= 1 collision} <=E[#collision]/1

So Pr {no collisions} = 1 - Pr{>= 1 collision} >= 1/2

To find a good level-2 hash function just test a few at random Find one quickly since at least 1/2 will work.

Analysis of storage

For level 1 choose m = n, and let n_i be random variable for # keys hash to slot i in T. Use m_i=n_i^2 slots in each level-2 table slots. n-1 E[total storage] = n + E[∑ θ(n_i^2)] = θ(n) by bucket-sort analysis i=0

Binary Search Tree(BST)

什么是二叉搜索树

搜索数支持许多动态集合操作，包括 SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE 等，即可以做字典，也可以作优先队列。

中序遍历

python
INORDER-TREE-WALK(x)
    if x != NIL
        INORDER-TREE-WALK(x.left)
        print x.key
        INORDER-TREE-WALK(x.right)

##查询二叉搜索树

python
TREE-SEARCH(x, k)
    if x == NIL or k == x.key
        return x
    if k < x.key
        return TREE-SEARCH(x.left, k)
    else return TREE-SEARCH(x.right, k)

从效率起见，用迭代替换递归

python
INTERATIVE-TREE-SEARCH(x, k)
    while x ！= NIL and k != x.key
        if k < x
            x = x.left
        else
            x = x.right
    return x
python
TREE-MINIMUM(x)
    while x.left != NIL
        x = x.left
    return x
python
TREE-MAXIMUM(x)
    while x.right != NIL
        x = x.right
    return x

后继与前驱
给定一棵二叉搜索树的一个结点，有时候需要按中序遍历查找它的后继:

python
TREE-SUCCESSOR(x)
    if x.right != NIL
        return TREE-MINIMUM(x, right)
    y = x.p
    while y != NIL and x == y.right
        x = y
        y = y.p
    return y

相应的，我自己写出 PREDECESSOR 的算法：

python
TREE-PREDECESSOR(x)
    if x.left != NIL
        return TREE-MAXIMUM(x)
    y = x.p
    while y != NIL and y.left == x
        x = y
        y = y.p
    return y

插入和删除

插入和删除会引起动态集合变化，插入相对容易，删除相对复杂。

插入

假设输入为一个节点 z， z.key=v, z.left=NIL, z.right=NIL

python
TREE-INSERT(T, z)
    y = NIL
    x = T.root
    while x != NIL
        y = x
        if z.key < x.key
            x = x.left
        else
            x = x.right
    z.p = y
    if y == NIL
        T.root = z  # tree T was empty
    elseif z.key < y.key
        y.left = z
    else
        y.right = z

删除

  • z 没有孩子结点，简单的删除，修改你结点的子节点为 NIL
  • 如果 z 只一个孩子，那么将这个孩子提升到树 z 的位置，并修改 z 的父结点，用 z 的孩子来替换。
  • 如果 z 有两个孩子，找 z 的后继 y，并让 y 占据树中 z 的位置。z 的原来右子树部分成 y 的新的右子树，并且 z 的左子树成为 y 的新的左子树。

下面是 TRANSPLANT 的过程

python
TRANSPLANT(T, u, v)
    if u.p == NIL
        T.root = v
    elseif u == u.p.left
        u.p.left = v
    else
        u.p.right = v
    if v != NIL
        v.p = u.p

下面是删除节点的过程

python
TREE-DELETE(T, z)
    if z.left == NIL
        TRANSPLANT(T, z, z.right)
    elseif z.right == NIL
        TRANSPLANT(T, z, z.left)
    else
        y = TREE-MINUTE(z.right)
        if y.p != z
            TRANSPLANT(T, y, y.right)
            y.right = z.right
            y.right.p = y
        TRANSPLANT(T, z, y)
        y.left = z.left
        y.left.p = y

除了 TREE-MINIMUM 之外，TREE-DELETE 的每一行，包括调用 TRANSPLANT，都只花费常数时间。

定理:
在一颗高度为 h 的二叉搜索树上，实现动态集合操作 INSERT 和 DELETE 的运行时间均为 O(h)

Randomly Built Binary Search Tree(BST)

BST sort

BST sort (A): T = nil for i <- to n do Tree-Insert(T, A[i]) Inorder-Tree-Walk(root[T])

Example:

A = [3, 1, 8, 2, 6, 7, 5]

Time: θ(n) + for walk n Tree-Inserts Ω(nlogn) all the time O(n^2)

if already sorted => θ(n)

其在时间复杂度上未随机化的 quciksort 具有一样的性质

Relation to Quicksort

BST sort & Quicksort make same comparisons, but in different order.

以下是快排的过程：

BST sort relate to quicksort

上图可以看出 quicksort 每次选择 pivot 从上至下其实就是二叉树插入的过程。

所以即然快排可以随机化来保证 worst case， BST 也可以， 如下。

Randomized BST Sort

  1. Randomly permute A
  2. BST sorted(A)

Time = time(randomized Quicksort)

E[time] = E[time(randomized quicksort)]

Randomly built BST = tree resulting from random BST sort

Time(BST sort) = ∑ depth(x) x∈T

E[1/n ∑depth(x)] = θ(nlogn)/n = θ(lgn) x∈T

上式说明随机搜索树的平均高度是 lgn

Theorem:

E[height of random built BST] = O(lgn)

如果能够证明这个定理，那么，查找必定能在 logn 内完成

Proof outline

  1. Prove Jenson inequality: f(E[x]) <= E[f(x)]
    for convex function f.
  2. Instead of analysing X_n = r.v of height of BST on n nodes, analyse Y_n = 2^X_n
  3. Prove that E[Y_n] = O(n^3)
  4. Conclude that E[2^X_n] = E[Y_n]=O(n^3) => 2^E[X_n] <= E[2^X_n] = E[Y_n] = O(n^3) => E[X_n] <= lg(O(n^3)) = 3lgn + O(1)

f:|R->|R is convex if for all x, y ∈ R & all α, β >= 0 with α + β = 1

plaintext
=> f(αx+βy) <= αf(x)+βf(y)

Jenson inequality 的证明太长太复杂，由于对于学习算法并不算特别重要，对其进行省略。从几何上讲，取 convex 函数的两个点，连成直线，其函数区线都在这两个点下方。

Expected BST Height analysis X_n = r.v of height of randomly built BST on n nodes.

Y_n = 2^X_n (这是一个 convex 函数)

if root r has rank k then Xn = 1 + max{X(k-1), X*(n-k)} Y_n = 2 max{Y*(k-1), Y_(n-k)}

define indicator random variable

plaintext
      1 if root has rank k

Z_nk = { 0 otherwise

Pr{Z_nk = 1} = E[Z_nk] = 1/n

plaintext
  n

Yn = ∑ Z_nk(2max{Y(k-1), Y*(n-k)})
k=1 n E[Y_n] = E[∑ Z_nk(2 max{Y*(k-1), Y*(n-k)})] k=1 n = ∑ E[Z_nk(2 max{Y*(k-1), Y*(n-k)})]
k=1 n = 2 ∑ E[Z_nk]E[max{Y*(k-1), Y*(n-k)}] k=1 n <= 2/n ∑ E[Y*(k-1) + Y_(n-k)] k=1 n-1 <= 4/n ∑ E[Y_k] k=0

Claim: E[Y_n] <= 3n^3

Proof, substitution method:

base: cn = θ(1) if c is sufficient large

(induction hypothesis)Step:

plaintext
         n-1

E[Y_n] <= 4/n ∑ E[Y_k] k=0

plaintext
      <= 4/n ∑ c*k^3

      <= 4c/n integral[0, n]x^3*dx

      <= 4c/n * n^4/4

       = c*n^3

E[X_n] 约= 2.9882×lgn

12 Balanced Search Trees