第2章:算法分析

一. 数学基础

1.几个数学定义:其中使用最多的是大O符号

大O:增长率小于等于(上界)

大Ω:增长率大于等于(下界)

大Θ:增长率等于

小o:增长率小于

2.洛必达法则

计算极限时,分子和分母都趋近于0/∞,则可以对分子分母求导来计算.

3. 常用求导

二.复杂度法则

法则1:如果S(N) = O(f(N)), T(N) = O(g(N))

那么(a) : S(N)+T(N) = O(f(N) + g(N)); 直观地和非正式地可以写成max(O(f(N)),O(g(N)));

        (b) : S(N)*T(N) = O(f(N) *g(N));

法则2:如果T(N)是一个k次多项式, 则T(N) = O(N^k)

法则3:对任意常数k,(logN)^k = O(N),可见对数增长的非常缓慢