算法分析包含两个方面 （1）正确性：不变性，单调性 （2）复杂度：时间，空间，稳定性

算法正确性的证明——以冒泡排序为例 算法是否必然会结束？ （1）不变性：k轮扫描后，k个最大元素必已就位 （2）单调性：k轮扫描，问题规模缩减至n-k 因此n次扫描后，算法必然终止，正确性得到证明

1、复杂度分析的方法： 迭代式：级数求和 递归式：递归跟踪 + 递推方程

2、复杂度分析几个常用到的级数： 1、算术级数(等差数列)： T ( n ) = 1 + 2 + 3 + . . . + n = n ( n + 1 ) / 2 = O ( n 2 ) T(n) = 1+2+3+...+n = n(n+1)/2 =O(n^2) T(n)=1+2+3+...+n=n(n+1)/2=O(n2)

2、幂方级数，结果比幂次高一阶： T 2 ( n ) = 1 2 + 2 2 + 3 2 + . . . + n 2 = n ( n + 1 ) ( 2 n + 1 ) / 6 = O ( n 3 ) T_2(n) = 1^2+2^2+3^2+...+n^2 = n(n+1)(2n+1)/6 =O(n^3) T2​(n)=12+22+32+...+n2=n(n+1)(2n+1)/6=O(n3) … T 4 ( n ) = O ( n 5 ) T_4(n) = O(n^5) T4​(n)=O(n5)

3、几何级数(等比数列的前n项和)，与末项同阶： T a ( n ) = a 0 + a 1 + . . . + a n = O ( a n ) T_a(n) = a^0 + a^1+...+a^n=O(a^n) Ta​(n)=a0+a1+...+an=O(an) 1 + 2 + 4 + . . . + 2 n = O ( 2 n ) 1+2+4+...+2^n=O(2^n) 1+2+4+...+2n=O(2n)

4、收敛级数，复杂度O(1) 1 + 1 / 2 2 + 1 / 3 2 + . . . + 1 / n 2 = O ( 1 ) 1+1/2^2+1/3^2+...+1/n^2 = O(1) 1+1/22+1/32+...+1/n2=O(1)

5、调和级数 1 + 1 / 2 + 1 / 3 + . . . + 1 / n = s e t a ( l o g n ) 1+1/2+1/3+...+1/n=seta(logn) 1+1/2+1/3+...+1/n=seta(logn)

6、对数级数 l o g 1 + l o g 2 + l o g 3 + . . . + l o g n = s e t a ( n l o g n ) log1+log2+log3+...+logn=seta(nlogn) log1+log2+log3+...+logn=seta(nlogn)

3、封底估计 一天≈10^5s 一生（100年）≈ 3*10^9s 使用冒泡排序对全国人口普查要花费多久？ 人口≈ 10^9 冒泡排序时间复杂度为 O ( n 2 ) O(n^2) O(n2) 因此，使用冒泡排序大概要进行10^18次计算，普通计算机估计每秒能进行10 ^9次运算，因此排好序大概要花费10 ^9s，大约为30年 而使用归并排序，则所用的时间用同样的方法估计则大约为30s。

迭代乃人工，递归方神通

1、递归的分类： 递归可分为两种类型： （1）减而治之：需要给出平凡的递归基 （2）分而治之：将原问题分成两个规模大体相当的子问题，分别求解子问题，得到原问题的解

2、迭代和递归的区别： 迭代计算数组和：for循环直接累加求和 递归计算数组和： （1）减而治之：return (n> 2; return sum(A,lo.mid) + sum(A,mid+1,hi);

3、递归时间复杂度求解—递归跟踪 （1）减而治之 所需时间为递归实例总数*每个递归实例所需时间 递归实例为：(sum(A,n)->sum(A,0)) 数组求和中每个递归实例需执行sum(A,n-1) + A[n-1]语句，sum(A,n-1)可以省略，计入尤其生成的递归实例中，本例中，每个递归实例需要O(1)的时间，因此总共复杂度为O(n)。 （2）分而治之 统计各层递归实例所需时间之和 第一层0个，第二层2个…最后一层2 ^(logn)个 每个递归实例时间复杂度为O(1)， 因此总的时间复杂度为O(n) 这里递归实例的情况符合几何级数，几何级数的阶数与末项同阶，因此只要考虑最底层就可以了，另外这里最底层的项数和元素个数相等，因此复杂度为O(n).

4、递归时间复杂度求解—递推方程 （1）减而治之： 数组求和的递推方程为：T(n)=T(n-1)+O(1)，T(0)=O(1) 递推方程的求解： 等式两边减n：T(n) - n= T(n-1) - (n-1) 可得：T(n)- n = T(0) = O(1) 因此：T(n)= O(1)+n = O(n) （2）分而治之： T(n) = 2*T(n/2) + O(1)

1、平均分析： 将数据结构各种操作的成为做加权取得平均性能 2、分摊分析 对数据结构实施足够多次操作，将总体成本分摊至单次操作