算法的时间复杂度和空间复杂度

算法效率的度量是对算法所需要的时间和空间进行估算，分别称为时间复杂度和空间复杂度。

时间复杂度

算法的时间效率称为算法的时间复杂度，它是问题规模n的某个函数，记作：T(n) = O(f(n))。

其中问题规模n是指输入量的多少，一般可以从问题描述中得到。如，数组元素的个数、矩阵的阶数等。f(n) 是问题规模n的某个函数。这里的O是Order的简写，意指数量级，表示随问题规模n的增大，算法执行时间的增长率和 f(n) 的增长率相同。

一个没有循环的算法基本运算次数与问题规模无关，记作O(1)，也称为常数阶。

常见的算法时间复杂度由小到大排列如下：

O(1) < O($\log_{2}n$) < O(n) < O($n\log_{2}n$) < O($n^2$) < O($n^3$) < … < O($c^n$) < O(n!)

时间复杂度的计算

不带循环

1	x++;//基本语句的执行次数为1，因此时间复杂度为O(1)

简单循环

int x = 0;//语句1，执行1次
for( int i = 0 ; i < n ; i++ ) {//语句2，i从0开始到n，执行了n+1次
    x+=i;//语句3，执行n次
}

因此，该算法的执行次数为T(n)=1+(n+1)+n=2n+2=O(n)，这种计算方式相对麻烦。

该算法的基本运算为循环中的语句3，它的执行次数为T(n)=n=O(n)。显然，这种计算方式比上面的简单得多，以后均采用这种方式分析算法的时间复杂度。

for(int i = 0 ; i < n ; i++) {//该循环执行n次
    for(int j = 0; j < n ;j++) {//该循环执行n次
        x++;
    }
}

显然，该算法的基本运算为x++，其执行了$n^2$次，因此该算法的时间复杂度为O($n^2$)。

void fun(int n) {
    int x=0;
    for(int i = 1 ; i < n ; i++) {//该循环执行n-1次
        for(int j = i + 1; j <= n ;j++) {//该循环执行n-(i+1)+1=n-i次
            x++;
        }
    }
}

如何计算该算法的时间复杂度呢？

显然，该算法的基本运算仍为x++，设x++语句执行次数为T(n)，则

$$T(n)=\sum_{i=1}^{n-1}\sum_{j=i+1}^n1=\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}=O(n^2)$$

复杂循环

void fun(int n) {
    int m = 0;
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 2*i ; j <= n ;j++) {
            m++;
        }
    }
}

该算法的基本运算为m++，设其执行次数为T(n)，如果按照上面的方法，则

$$T(n)=\sum_{i=1}^n\sum_{j=2i}^{n}1=\sum_{i=1}^{n}(n-2i+1)=(n+1)n-2\frac{n(n+1)}{2}=0$$

显然，这种做法是错误的，因为内循环从2i到n，即 i 必须满足: 2i ≤ n => $i<\frac{n}{2}$，因此正确的做法是：

$$T(n) = \sum_{i=1}^{\frac{n}{2}}\sum_{j=2i}^{n}1=\sum_{i=1}^{\frac{n}{2}}(n-2i+1)=(n+1)\frac{n}{2}-2\sum_{i=1}^{\frac{n}{2}}i$$

$$=(n+1)\frac{n}{2}-2\frac{(\frac{n}{2}+1)\frac{n}{2}}{2}=\frac{n^2}{4}=O(n^2)$$

需要递归

void fun(int a[],int n,int k) {
    int i;
    if(k==n-1) {
        for(i = 0 ; i < n ; i++) {
            printf("%d\n",a[i]);
        }
    } else {
        for(i = k ; i < n ; i++) {
            a[i] = a[i] + i * i;
        }
        fun(a,n,k+1);
    }
}

如何求fun(a,n,0)的时间复杂度呢？

设fun(a,n,k)的执行时间为T(n,k)，从而，fun(a,n,0)的执行时间为T(n)=T(n,0)。

$$T(n,k)=\begin{cases} n, & \text {k=n-1} \\ (n-k)+T(n,k+1), & \text{其他} \end{cases}$$

则，

