时间复杂度和空间复杂度

数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢？这里就要用到我们今天要讲的内容：时间、空间复杂度分析。

为什么需要复杂度分析

通常，对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础上，第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。因此，作为程序员，掌握基本的算法时间复杂度分析方法是很有必要的。

算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。

事后统计的方法

这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。但这种方法显然是有很大缺陷的：

(1). 必须依据算法事先编制好程序，这通常需要花费大量的时间和精力。如果编制出来发现它根本是很糟糕的算法，不是竹篮打水一场空吗？

(2). 时间的比较依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣。要知道，现在的一台四核处理器的计算机，跟当年286、386、486等老爷爷辈的机器相比，在处理算法的运算速度上，是不能相提并论的；而所用的操作系统、编译器、运行框架等软件的不同，也可以影响它们的结果；就算是同一台机器，CPU使用率和内存占用情况不一样，也会造成细微的差异。

(3). 算法的测试数据设计困难，并且程序的运行时间往往还与测试数据的规模有很大关系，效率高的算法在小的测试数据面前往往得不到体现。比如10个数字的排序，不管用什么算法，差异几乎是零。而如果有一百万个随机数字排序，那不同算法的差异就非常大了。那么我们为了比较算法，到底用多少数据来测试，这是很难判断的问题。

基于事后统计方法有这样那样的缺陷，我们考虑不予采纳。

事前分析估算的方法

因事后统计方法更多的依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。

在编写程序前，依据统计方法对算法进行估算。一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

(1). 算法采用的策略、方法；
(2). 编译产生的代码质量；
(3). 问题的输入规模；
(4). 机器执行指令的速度。

一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。

函数的渐近增长

算法对比1

我们现在来判断一下，以下两个算法A和B哪个更好。假设两个算法的输入规模都是n，算法A要做2n+3次操作，你可以理解为先有一个n次的循环，执行完成后，再有一个n次循环，最后有三次赋值或运算，共2n+3次操作。算法B要做3n+1次操作。你觉得它们谁更快呢？
准确说来，答案是不一定的，如下图所示。

当n=1时，算法A效率不如算法B（次数比算法B要多一次）。而当n=2时，两者效率相同；当n>2时，算法A就开始优于算法B了，随着n的增加，算法A比算法B越来越好了（执行的次数比B要少）。于是我们可以得出结论，算法A总体上要好过算法B。

此时我们给出这样的定义，输入规模n在没有限制的情况下，只要超过一个数值N，这个函数就总是大于另一个函数，我们称函数是渐近增长的。
函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于

从中我们发现，随着n的增大，后面的+3还是+1其实是不影响最终的算法变化的，例如算法A′与算法B′，所以，我们可以忽略这些加法常数项。

算法对比2

我们来看第二个例子，算法C是4n+8，算法D是$2n^2+1$，如下图所示。

当n≤3的时候，算法C要差于算法D（因为算法C次数比较多），但当n>3后，算法C的优势就越来越优于算法D了，到后来更是远远胜过。而当后面的常数去掉后，我们发现其实结果没有发生改变。甚至我们再观察发现，哪怕去掉与n相乘的常数，这样的结果也没发生改变，算法C′的次数随着n的增长，还是远小于算法D′。也就是说，与最高次项相乘的常数并不重要。

算法对比3

我们再来看第三个例子。算法E是$2n^2+3n+1$，算法F是$2n^3+3n+1$，如下图所示。

当n=1的时候，算法E与算法F结果相同，但当n>1后，算法E的优势就要开始优于算法F，随着n的增大，差异非常明显。通过观察发现，最高次项的指数大的，函数随着n的增长，结果也会变得增长特别快。

算法对比4

我们来看最后一个例子。算法G是$2n^2$，算法H是3n+1，算法I是$2n^2+3n+1$，如下图所示。

这组数据应该就看得很清楚。当n的值越来越大时，你会发现，3n+1已经没法和2n2的结果相比较，最终几乎可以忽略不计。也就是说，随着n值变得非常大以后，算法G其实已经很趋近于算法I。于是我们可以得到这样一个结论，判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。

判断一个算法好不好，我们只通过少量的数据是不能做出准确判断的。根据刚才的几个样例，我们发现，如果我们可以对比这几个算法的关键执行次数函数的渐近增长性，基本就可以分析出：某个算法，随着n的增大，它会越来越优于另一算法，或者越来越差于另一算法。这其实就是事前估算方法的理论依据，通过算法时间复杂度来估算算法时间效率。

