时间复杂度&空间复杂度

发表于 | 分类于 | 阅读次数：

【基础知识】考量一个算法的维度

时间复杂度

时间频度

  一个算法执行所耗费的时间。
  从理论上讲时间是不能计算出来的，必须上机运行测试才能知道，但我们不可能也没有必要对每个算法都上机运行测试，我们只需要知道哪个算法花费的时间多，哪个算法花费的时间少即可。并且一个算法花费的时间与算法中语句的执行次数成正比，所以一个算法中语句执行的次数多，它花费时间就多。
  一个算法中的语句执行次数称为语句频度或时间频度，记为O(n)。

计算时间复杂度的具体步骤

  1. 找出算法中的基本语句
      算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

  2. 计算基本语句的执行次数的数量级
      只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

  3. 用大Ο记号表示算法的时间性能
      将基本语句执行次数的数量级放入大Ο记号中。

如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加;

时间复杂度

O(1)

1
2
3
int a=2;
int b=2;
int c=2;

  以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n)

1
2
3
4
5
int i, n = 100, sum = 0;
for( i=0; i < n; i++ )  /执行n+1次/
{
	sum = sum + i;
}

  这段代码的时间复杂度为O(n)，因为循环体中的代码需要执行n次。

O(n*n)

1
2
3
4
5
6
7
8
int i, j, n = 100;
for( i=0; i < n; i++ )  /执行n+1次/
{
	for( j=0; j < n; j++ )    /执行n*(n+1)次/
	{	
		printf(“I love you!”);	/执行n*n次/
	}
}

根据以上代码，n=100，也就是说外层循环每执行一次，内层循环就执行100次，那么程序要运行完两个循环，需要执行100*100次，也就是n的平方，所以这段代码的时间复杂度为O(n*n)。

  那么问题就来了，要是有三个这样的嵌套循环，时间复杂度就是n*n*n。

特殊的–> 选择排序法

1
2
3
4
5
6
7
8
int i, j, n = 100;
for( i=0; i < n; i++ )
{
	for( j=i; j < n; j++ )
	{
		printf("选择排序");
	}
}

根据以上代码分析，当i=0时，内循环执行了n次；当i=1时，内循环则执行n-1次……当i=n-1时，内循环执行1次，所以总的执行次数是：n+(n-1)+(n-2)+…+1 = n(n+1)/2。用我们推导大O的攻略，第一条忽略，因为没有常数相加。第二条只保留最高项，所以n/2这项去掉。第三条，去除与最高项相乘的常数，最终得时间复杂度为O(n2)。

空间复杂度

算法中用到的变量个数

O(n)