算法设计的艺术：探索时间复杂度和空间复杂度的计算方法

算法复杂性

假如有这么一道题，要求序列之和：

-1，1，-1，1，...，（-1）^n。

第一种实现方式：

int sum1(int n)
{
	int sum = 0;
	for (int i = 1; i <= n; i++)
		sum += pow(-1, i);
	return sum;
}

但是，为什么不这样运算呢：

图片

这就数学家高斯使用的方式，对应的代码实现：

int sum2(int n)
{
	if (n % 2 == 0)
		return 0;
	
	return -1;

}

来看两者的执行时间比较：

#include <stdio.h>
#include <sys/time.h>
#include <math.h>

size_t get_time()
{
	struct timeval tm;
	gettimeofday(&tm, NULL);
	return tm.tv_usec;
}

int sum1(int n)
{
	int sum = 0;
	for (int i = 1; i <= n; i++)
		sum += pow(-1, i);
	return sum;
}

int sum2(int n)
{
	if (n % 2 == 0)
		return 0;
	
	return -1;

}

int main(int argc,char **argv)
{
	size_t start = get_time();

	int sum = sum1(10000);

	size_t end = get_time();

	printf("n=10000,sum1=%d, run %lu ms\n", sum,end - start);
	
	start = get_time();

	sum = sum2(10000);

	end = get_time();

	printf("n=10000,sum2=%d, run %lu ms\n", sum, end - start);
	return 0;
}

执行结果如下：

n=10000,sum1=0, run 377 ms
n=10000,sum2=0, run 0 ms

可以看到，第二种算法非常高效。第一种算法需要执行n次，而第二种算法只需要执行1次。

算法的定义

算法是对特定问题求解方法的一种描述。算法具有以下特性： （1）有穷性。算法是由若干条指令组成的有穷序列，总能结束，不可能永不停止。 （2）确定性。每条语句都有确定含义，无歧义。 （3）可行性。可以通过有限次运算来实现。 （4）输入/输出。有零个或多个输入，以及一个或多个输出。

“好”算法的标准

（1）正确性。满足需求，能正常运行无错误，能通过测试。 （2）易读性。遵循命名规则，恰当地注释。 （3）健壮性。对非法数据及操作有较好的反应和处理。 （4）高效性。指算法运行效率高，即算法运行消耗的时间短。 （5）低存储。算法所需的存储空间小。

时间复杂度

算法时间复杂度是指算法运行所需的时间。我们将算法基本运算的执行次数作为时间复杂度的衡量标准。

int sum=0;                  //运行1次
int total=0;                //运行1次
for(int i=1;i<=n;i++){      //运行n+1次，最后一次判断不满足循环条件
  sum=sum+i;                //运行n次
  for(j=1;j<=n;j++)         //运行n×(n+1)次
    total=total+i*j;        //运行n×n次
}

上述算法运行次数：�(�)=1+1+�+1+�+�∗(�+1)+�∗�=2�2+3�+3

图片

当n足够大时，算法的运行时间取决于最高项，小项和常数项可以忽略不计。 用极限表示为：

图片

当n足够大时，T(n)和f(n)近似相等，可以用O(f(n))表示时间复杂度渐近上限，衡量算法的时间复杂度。上述算法的时间复杂度就可以表示为O(f(n))=O(n^2)。�(�(�))=�(�2)

i=1;             //运行1次
while(i<=n){     //可假设运行x次
  i=i*2;         //可假设运行x次
}

上述算法中，假设运行了x次才退出循环，i的值依次是2，22，23，......，2�2，2^2,2^3，...，2^x，i>=n结束，即2^x = n，那么x=log_2n，运行次数是1+2*log_2n，因此算法复杂度为O(f(n))=O(log_2n)。

渐近复杂度是对算法运行次数的粗略估计，大致反映问题规模增长趋势。在计算渐近时间复杂度时，可以只考虑对算法运行时间贡献大的语句，忽略运算次数少的语句，比如循环语句中处于循环最内层的语句。

注意，不是所有的算法都能直接计算运行次数。 比如在数组中顺序查找元素并返回其下标，如果找不到返回-1。