算法的时间复杂度

算法的时间复杂度的定义

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：
T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。

这样用大写O( )来体现算法时间复杂度的记法，我们称之为大O记法。
一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。
O(1)叫常数阶、O(n)叫线性阶、O($n^2$)叫平方阶，当然，还有其他的一些阶，我们之后会介绍。

推导大O阶方法

那么如何分析一个算法的时间复杂度呢？即如何推导大O阶呢？我们给出了下面的推导方法，基本上，这也就是总结前面我们举的例子。
推导大O阶：

1．用常数1取代运行时间中的所有加法常数。
2．在修改后的运行次数函数中，只保留最高阶项。
3．如果最高阶项存在且不是1，则去除与这个项相乘的常数。

常见时间复杂度

常数阶

int sum = 0 ; n = 100;        /*执行一次*/
sum = (1+n)*n/2;              /*执行一次*/
printf("%d",sum);             /*执行一次*/

这个算法的运行次数函数是f(n)=3。根据我们推导大O阶的方法，第一步就是把常数项3改为1。在保留最高阶项时发现，它根本没有最高阶项，所以这个算法的时间复杂度为O(1)。

另外，我们试想一下，如果这个算法当中的语句sum=(1+n)*n/2有10句，即：

int sum = 0 ; n = 100;       /*执行一次*/
sum = (1+n)*n/2;             /*执行第1次*/
sum = (1+n)*n/2;             /*执行第2次*/
sum = (1+n)*n/2;             /*执行第3次*/
sum = (1+n)*n/2;             /*执行第4次*/
sum = (1+n)*n/2;             /*执行第5次*/
sum = (1+n)*n/2;             /*执行第6次*/
sum = (1+n)*n/2;             /*执行第7次*/
sum = (1+n)*n/2;             /*执行第8次*/
sum = (1+n)*n/2;             /*执行第9次*/
sum = (1+n)*n/2;             /*执行第10次*/
printf("%d",sum);            /*执行一次*/

事实上无论n为多少，上面的两段代码就是3次和12次执行的差异。这种与问题的大小无关（n的多少），执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶。
注意：不管这个常数是多少，3或12，都不能写成O(3)、O(12)，而都要写成O(1)，这一点要特别注意。
此外，对于分支结构而言，无论真假执行的次数都是恒定不变的，不会随着n的变大而发生变化，所以单纯的分支结构（不在循环结构中），其时间复杂度也是O(1)。

线性阶

线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常需要确定某个特定语句或某个语句集运行的次数。因此，我们要分析算法的复杂度，关键就是要分析循环结构的运行情况。
下面这段代码，它的循环的时间复杂度为O(n)，因为循环体中的代码须要执行n次。

int i;
for (i = 0; i < n; i++)
{
    /* 时间复杂度为O(1)的程序步骤序列 */
}

对数阶

下面的这段代码，时间复杂度又是多少呢？

int count = 1;
while (count < n)
{
    count = count * 2;
    /* 时间复杂度为O(1)的程序步骤序列 */
}

由于每次count乘以2之后，就距离n更近了一分。也就是说，有多少个2相乘后大于n，则会退出循环。由$2^x=n$得到$x=\log_2n$。所以这个循环的时间复杂度为O($\log n$)。

平方阶

下面例子是一个循环嵌套，它的内循环刚才我们已经分析过，时间复杂度为O(n)。

int i, j;
for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        /* 时间复杂度为O(1)的程序步骤序列 */
    }
}

而对于外层的循环，不过是内部这个时间复杂度为O(n)的语句，再循环n次。所以这段代码的时间复杂度为O($n^2$)。

如果外循环的循环次数改为了m，时间复杂度就变为O(m×n)。

int i, j;
for (i = 0; i < m; i++)
{
    for (j = 0; j < n; j++)
    {
        /* 时间复杂度为O(1)的程序步骤序列 */
    }
}

所以我们可以总结得出，循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。

那么下面这个循环嵌套，它的时间复杂度是多少呢？

int i, j;
for (i = 0; i < n; i++)
{
    /* 注意j = i 而不是0 */
    for (j = i; j < n; j++)  
    {
        /* 时间复杂度为O(1)的程序步骤序列 */
    }
}

