算法分析与设计analysisanddesignofalgorithmlesson03.pdf

算法分析与设计 Analysis and Design of Algorithm Lesson 03 要点回顾  算法复杂度的概念  时间复杂度  最坏情况时间复杂度W(n)  平均情况时间复杂度A (n)  三大衡量标准 1. 渐近上界记号O  问题规模 2. 渐近下界记号  基本运算 3. 紧渐近界记号  计量函数 4. 非紧上界记号o  复杂度的渐近性态 5. 非紧下界记号  略去低阶项所留下的主项  五个渐近分析记号 72 渐近分析的记号  渐近上界记号O  若存在两个正的常数c和n ，使得对所有n ≥n ， 0 0 都有：f (n)≤c ×g(n) ，则称f (n) = O(g(n)) 执 c ×g (n) 行 次 f (n) 数 n0 之前的 2 例子：f (n) =32n +17n+1 情况无关 紧要 c n0 g (n) =? n 0 问题规模n 73 O的运算性质         O f O g O max f , g        O f O g O f g        O f O g O f g             如果 g N O f N O f O g O f        O cf N O f N 其中c是一个正的常数    f O f 下面考察性质的证明： 74 性质：        O f O g O max f , g     证明：设F