第1章 算法设计与分析.ppt

定理1.1 设 f 和g是定义域为自然数集合的函数. 如果 存在且等于某个常数c>0, 那么 f(n)=(g(n. (2) 如果 那么 f(n)=o(g(n. (3) 如果 那么 f(n)=(g(n. 有关定理 证明定理1.1 (1) 证 根据极限定义对于给定的正数 ? =c/2, 存在某个n0 只要 n?n0就有 对所有的n?n0 f(n?2cg(n. 从而推出 f(n)=O(g(n) 对所有