源码学院算法复杂度分析

1、算法复杂度分析 背景 大 O记号 目录 为什么讨论算法的复杂度？ 算法两个主要方面： 正确：算法功能与问题要求一致？ 成本：运行时间 + 所需存储空间 = 如何度量？ + 如何比较？ 算法复杂度分析的动机 如何度量： 设计的这个算法如何？跑得是不是足够快？ 随着问题规模的增长会怎样变化了？ 如何比较？ 同一个问题有多种不同的算法，如何判断其优劣了？ 为什么讨论算法的复杂度？ 直接想法 实验测试 把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大 小 实验测试难以准备反映算法的效率 - 测试环境和测试数据各异 不同的算法可能适应不同的输入规模 不同的算法可能适应不同类型的输入 同

2、一个算法，可能由不同的程序员、用不同的语言、由不同的编译器编译 同一个算法，可能被运行在不同的OS、不同体系结构的计算机上 为了给出一个客观的评判断，需要抽象出一个理解的计算模型 不依赖于上述各种具体因素，准确测量和评价算法 RAM(Random Access Model) 1. 指令一条接着一条执行（串行） 2. 指令包含了真实计算机的常见指令，例如： 算术指令（加法，减法，乘法，除法，取余，向下取整，向上取整） 数据移动指令（装入，存储，复制） 控制命令（条件与无条件转移、子程序调用与返回） 3. 上述每条指令所用的时间均为常数 在RAM模型中，算法的运行时间就与算法需要执行的指令操作次数

3、成正 比，记为T(n)，即算法为求解规模为n的问题，所需要执行的指令操作次 数。 RAM(Random Access Model) int hello() System.out.println(Hello, World!n); / 需要执行 1 次 return 0; / 需要执行 1 次 T(n) = 2 int hello(int n) for(int i=0; in; i+) / 需要执行 (n + 1) 次 System.out.println(Hello, World!n); / 需要执行 n 次 return 0; / 需要执行 1 次 int hello(int n) for(i

4、nt i=0; in; i+) / 需要执行 (n + 1) 次 System.out.println(Hello, World!n); / 需要执行 n 次 for(int i=0; in; i+) / 需要执行 (n + 1) 次 for(int j=0; j= c 时 T(n) b 0 如果一个算法的执行次数是如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时，那么只保留最高次项，同时 忽略最高项的系数后得到函数忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就，此时算法的时间复杂度就 是是 O(f(n) T(n) = n + 1 + n + n+ 1+(2n+1)*

5、n + n*n = 3n*n + 4n + 2 O(f(n)= O(n*n) 其他记号 Big O void aFunc(int n) for(int i = 0; i n; i+) printf(Hello, World!n); void aFunc(int n) for(int i = 0; i n; i+) for(int j = 0; j n; j+) printf(Hello, World!n); T(n) = n+1+1 = n+2 O(n) T(n) = n +n2 + n2= 2n2+2 O(n2) Big O void aFunc(int n) for(int i = 0;

6、i n; i+) for(int j = 0; j n; j+) printf(Hello, World!n); for(int j = 0; j = 0) for(int i = 0; i n; i+) for(int j = 0; j n; j+) printf(输入数据大于等于零n); else for(int j = 0; j n; j+) printf(输入数据小于零n); O(n2) Big O void aFunc(int n) for (int i = 2; i n; i+) i *= 2; printf(%in, i); T(n) = 2lgn O(lgn) 16 *16 *

7、4 Big O long aFunc(int n) /Fab if (n = 1) return 1; else return aFunc(n - 1) + aFunc(n - 2); T(N) = T(N-1) + T(N-2) (复杂度是多少？） 复杂度分析-递归与主定理 主定理示例 快速排序: Tn = 2Tn/2 + O(n) 对比主定理， T n = aTn/b + f (n) 快速排序中：a = 2, b = 2, f(n) = O(n) 故其复杂度为：平均的复杂度O(nlogn) 最坏：o(n2) n O(n) n/2n/2 常数阶O(1) Int sum(int n) Int

8、sum = 0; For(int i=1; i=n; i+) O(n) sum+=I; Return sum; Int sum(int n) return n*(n+1)/2; O(1) 对数阶O(logn) 多项式阶O(nc) 指数阶O(2n) 几种不同类型的时间复杂度 最好情况时间复杂度（best case time complexity）O(1) 最坏情况时间复杂度（worst case time complexity）O(n) 平均情况时间复杂度（average case time complexity）O(n) 均摊时间复杂度（amortized time complexity） ArrayList 可动态扩容的一个数组 Add: O(1) 当扩容时，需要O(n) N*O(1) + O(n) = O(1) int sea