本节书摘来自异步社区《趣题学算法》一书中的第0章0.5节算法分析，作者徐子珊,更多章节内容可以访问云栖社区“异步社区”公众号查看。
0.5 算法分析
解决同一问题的不同算法所消耗的计算机系统的时间（占用处理器的时间）和空间（占用内部存储器空间）资源量可能有所不同。算法运行所需要的资源量称为算法的复杂性。一般来说，解决同一问题的算法，需要的资源量越少，我们认为越优秀。计算算法运行所需资源量的过程称为算法复杂性分析，简称为算法分析。理论上，算法分析既要计算算法的时间复杂性，也要计算它的空间复杂性。然而，算法的运行时间都是消耗在已存储的数据处理上的，从这个意义上说，算法的空间复杂性不会超过时间复杂性。出于这个原因，人们多关注于算法的时间复杂性分析。本书中除非特别说明，所说的算法分析，局限于对算法的时间复杂性分析。
算法的运行时间，就是执行基本操作的次数。所谓基本操作，指的是计算机能直接执行的最简单的不可再分的操作。例如对数据进行的算术运算和逻辑运算，以及将数据存储于内存的某个单元。考虑算法0-1，当序列A的元素个数为N时：
GET-THE-INVERSION(A)
1 N← length[A] 耗时1个单位
2 count←0 耗时1个单位
3 for j← N downt o 2 耗时N个单位
4 do for i←1 to j-1 耗时=N(N+1)/2-1个单位
5 do if A[i]>A[j] 耗时=N(N+1)/2个单位
6 then count←count+1 耗时不超过=N(N+1)/2个单位
7 return count +） 耗时1个单位
3N2/2+N/2+2
具体地说，第1、2、7行各消耗1个单位时间，总数为3，第3行做N次j与2的比较耗时N，第4行作为外层循环的循环体中一个操作，每次被执行时做j次i与j−1的比较，所以总耗时为N+(N−1)+…+2=N(N+1)/2-1。相仿地，第5、6行作为内层循环的循环体每次被重复j−1次，但它们也在外层循环的控制之下，所以两者的耗时为2(1+ 2+…+N−1)=N(N−1)。把它们相加得到
N+3+N(N+1)/2-1+N(N-1)
=N+2+N2/2+N/2+N2-N
=3N2/2+N/2+2
一般而言，算法的时间复杂性与输入的规模（算法0-1中序列A的元素个数）相关。规模越大，需要执行的基本操作就越多，当然运行时间就越长。此外，即使问题输入的规模一定，不同的输入也会导致运行时间的不同。对固定的输入规模，使得运算时间最长的输入所消耗的运行时间称为算法的最坏情形时间。通常，人们以算法的最坏情形时间来衡量算法的时间复杂性，并简称为算法的运行时间。例如，在上述的算法0-1的分析中，第3～6行的嵌套循环的循环体的每次重复，第6行并非必被执行，所以我们说其耗时“不超过sumnolimits_{i=1}^{N-1}{i}=N(N+1)/2个单位”。但我们要考虑的是最坏情形时间，所以运行时间是按N(N+1)/2加以计算的。
对于算法的输入规模为n的运行时间，常记为T(n)。以算法0-1的GET-THE- INVERSION(A)过程为例，数组A[1..N]的元素个数N越大，运行时间T(N)=3N2/2+N/2+2的值就越大。
对算法0-2而言，设其对输入规模为N的运行时间为T(N)。
GET-THE-INVERSION(A, N)
1 if N<2 耗时1个单位
2 then return 耗时不超过1个单位
3 for i←1 to N-1 耗时N个单位
4 do if A[i]>A[N] 耗时N-1个单位
5 then count←count+1 耗时不超过N-1个单位
6 GET-THE-INVERSION(A, N-1) +） 耗时T(N-1)
T(N)=T(N−1)+3N-1
这是一个在等式两端都含有未知式T的方程，称为递归方程。递归方程可以用迭代法来解，即
T(N)=T(N-1)+3N-1
=T(N-2)+3(N-1)+3N-2
=T(N-3)+3(N-2)+3(N-1)+3N-3
……
=T(1)+3*2+…+3(N-1)+3N-(N-1)
=2+3(1+2+3+…+N)-3-N+1
=3N(N+1)/2-N
=3N2/2+N/2
显然，这算法0-1的运行时间大同小异。注意，式中的T(1)指的是算法0-2的第2个参数N=1时的运行时间。显然，这将仅执行其中1～2行的操作，耗时为2个单位。
