算法导论读书笔记(2)

I.渐进符号(此部分借鉴自Lazy pig)

当输入规模大到使运行时间只和增长的量级有关时，就是在研究算法的 渐近 效率。就是说，从极限角度看，我们只关心算法运行时间如何随着输入规模的无限增长而增长。

五种渐进符号 Ο   Θ  Ω  ο  ω

对任何一个函数 f ( n )，若存在正常数 c1 ， c2 ，使当 n 充分大时， f ( n )能被夹在 c1 g ( n )和 c2 g ( n )之间，则 f ( n )属于集合 Θ ( g ( n ))。可以写成“ f ( n ) ∈ Θ ( g ( n ))”表示 f ( n )是 Θ ( g ( n ))的元素。不过，通常写成“ f ( n ) = Θ (g ( n ))”来表示相同的意思。<p align="center"> </p>

上图(a)给出了函数 f ( n )和 g ( n )的直观图示，其中 f ( n ) = Θ ( g ( n ))。对所有位于 n0 右边的 n 值， f ( n )的值落在 c1g ( n )和 c2 g ( n )之间。换句话说，对所有的 n >= n0 ， f ( n )在一个常数因子范围内与 g ( n )相等。我们说 g ( n )是 f( n )的一个 渐近确界 。

Θ ( g ( n ))的定义要求每个成员 f ( n ) ∈ Θ ( g ( n ))都是 渐近非负 ，就是说当 n 足够大时 f ( n )是非负值。这就要求函数_g_ ( n )本身也是渐近非负的，否则集合 Θ ( g ( n ))就是空集。

Θ 记号的效果相当于舍弃了低阶项和忽略了最高阶项的系数。

---

 

Θ 记号渐近地给出了一个函数的上界和下界。当只有 渐近上界 时，使用 O 记号。对一个函数 g ( n )，用 O ( g ( n ))表示一个函数集合：

上图(b)说明了 O 记号的直观意义。对所有位于 n0 右边的 n 值，函数 f ( n )的值在 g ( n )下。

---

Ω 记号给出了函数的渐近下界。给定一个函数 g ( n )，用 Ω ( g ( n ))表示一个函数集合：

上图(c)说明了 Ω 记号的直观意义。对所有在 n0 右边的 n 值，函数 f ( n )的数值等于或大于 c g ( n )。

---

O 记号提供的渐近上界可能是也可能不是渐近紧确的。这里用 o 记号表示非渐近紧确的上界。 o ( g ( n ))的形式定义为集合：

O 记号与 o 记号的主要区别在于对 f ( n ) = O ( g ( n ))，界0 <= f ( n ) <= c g ( n )对某个常数 c > 0成立；但对 f ( n ) = o ( g ( n ))，界0 <= f ( n ) <= c g ( n )对所有常数 c > 0都成立。即

---

我们用 ω 记号来表示非渐近紧确的下界。 ω ( g ( n ))的形式定义为集合：

关系 f ( n ) = ω ( g ( n ))意味着

如果这个极限存在。也就是说当 n 趋于无穷时， f ( n )相对 g ( n )来说变得任意大了。

 

附：函数间的比较

设 f ( n )和 g ( n )是渐近正值函数。

传递性： f ( n ) = Θ ( g ( n ))和 g ( n ) = Θ ( h ( n )) 蕴含 f ( n ) = Θ ( h ( n )) f ( n ) = O ( g ( n ))和 g ( n ) = O ( h ( n )) 蕴含 f ( n ) = O ( h ( n )) f ( n ) = Ω ( g ( n ))和 g ( n ) = Ω ( h ( n )) 蕴含 f ( n ) = Ω ( h ( n )) f ( n ) = o ( g ( n ))和 g ( n ) = o ( h ( n )) 蕴含 f ( n ) = o ( h ( n )) f ( n ) = ω ( g ( n ))和 g ( n ) = ω ( h ( n )) 蕴含 f ( n ) = ω ( h ( n ))

自反性： f ( n ) = Θ ( f ( n )) f ( n ) = O ( f ( n )) f ( n ) = Ω ( f ( n ))

对称性： f ( n ) = Θ ( g ( n ))当且仅当 g ( n ) = Θ ( f ( n ))

转置对称性： f ( n ) = O ( g ( n ))当且仅当 g ( n ) = Ω ( f ( n )) f ( n ) = o ( g ( n ))当且仅当 g ( n ) = ω ( f ( n ))

 

II. 主方法和递归树方法

Master Method

• T(n) = aT(n/b) +h(n)
• a>=1; b>1;h(n):不参与递归的复杂度函数

实际用法 判断n^log b (a)与h(n)的大小关系

定理一：>Θ(h(n))  : 复杂度       Θ(n^(log b (a)))

定理二：= Θ(h(n)) : 复杂度       Θ(h(n)*lg(n))

定理三：<Θ(h(n))  : 复杂度       Θ(h(n))

例子:

(1). T(n) = 9T(n/3) + n

a = 9   b = 3     n^log b (a) = n^log3(9) = n^2

n^2 > n           利用定理1   Θ(n^2)

(2) T(n) = T(2n/3)  + 1

a = 1    b =  3/2    n^log b (a) = n^log 3/2 (1) = 1

1 = h(n)             利用定理2   Θ(1*lgn)

(3) T(n) = 3T(n/4)  + nlgn

a = 3    b =  4    n^log b (a) = n^log 4 (3)

n^log 4 (3) < h(n)     利用定理3   Θ(nlgn)

Recursion Tree Method

主要是把递归式转换成树的形式，则利用树的数学概念和特性可以知道树高和叶子结点个数，从而可以求解出算法的复杂度。当然这种方法更合适你去验证自己的结论，因为是严格的证明过程。

 

谷歌上面找了一个代换法来解决递归树的证明PPT，直接搬运过来翻译。（借鉴自：MSC:introduction to Algorithm）

代换法解决递归树包括2步

①  猜测解决的规模形式大小

②用数学归纳法找到常量并证明方法可用

• 1 将递归放进树里面

假设递归式:  T(n) = 3T(n/4) + cn^2    [c是常数]

递归式里面  如 T(n) = aT(n/b) + h(n)

a是分解后的子规模 b是把和h(n)的规模的式子分解为原来的1/b

继续递归下去

T（n/4） = 3T(n/16) + c(n/4)^2

 

接下去递归

• 计算每一层的cost

计算每一层的cost之和

如果要约分分母，如果有 n = 16的话

或者 这棵树高度至少为2   如果  n>=16 = 4^2

对于  n = 4^k   k = log4(n)   可以得

 

 

如果你个有穷和为

如果要找到一般式 归纳 作差法：

求出Sn的一般式子

对于刚刚的式子 r的位置应该是 3/16.所以可以变换成

对于T（n）<=dn^2的式子 有 上式

不考虑log4(n) 则有

 

尝试使用递归树

第二个算法导论的笔记就写到这吧！