T(n)=T(n,0)=n+T(n,1)=n+(n-1)+T(n,2)=…=n+(n-1)+…+2+T(n,n-1)

=$\frac{(n+2)(n-1)}{2}+n=\frac{n^2}{2}+\frac{3n}{2}-1=O(n^2)$

最好、最坏及平均时间复杂度

实际上，算法效率不仅仅依赖于问题的规模n，还与问题的初始输入有关。例如:

int fun(int a[],int n,int k) {//该算法用于在给定的数组a[]中查找k
    for(int i = 0 ; i < n ; i++) {
        if(a[i] == k) {
            return i;
        }
    }
    return -1;
}

循环体的执行次数，不仅与问题规模n有关，还与输入实例中a的各元素取值以及k的取值有关。在最坏的情况下，a中没有与k相等的元素，则循环体执行n次；在最好的情况下，a中的第一个元素a[0]等于K，则循环体执行1次。

故，该算法的最好时间复杂度为O(1)，最坏时间复杂度为O(n)。在这种情况下，可用最坏情况下的时间复杂度作为算法的时间复杂度，因为最坏情况下的时间复杂度是在任何输入实例上运行时间的上界。

当然，也可用平均时间复杂度来衡量算法，下面给出平均时间复杂度的定义：

设一个算法的输入规模为n，$D_n$是所有输入的集合，任一输入I∈$D_n$，p(I)是I出现的频率，有$\sum_{I∈D_n}P(I)=1$，T(I)是算法在输入I下所执行的基本运算次数，则该算法的平均时间复杂度为：

$$T(n)=\sum_{I∈D_n}{P(I)·T(I)}$$

显然，最坏时间复杂度为$$T(n)=\max_{I∈D_n}{T(I)}$$

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的度量。

一个算法在执行过程中所需要的存储空间包括以下3个部分：

1.算法本身占用的空间，取决于算法的长度；

2.输入输出数据占用的空间，取决于问题规模，与算法无关；

3.辅助存储空间，即算法临时开辟的存储空间，与算法有关。

算法的空间复杂度是对算法的执行过程需要的辅助空间进行度量。通常记作 S(n) = O(f(n))，其中n为问题规模，f(n)为问题规模n的一个函数。

下面也举几个例子

void sort(int x[],int n) {//该算法将一个数组按从大到小的顺序排序
	int i,j,k,t;
	for(i = 0 ; i < n-1 ; i++) {
		k = i;
		for(j = i + 1 ; j < n ; j++) {
			if(x[j] > x[k]) {
				k=j;
			}
			if(k != i) {
				t = x[i];
				x[i] = x[k];
				x[k] = t;
			}
		}
	}
}

这里定义了四个辅助变量，临时存储空间与问题规模n无关，故其空间复杂度为O(1)，时间复杂度为O($n^2$)

一般而言，如果不包含递归调用，则算法的空间复杂度为O(1)

void mergesort(int a[],int i,int j) {
    int m;
    if(i != j) {
        m = (i+j)/2;
        mergesort(a,i,m);
        mergesort(a,m+1,j);
        merge(a,i,j,m);//假定merge是一个非递归函数，其内部只定义了一个辅助变量
    }
}

如何求mergesort(a，0，n-1)的空间复杂度呢？

对于该算法，设mergesort(a，0，n-1)的临时空间大小为S(n)，其中定义了一个辅助变量m，

$$S(n)=\begin{cases} O(1) , & \text{n=1} \\ 2·S(\frac{n}{2})+1 , & \text{n>1} \end{cases}$$

当n > 1 时，S(n) = 2·S($\frac{n}{2}$) + 1 = 2 ( 2·S($\frac{n}{2^2}$) + 1) + 1=$2^2S(\frac{n}{4})$ + 1 + 2=$2^3S(\frac{n}{8})+1+2+2^2$

=…=$2^kS(\frac{n}{2^k})+\sum_{i=1}^{k}2^{i-1}$=$2^kO(1)+2^k-1$

由于$\frac{n}{2^k}$ -> 1，则k=$\log_{2}n$

故S(n) = n + n - 1=2n-1，故该算法的空间复杂度为O(n)