时空复杂度的理解

1. 算法效率的度量

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

（1）事后统计法

         因为计算机内部都有计时功能，有的甚至精确到毫秒级，不同算法的程序可通过一组或若干组相同的统计数据以辨别优劣。但这种方法有两个缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身优劣。

（2）事前分析法

       一个用高级程序语言编写的程序在计算机上运行时所消耗的是阿金取决于以下因素：

        ①依据算法选用何种策略

        ②问题的规模，例如：求100以内还是1000以内的素数

        ③书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率越低；

        ④编译程序所产生的机器代码质量；

        ⑤机器执行指令的速度。

显然，同一个算法用不同语言或者不同编译程序编译或者不同的计算机上运行，效率都不相同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开与计算机硬件、软件相关的因素，可以认为一个特定算法“运行工作量”的大小，是依赖于问题的规模，或者说是问题规模的函数。

2. 基本操作的原操作

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

           显然基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下它是最深循环内的语句中的原操作，它执行次数和包含它的语句频度相同。语句的频度指的是该语句重复执行的次数。

3. 时间复杂度

             一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用"O"来表示数量级，给出算法的时间复杂度。

                    

          它表示随着问题规模的n的增大，算法的执行时间的增长率和f(n)的增长率相同，这称作算法的渐进时间复杂度，简称时间复杂度。而我们一般讨论的是最坏时间复杂度，这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，分析最坏的情况以估算算法指向时间的一个上界。

例1：
for(i = 1;i <= n; ++i)
	for(j = 1; j <= n; ++j)
	{
		++x; 
		s += x;
	}

            包含 “x 增 1” 基本操作的语句的频度为：，其时间复杂度为：，即：平方阶。

例2：
for(i = 2; i <= n; ++i)
	for(j = 2;j <= i-1; ++j)
	{
		++x;  
		a[i,j] = x;
	}

包含 “x 增 1” 基本操作的语句的频度为 1+2+3+…+n-2 = (1+n-2)×(n-2)/2 = (n-1)(n-2)/2 其时间复杂度为：，即：平方阶。

例3：
void bubble_sort(int a[]，int n) 
{   //将a中整数序列重新排列成自小至大有序的整数序列。 
	for(i = n-1,change = TURE;i >= 1 && change; --i)
	{
		change = false;
		for (j = 0; j < i; ++j)
			if (a[j] > a[j+1])
			{
				a[j]←→a[j+1];  
				change = TURE;
			} 
	}
}// bubble-sort

最好情况：0次

最坏情况：1+2+3+…+n-1=n(n-1)/2

在数据结构中讨论的时间复杂度，均指最坏的时间复杂度。平均时间复杂度为：

4. 时间复杂度的分析方法：

①时间复杂度就是函数中基本操作原操作所执行的次数

②一般默认的是最坏时间复杂度，即分析最坏情况下所能执行的次数

③忽略掉常数项

④关注运行时间的增长趋势，关注函数式中增长最快的表达式，忽略系数

⑤计算时间复杂度是估算随着n的增长函数执行次数的增长趋势

⑥递归算法的时间复杂度为：递归总次数 * 每次递归中基本操作所执行的次数

5. 常见时间复杂度

常数阶，对数阶，线性阶，线性对数阶，平方阶 ，立方阶，k 次方阶，指数阶，阶乘阶 。

时间复杂度之间的关系为：

      

当n很大时，指数阶算法和多项式阶算法在所需时间上非常悬殊。因此，只要有人能将现有指数阶算法中的任何一个算法化简为多项式阶算法，那就取得了一个伟大的成就。

常见时间复杂度的增长率：

6. 空间复杂度

空间复杂度作为算法所需存储空间的量度，记作

其中n为问题的规模（或大小）。

 

 

程序代码本身所占空间对不同算法通常不会有数量级之差别，因此在比较算法时可以不加考虑；算法的输入数据量和问题规模有关，若输入数据所占空间只取决于问题本身，和算法无关，则在比较算法时也可以不加考虑；由此只需要分析除输入和程序之外的额外空间。 

若所需临时空间不随问题规模的大小而改变，则称此算法为原地工作。

例1：
float abc (float a,float b,float c)
{
	return a + b + b * c;
}
float sum (float list [],int n)
{
	float tempsum = 0;
	for(int i = 0; i < n; i++)	   tempsum += list[i];
	return tempsum;
}

以上两个函数临时空间不随问题规模的大小而改变，其空间复杂度为：O(1)，即：原地工作。

例2：
float rsum (float list [], int n)
{
	if(n == 0) return 0;
	return rsum(list, n-1) + list[n-1];
}

该递归函数临时空间n大小而改变，其空间复杂度为：。