算法的性能分析

Posted on | Edited on | In | Views:

在程序设计中算法的性能分析是非常重要的，针对一个具体的问题可能提出若干种不同的算法实现。如何从这些算法种找出性能最优的那个？或者说针对一个具体的算法如何评论它的优劣？这里要涉及的一个问题就是如何对算法的性能进行评价？评价算法的性能主要从两个方面着手：

  1. 算法的执行时间
  2. 算法所占用的存储空间

这两个指标分别对应算法的时间复杂度与空间复杂度，下面分别来说.

算法的时间复杂度

定义

算法的时间复杂度的目的是为了近似的评估算法的执行时间，因为要准确测量一个算法的执行时间多少是非常困难的，它受到计算机软硬件环境的影响。它的定义是这样的:

T(n) = O(f(n))

它表示随问题规模n的增大，算法的执行时间的增长率和算法中语句的总的执行次数f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。其中这里O来表示数量级，f(n)一般是算法中频度最大的语句频度.

如何求时间复杂度

要求算法的时间复杂度, 关键就在于找到这个算法中执行频度最大的那条语句f(n), 找到了f(n)那么时间复杂度T(n)自然就出来了.

下面举例说明:

  1. 常数阶
1
2
3
4
5
O(1)

temp = i;
i = j;
j = temp;

以上3条语句的语句频度都为1, 而且该程序段的执行时间是一个与问题规模n无关的常数. 这种类型的算法的时间复杂度:T(n)=O(1).

  1. 线性型
1
2
3
4
5
O(n)

for (int i = 0; i < n; i++){
  n++; //频度最大
}

很显然这种类型的算法的语句频度与问题规模n刚好是呈正线性相关的, 时间复杂度为T(n) = O(n).

  1. 平方型
1
2
3
4
5
6
7
8
9
10
11
12
O(n2)

int[] a = {3, 2, 4, 7, ..., n}
for(int i = 0; i < n - 1; i++){
	for (int j = i + 1; j < n; j++){
		if(a[i] > a[j]){ // do swap, f(n)= n * n
			int temp = a[i]; //频度最大
			a[i] = a[j];
			a[j] = temp;
		}
	}
}

当有若干个循环语句时, 算法的时间复杂度是由嵌套最深的循环语句中最内层的语句的频度f(n)决定.而忽略其它嵌套层次更低的循环.

  1. 立方型
1
2
3
4
5
6
O(n3)

for i..n
  for ...
    for ...
      do something... //频度最大

常见的时间复杂度

O(1)常数型
O(log2n)对数型
O(nlog2n)二维型
O(n)线性型
O(n2)平方型
O(n3)立方型
O(2n)指数型

时间复杂度图示

一般情况下, 随问题规模n的增大, 时间复杂度T(n)增长最慢的算法为最优算法. 以上几种算法随n的不断最加时间复杂度增加越来越快, 因此一般应该选择使用O(nk)的算法. 避免使用指数阶的算法.

最坏时间复杂度与平均时间复杂度

算法的时间复杂度不仅与问题规模n相关还与输入实例的初始状态有关.

看个例子:

1
2
3
4
5
T(n) = O(n)

i = n - 1;
while(i >= 0 && (a[i] != k))
  i--;

上述算法的时间复杂度不仅与n相关还与输入的数组a及k的取值情况相关:

最坏情况: 数组a中没有与k相等的元素.则语句3的频度f(n) = n, 时间复杂度T(n) = O(n)

最好情况: 或a中最后一个元素等于k,则语句3的频度f(n) = 0, 时间复杂度T(n) = O(1)

一般不特别说明, 讨论的时间复杂度均是最坏情况下的时间复杂度, 这样做的原因是能够保证算法在任何输入实例情况下都能够被考虑到. 而平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下的时间复杂度.

因此上述算法的时间复杂度为: O(n)

算法的空间复杂度

辅助存储空间

一般情况下, 一个程序在机器上执行时, 除了需要存储本身所需要的代码/输入数据外, 还需要一些对数据进行操作的辅助存储空间.其中输入数据所占用的具体空间取决于问题本身, 与算法无关. 因此我们所讨论的空间复杂度只与该算法在实现时所需要的辅助空间单元个数相关. 即 空间复杂度讨论的是算法所需要的辅助存储空间.

定义

算法的空间复杂度S(n)定义为该算法所耗费的存储空间的数量级, 它是问题规模n的函数, 记作:

S(n) = O(f(n))

若算法执行时间时所需要的辅助空间相对于输入数据量而言是一个常数, 则称这个算法为原地工作, 辅助空间为O(1). 看个例子:
将一维数组a中的n个数据逆序存放到原数组中, 下面是两种算法:

[算法1]

1
2
3
4
5
6
S(n) = O(n)

for(i = 0; i < n; i++)
  b[i] = a[n - i - 1];
for(i = 0; i < n; i++)
  a[i] = b[i]

[算法2]

1
2
3
4
5
6
7
S(n) = O(1)

for(i=0; i < n/2; i++){
  t = a[i];
  a[i] = a[n - i - 1];
  a[n - i - 1] = t;
}

算法1的空间复杂度为O(n), 需要一个大小为n的辅助数组b

算法2的空间复杂度为O(1), 仅需要一个变量t, 与问题规模n无关

总结

算法的空间复杂度与时间复杂度合称为算法的复杂度. 面对不同的算法如何选择主要就从这两个方面去考虑, 理想情况是一个算法的时间与空间复杂度都小, 但这是很难做到的, 面对不同的情况要具体问题具体分析: 是以时间换空间, 还是以空间换时间.

参考

数据结构-用C语言描述