由于当i=0时，内循环执行了n次，当i=1时，执行了n-1次，……当i=n-1时，执行了1次。所以总的执行次数为：
$n+(n-1)+(n-1)+…+1 = n(n+1)/2 = n^2/2 + n/2$
用我们推导大O阶的方法，第一条，没有加法常数不予考虑；第二条，只保留最高阶项，因此保留n2/2；第三条，去除这个项相乘的常数，也就是去除1/2，最终这段代码的时间复杂度为O($n^2$)。

常见的时间复杂度

执行次数函数	阶	术语描述
12	O(1)	常数阶
2n+3	O(n)	线性阶
3n2 +2n+1	O($n^2$ )	平方阶
5log2 n+20	O($\log n$)	对数阶
2n+3nlog2 n+19	O($n\log n$)	nlogn阶
6n3+2n2 +3n+4	O($n^3$ )	立方阶
2n	O($2^n$ )	指数阶

常用的时间复杂度所耗费的时间从小到大依次是：
$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$

算法的空间复杂度

算法的空间复杂度定义

一个程序的空间复杂度是指运行完一个程序所需内存的大小，利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分：

（1）固定部分：这部分空间的大小与输入/输出的数据的个数多少、数值无关，主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间，这部分属于静态空间。
（2）可变空间：这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等，这部分的空间大小与算法有关。

我们在写代码时，完全可以用空间来换取时间，比如说，要判断某某年是不是闰年，你可能会花一点心思写了一个算法，而且由于是一个算法，也就意味着，每次给一个年份，都是要通过计算得到是否是闰年的结果。还有另一个办法就是，事先建立一个有2050个元素的数组（年数略比现实多一点），然后把所有的年份按下标的数字对应，如果是闰年，此数组项的值就是1，如果不是值为0。这样，所谓的判断某一年是否是闰年，就变成了查找这个数组的某一项的值是多少的问题。此时，我们的运算是最小化了，但是硬盘上或者内存中需要存储这2050个0和1。
这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好，其实要看你用在什么地方。

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

常见的空间复杂度

常数阶

int fun(int n)
{   
    int i，j，k，s; 
    s=0;
    for (i=0;i<=n;i++)           
        for (j=0;j<=i;j++)      
            for (k=0;k<=j;k++)     
                s++; 
    return(s);
}

由于算法中临时变量得个数与问题规模n无关，所以空间复杂度均为S(n) = O(1)

线性阶

void fun(int a[]，int n，int k) 
//数组a共有n个元素
{   
    int i;
    
	if (k==n-1)
	{
        for (i=0;i<n;i++)　　
            printf(“%d\n”，a[i]);  //执行n次
	}
    else
    {  
        for (i=k;i<n;i++)
            a[i]=a[i]+i*i;    　　//执行n-k次
        fun(a，n，k+1);
    }
}

此方法属于递归算法，每次调用本身都要分配空间，fun(a,n,0)的空间复杂度为O(n)。S(n) = O(g(1*n))
若写成非递归算法，代码一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。

常见数据结构的空间复杂度

时间复杂度、空间复杂度举例分析

二分法查找

二分查找的非递归算法

template<typename T>  
T* BinarySearch(T* array,int number,const T& data)  //data要查找的数，number查找范围长度，array要查找的数组
{  
       assert(number>=0);  
       int left = 0;  
       int right = number-1;  
       while (right >= left)  
       {  
              int mid = (left&right) + ((left^right)>>1);  
              if (array[mid] > data)  
              {  
                     right = mid - 1;  
              }  
              else if (array[mid] < data)  
              {  
                     left = mid + 1;  
              }  
              else  
              {  
                     return (array + mid);  
              }  
       }  
       return NULL;  
}

分析：
假设最坏情况下，循环X次之后找到，则：$2^x=n; x=\log_2n$
循环的基本次数是$\log_2N$，所以: 时间复杂度是O(logN);
由于辅助空间是常数级别的所以：空间复杂度是O(1);

二分查找的递归算法

template<typename T>  
T* BinarySearch(T* left,T* right,const T& data)  
{  
       assert(left);  
       assert(right);  
       if (right >=left)  
       {  
              T* mid =left+(right-left)/2;  
              if (*mid == data)  
                     return mid;  
              else  
                     return *mid > data ? BinarySearch(left, mid - 1, data) : BinarySearch(mid + 1, right, data);  
       }  
       else  
       {  
              return NULL;  
       }  
}

假设最坏情况下，循环X次之后找到，则：$2^x=n; x=\log_2n$
递归的次数和深度都是$\log_2N$,每次所需要的辅助空间都是常数级别的：
时间复杂度:O(log2N)；
空间复杂度：O(log2N )。

