数据结构算法分析算法分析概述算法分析分析算法占用的两类资源CPU时间 → 时间性能分析内存空间 → 空间性能分析时间复杂度一般是看循环几次。时间复杂度越高时间用的就越长。算法分析的目的分析算法的时空效率以便改进算法性能。算法效率的度量时间复杂度空间复杂度例题算法分析的目的是A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和可行性答案C示例设计算法求 1(12)(123)…(12…n), n2版本1双重循环intSum1(intn){intsum0;for(inti1;in;i){for(intj1;ji;j){sumsumj;}}returnsum;}版本2一重循环intSum2(intn){intsum0;ints0;for(inti1;in;i){ssi;sumsums;}returnsum;}对比双重循环时间复杂度更高一重循环优化后效率更好。1.3.2 算法时间复杂度分析一个算法由控制结构顺序、分支、循环 和原操作构成。原操作固有数据类型的操作如赋值、比较、算术运算 - * /顺序结构按照顺序依次处理分支结构根据条件判断改变执行路径循环结构当条件成立时反复执行指定处理示例代码voidfun(inta[],intn){for(inti0;in;i){a[i]2*i;for(intj0;ji;j){printf(%d ,a[i]);}printf(\n);}}两种算法分析方式① 事后分析统计方法编写对应程序统计实际运行时间。缺点和机器性能有关高性能计算机 vs 单片机和编程语言有关高级语言执行效率低和编译产生的机器指令质量有关有些算法不能事后统计如导弹控制系统② 事前估算分析方法抛开机器、语言等外部因素把算法执行时间看作问题规模n的函数。算法时间复杂度事前预估算法时间开销 T(n) 和问题规模 n 的关系。T time。时间复杂度记号 O前面这个O绝对不要忘记写T(n)O(f(n))读作T(n)是f(n)的大O阶含义随问题规模n增大算法执行时间的增长率和f(n)增长率相同。大O是渐近上界取最小的上界忽略常数因子、低阶项。例子语句频度计算//示例爱你算法voidlove(intn){inti1;while(in){printf(I love you\n);ii1;}printf(I love you More Than %d\n,n);}统计语句执行次数频度int i1; → 1次while(in) → n1次printf(“I love you\n”); → n次ii1; → n次printf(“I love you More Than %d\n”,n); →1次T(n)1(n1)nn1 3n3当n足够大常数项可以忽略就是这里的3并且这里的最高次幂前面的系数也可以省略就是这里的3n前面的系数3再eg:f(n)2n³3n²2n1这里只剩下n³它是最高次幂其他的都可以忽略。T(n)3n3 O(n)化简规则常数项可以忽略只保留最高次幂最高次幂前面的系数忽略。例T(n)n²3n1000 ⇒ O(n²)T(n)5n³999999 ⇒ O(n³)循环嵌套时间复杂度计算单层循环循环执行次数和n成正比 ⇒ O(n)两层嵌套循环内外循环都和n相关 ⇒ O(n²)三层嵌套循环 ⇒ O(n³)示例1两层循环voidfun(intn){inti,j;for(i1;in;i){for(j1;jn;j){printf(*);}}}外层循环n次内层循环每次n次总次数 n×n n²T(n)n²时间复杂度O(n²)示例2循环变量不断翻倍voidfun(intn){inti1;while(in){ii*2;}}i1,2,4,8,…,2ᵏ ≤ n2ᵏ ≤ n ⇒ k ≤ log₂n时间复杂度O(log n)最好、最坏、平均时间复杂度最坏时间复杂度最坏输入情况下算法的执行时间。考试最常考。最好时间复杂度最好输入情况下。平均时间复杂度所有输入等概率下的平均执行时间。做题默认求最坏时间复杂度。常见时间复杂度大小排序重点O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ)O(1)常数阶和n无关O(log n)对数阶O(n)线性阶O(n log n)线性对数阶O(n²)平方阶O(n³)立方阶O(2ⁿ)指数阶效率很差例题某算法时间复杂度为O(n²)表明该算法A.问题规模是n²B.执行时间等于n²C.执行时间与n²成正比D.问题规模与n²成正比答案C要说就说与它成正比。例题下面算法时间复杂度最高的是A.O(log₂n) B.O(n) C.O(n²) D.O(2ⁿ)答案D排序O(log₂n) O(n) O(n²) O(2ⁿ)例题真题count0;for(i1;in;i)for(j1;jn;j)count;时间复杂度O(n²)例题voidfun(intn){inti0,s0;while(sn){i;ssi;}}分析s123…i i(i1)/2 ni² ≈ 2n ⇒ i ≈ √(2n)时间复杂度O(√n)时间复杂度做题通用步骤记下来找出基本原操作最内层循环里面的语句统计基本操作执行次数得到 T(n)去掉常数、低次项、系数得到大O表示。多层循环看每层循环的次数相乘。小技巧一层循环O(n)两层嵌套O(n²)循环变量乘2/除2O(log n)空间复杂度空间复杂度算法执行过程中占用的存储空间记为 S(n)S(n)O(f(n))空间复杂度O(1)原地算法额外空间不随n变化。递归算法空间复杂度要看递归深度。背诵总结算法分析分析时间复杂度、空间复杂度。大O记号只看最高次项忽略常数、系数、低次项。常见复杂度大小O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ)单层循环 O(n)双层嵌套 O(n²)循环成倍增长 O(log n)考试优先求最坏时间复杂度。