int findx(int x){     //在a[n]数组中顺序查找x
    for(int i=0;i<n;i++){
        if(a[i]==x)
            return i; //查找成功，返回其下标i
    }
    return -1;        //查找失败，返回-1 
}

对于上述算法，很难计算其唯一的时间复杂度。 因此，有些算法可以分为最好、最坏和平均情况分别求算法的渐近复杂度。但是，算法通常考察的是最坏的情况，最坏情况对衡量算法的好坏具有实际意义。

空间复杂度

空间复杂度是指算法占用的空间大小，即算法在运行过程中占用了多少存储空间。算法占用的存储空间包括： （1）输入/输出数据。 （2）算法本身。 （3）额外需要的辅助空间。

输入/输出数据是必须的，算法本身能缩减的空间很小，所以辅助空间才是衡量算法空间复杂度的关键因素。

void swap(int x,int y){    //交换x与y 
     int temp;
     temp=x;               //辅助空间 
     x=y;                  
     y=temp;               
}

上述算法中两数的交互过程如下图：

图片

使用了辅助空间temp，空间复杂度为O(1)。

注意，在递归算法中，每次递推都需要一个栈空间来保存调用记录，因此在分析算法的空间复杂度时需要递归栈的辅助空间。例如下面计算N的阶乘算法：

int func(int n){ //计算n的阶乘
    if(n==0||n==1) 
        return 1; 
    else 
        return n*func(n-1); 
}

假设n=5，其递推和回归过程如下：

图片

上述过程是逻辑思维的推理，在计算机中使用栈存放上述过程，即后进先出的模式。

图片

从上图的进栈、出栈可以看到，子问题一步步压进栈，直到可解得到返回值，再一步步出栈，最终得到递归结果。运算过程中使用了n个栈空间作为辅助空间，因此阶乘递归算法的空间复杂度为O(n)。

再回到上述的算法代码中，n的阶乘仅比n-1的阶乘多了一次乘法运算使用T(n)表示func(n)的时间复杂度，则可以表示为：

图片

即时间复杂度也是O(n)。

算法时间复杂度的种类

先看看一个例子：一个64格的棋盘，按照第1个格子放1粒麦子，第2个格子放2粒麦子，第3个格子放4粒麦子，第4个格子放8粒麦子，以此类推，每个格子里麦子的粒数是前一个格子的两倍，把64个格子放满究竟需要多少粒麦子？

乍一看，很少的感觉，那么来用数学计算一下。 把每个格子所需的麦子数加起来，总和为S，则：

图片

上述等式等号两边都乘以2，等式依旧成立：

图片

两个等式相减，得：

图片

按照一颗麦粒平均重量约41毫克，则总麦粒的总重量为：

图片

是不是很大，我们称这样的函数为爆炸性增量函数。如果算法的时间复杂度也是爆炸性增量，比如O(2^n)。后果不敢想象，随着n不断增大，导致程序、系统、服务之间宕机。

常见的算法时间复杂度有以下几类： （1）常数阶。算法的运行次数是一个常数，比如2，10，18，100。时间复杂度通常用O(1)表示。

（2）多项式阶。很多算法的时间复杂度是多项式，通常是O(n)、O(n^2)、O(n^3)

（3）指数阶。算法的运行效率极差，时间复杂度通常是O(2^n)、O(n!)、O(n^n)。

（4）对数阶。算法的运行效率较高，通常用O(logn)、O(n log n)、O(log_2 n)等表示。

指数阶增量随着n的增加而急剧增加，而对数阶增长缓慢。它们的关系如下：

图片

设计算法时，需要注意算法复杂度增量问题，避免爆炸级增量。

总结

1. 将程序执行次数作为时间复杂度衡量标准。
2. 时间复杂度通常用渐进上界符号O(f(n))表示。
3. 衡量算法的好坏通常考察算法的最坏情况。
4. 空间复杂度只计算辅助空间。
5. 递归算法的空间复杂度需要计算递归使用的栈空间。
6. 计算算法时要尽量避免爆炸级增量复杂度。

通过本节，对算法有初步的认识，算法不是凭空造出来的，而是来源于生活中的某些问题。算法的本质是高效地解决实际问题。