斐波那契数

这里我借用百度百科上的解释：斐波那契数，亦称之为斐波那契数列（意大利语： Successione di Fibonacci)，又称黄金分割数列、费波那西数列、费波拿契数、费氏数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*），用文字来说，就是斐波那契数列列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。特别指出：0不是第一项，而是第零项。在这个斐波那契数列中的数字，就被称为斐波那契数
求第N个斐波那契数比较简单可以直接套用公式n = 0,1 时，fib(n) = 1；n > =2 时，fib(n) = fib(n-2) + fib(n-1)在计算时有两种算法：递归和非递归。如下：

第N个斐波那契数的非递归算法

//非递归算法
long long fib1(size_t N) 
{
    long long a = 0, b = 1, c = 0;
    if (N < 2) 
	{
        return N;
    }
    else 
	{
        for (long long i = 2; i <= N; ++i) 
		{
            c = a + b;
            a = b;
            b = c;
        }
    }
    return c;
}
int main()
{
    printf("%lld", fib1(10));
    getchar();
    return 0;
}  //此算法最大的优点是不存在重复计算，故效率比递归算法快的多得多。

使用非递归算法求到第n个斐波那契数，是从第2个数开始，将前两个数相加求求后一个数，再将后一个数赋值给前一个数，再计算前两个数相加的结果。依次类推直到第n个数，用n-1个数和n-2个数相加求出结果，这样的好处是，我们只计算了n-1次就求出了结果，即时间复杂度为O(n)；我们以代码中测试数10为例详解求第十个数的过程。当N=10时，进入函数首先判断，然后走下面的分支开始计算。

计算了N-1次，得出了结果所以时间复杂度是O（N）。
此函数内部最多时一共开辟了a, b, c, i四个变量空间复杂度是常数，即为O（1）。

第N个斐波那契数的递归算法

//递归算法
long long fib2(size_t N) 
{
    if (N < 2) 
        return N;
    return fib2(N - 1) + fib2(N - 2);
}
int main()
{
    printf("%lld", fib2(10));
    getchar();
    return 0;
}

在递归算法中，求解fib2(n)，把它推到求解fib2(n-1)和fib2(n-2)。也就是说，为计算fib2(n)，必须先计算
fib2(n-1)和fib2(n-2)，而计算fib2(n-1)和fib2(n-2)，时按照表达式及计算法则，需先计算又必须先计算fib2(n-1)，而fib2(n-1)由fib2(n-2)和fib2(n-3)计算得来，而这之中的和fib2(n-2)由fib2(n-3)和fib2(n-4)计算得来……依次类推，表面上看不出有何复杂度，但是仔细分析可知，每一个计算fib2(n)的分支都会衍生出计算直至(1)和fib(0)，也就是说每个分支都要自己计算数本身到1的斐波那契数列，这样就增加了庞大且冗杂的运算量，还是以10 为例详细计算说明。

图中数字代表第N个斐波那契数，图中没有全部将计算步骤画出来，但是已经足够说明问题，它的每一步计算都被分成计算前两个斐波那契数，以此类推。那么这就形成了一颗二叉树，虽然不是满二叉树，但是我们分析的是最坏时间复杂度，而且只要估算出来递归次数随N增长的趋势即可，故可以近似将它看成满二叉树，其中的节点数就是计算的次数，也就是复杂度，由公式：节点数=$2^h-1$（h为树的高度）可得O（$2^n$）。
递归的时间复杂度是： 递归次数*每次递归中执行基本操作的次数，所以时间复杂度是： O($2^N$)

递归最深的那一次所耗费的空间足以容纳它所有递归过程。递归产生的栈侦是要销毁的，所以空间也就释放了，要返回上一层栈侦继续计算+号后面的数，所以它所需要的空间不是一直累加起来的，之后产生的栈侦空间都小于递归最深的那一次所耗费的空间。
递归的深度*每次递归所需的辅助空间的个数 ，所以空间复杂度是：O(N)

注意：

1.空间复杂度相比时间复杂度分析要少。
2.对于递归算法来说，代码一般都比较简短，算法本身所占用的存储空间较少，但运行时需要占用较多的临时工作单元，并且可能导致栈溢出，当需要计算的数稍大一点，就需要很长的计算时间，因此需要灵活使用递归

参考

《大话数据结构》
斐波那契数与二分法的递归与非递归算法及其复杂度分析