文档介绍：计算机程序算法分析之算法概述
第1页，此课件共42页哦
关于学****与研究
Research (研究）
Arch
Search
Research
算法－－寻找解的过程s)) = O (g(n)) (g(n))
第14页，此课件共42页哦
渐近分析记号在等式和不等式中的意义
f(n)= (g(n))的确切意义是：f(n) (g(n))。
一般情况下，等式和不等式中的渐近记号(g(n))表示(g(n))中的某个函数。
例如：2n2 + 3n + 1 = 2n2 + (n) 表示
2n2 +3n +1=2n2 + f(n)，其中f(n) 是(n)中某个函数。
等式和不等式中渐近记号O,o, 和的意义是类似的。
第15页，此课件共42页哦
渐近分析中函数比较
f(n)= O(g(n)) a b;
f(n)= (g(n)) a b;
f(n)= (g(n)) a = b;
f(n)= o(g(n)) a < b;
f(n)= (g(n)) a > b.
第16页，此课件共42页哦
渐近分析记号的若干性质
（1）传递性：
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))；
第17页，此课件共42页哦
（2）反身性：
f(n)= (f(n))；
f(n)= O(f(n))；
f(n)= (f(n)).
（3）对称性：
f(n)= (g(n)) g(n)= (f(n)) .
（4）互对称性：
f(n)= O(g(n)) g(n)= (f(n)) ；
f(n)= o(g(n)) g(n)= (f(n)) ；
第18页，此课件共42页哦
（5）算术运算：
O(f(n))+O(g(n)) = O(max{f(n),g(n)}) ；
O(f(n))+O(g(n)) = O(f(n)+g(n)) ；
O(f(n))*O(g(n)) = O(f(n)*g(n)) ；
O(cf(n)) = O(f(n)) ；
g(n)= O(f(n)) O(f(n))+O(g(n)) = O(f(n)) 。
第19页，此课件共42页哦
规则O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 的证明：
对于任意f1(n) O(f(n)) ，存在正常数c1和自然数n1，使得对所有n n1，有f1(n) c1f(n) 。
类似地，对于任意g1(n) O(g(n)) ，存在正常数c2和自然数n2，使得对所有n n2，有g1(n) c2g(n) 。
令c3=max{c1, c2}， n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。
则对所有的 n n3，有
f1(n) +g1(n) c1f(n) + c2g(n)
c3f(n) + c3g(n)= c3(f(n) + g(n))
c32 max{f(n),g(n)}
= 2c3h(n) = O(max{f(n),g(n)}) .
第20页，此课件共42页哦
算法渐近复杂性分析中常用函数
（1）单调函数
单调递增：m n f(m) f(n) ;
单调递减：m n f(m) f(n);
严格单调递增：m < n f(m) < f(n);
严格单调递减：m < n f(m) > f(n).
（2）取整函数
x ：不大于x的最大整数；
x ：不小于x的最小整数。
第21页，此课件共42页哦
取整函数的若干性质
x-1 < x x x < x+1；
n/2 + n/2 = n;
对于n 0，a,b>0，有：
n/a /b = n/ab ;
n/a /b = n/ab ;
a/b (a+(b-1))/b;
a/b (a-(b-1))/b;
f(x)= x , g(x)= x 为单调递增函数。
第