渐近符号算法

1、渐近符号2.1 渐近符号算法运行时间主要取决于问题的规模，对于足够大的输入，算法运行时间表达式里的那些低阶项以及高阶项的常数系数等，主要受高阶项的制约。为了表示算法的渐进有效性，引入渐进符号以便表示算法的运行时间与输入规模之间的主要关系，即渐进时间复杂性，来衡量算法的好坏。渐进符号： 、O、 2符号符号: 对于给定的函数 g(n), 记(g(n) = f(n) : 存在三个正常数c1, c2, n0 ，对于任给nn0，满足0c1g(n) f(n)c2g(n)的函数集。并记f(n) =(g(n)，它表示f(n) 是(g(n)中的一个元素。定理：如果 存在，且 则必有f(n) =(g(n)。直观含

2、义： f(n) 与g(n)同阶。3注意： (g(n)的定义要求任意f(n) =(g(n)都是渐进非负的。4例2.1：已知 f (n) = 3n+ 3,证明f (n)= (n).例2.2：已知 f (n) = 1/2n2 - 3n ,证明f (n)= (n2).例2.3：已知 f (n) = 6n3,证明f (n)!=(n2).5几个结论渐近正函数的低阶项在估计其渐近界的时候可以被忽略掉；对于符号定义中涉及的两个常数c1和c2，只要选取c1等于一个比高阶项系数稍小的数，选取c2等于一个比高阶项系数稍大的数，就可以满足符号定义中的不等式；高阶项系数同样可以忽略，因为它的改变只会使高阶项的值发生常数

3、系数倍的改变。例： f(n) = an2 + bn + c， a, b, c 是常数且 a 0,则必有f(n) = (n2 )。6O符号O符号:对于给定的函数 g(n), 记O(g(n) = f(n) : 存在c和 n0 ，对于任意nn0，满足0f(n)cg(n)的函数集。并记f(n) =O(g(n)，它表示f(n) 是O(g(n)中的一个元素。定理：如果 存在，且 则必有f(n) =O(g(n)。直观含义： f(n) 的阶不高于g(n)的阶。7注意： O(g(n)的定义要求任意f(n) =O(g(n)都是渐进非负的。8推论：如果f(n) =(g(n) ，则必有f(n) = O(g(n) 。O

4、符号描述了时间复杂度f(n)的上界, 也就是描述算法运行的最坏运行时间。回顾：插入排序算法中主要有2重循环，for循环和while循环，他们最多各执行n次，所以最坏运行时间或者说时间复杂度上界为O(n2)。没有必要计算算法每一行执行的时间以及每行执行的次数，然后求和，只需要考虑算法中主要循环执行的次数即可。9符号符号：对于给定的函数 g(n), 记(g(n) = f(n) : 存在c和 n0 ，对于任意nn0，满足0cg(n) f(n)的函数集。并记f(n) = (g(n)，它表示f(n) 是(g(n)中的一个元素。定理：如果 存在，且 则必有f(n) = (g(n)。直观含义： f(n) 的

5、阶不低于g(n)的阶。10注意： (g(n)的定义要求任意f(n) = (g(n)都是渐进非负的。11渐进符号的性质定理2.1：对于f(n)和g(n), f(n) = (g(n) 当且仅当f(n) = O(g(n) 且 f(n) = (g(n). 证明：由定义即可证得。例：an2 + bn + c = (n2) ，a, b, c均为常数且a 0, 则必有an2 + bn + c = (n2) ，an2 + bn + c = O(n2).12渐进符号的性质定理2.2 ：对于f1(n)和f2(n) , 如果f1(n) =O(g1(n)， f2(n) =O(g2(n) ，则必有f1(n)+ f2(n)= O(maxg1 (n), g2(n) ) 。例： O(n2lgn)+O(n2)=O(n2lgn).推论：对于任意给定