1 综述

当我们需要比较多个可进行比较的事物时，需要找到一种能够方便地进行比较的方法。 具化一下，以算法来说，为了比较不同的算法性能， 需要找到一种合适的抽象层次的衡量方法。

衡量某种算法的性能主要包括两个方面：

  1. 时间性能，即一个算法的执行需要多长时间
  2. 空间性能

2 时间性能

算法主要由语句构成，因此一个算法的时间性能主要取决于两点：

  1. 每条语句的执行时间
  2. 语句执行次数

这里 语句执行次数 称为 语句频度或时间频度, 记为T(n), n代表问题的规模。

如果只有两个算法需要比较，我们可以详细地计算出每个算法的T(n)。但是，

我们需要比较的成千上万的算法，因此需要一种 合适抽象层次的衡量方法 。

因此引入了 时间复杂度 的概念

2.1 时间复杂度

有n代表问题的规模， 如果有一个函数f(n)，当n无限大时，T(n)/f(n)的极限值为不等于零的常数，

则称f(n)是T(n)的同数量级函数（也就是说可以使用f(n)来衡量这个函数），记作T(n)=Ｏ(f(n)),

称Ｏ(f(n)) 为算法的 渐进时间复杂度 ，简称 时间复杂度 。

选择这个f(n)时，应该选择一个简单直观的函数，这样便于进行比较。

常见的f(n)有：

  1. 常数阶O(1)
  2. 对数阶O(log2n)
  3. 线性阶O(n)
  4. 线性对数阶O(nlog2n)
  5. 平方阶O(n2)
  6. 立方阶O(n3)
  7. k次方阶O(nk)
  8. 指数阶O(2n)

常见复杂度

从图中可见，我们应该尽可能选用多项式阶O(nk)的算法，而不用指数阶的算法。

常见的算法时间复杂度由小到大依次为：

Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

2.2 时间复杂度计算方法

2.2.1 找到基本语句

找到最内层的循环体，体内的语句即为 基本语句

2.2.2 计算基本语句的数量级

只需要计算基本语句的 数量级 ，因此只要保证基本语句执行次数的函数中的最高次幂正确即可

2.3 实例

2.3.1 n2 + n = n2

for (i=1; i<=n; i++)
	x++;  n
for (i=1; i<=n; i++)
     　for (j=1; j<=n; j++)
	   x++; n^2

2.3.2 1 + n + n + n = n

a=0;
b=1;
for (i=1;i<=n;i++)
{
   s=a+b;　　　　
   b=a;　　　　　
   a=s;　　　　　
}

2.3.3 log2n

int n = 8, count = 0;;
for(int i=1; i<=n; i *= 2) {
    count++;
}

2.3.4 nlog2n

int n = 8, count = 0;;
for(int i=1; i<=n; i *= 2) {
    for(int j=1; j<=n; j++) {
	count++;
    }
}

2.3.5 n2

sum=0；                 （一次）
for(i=1;i<=n;i++)     （n+1次）
   for(j=1;j<=n;j++) （n2次）
    sum++；            （n2次）

2.3.6 n3

for(i=0;i<n;i++)
   {
      for(j=0;j<i;j++)
      {
	 for(k=0;k<j;k++)
	    x=x+2;
      }
   }

3 空间复杂度

4 常用的算法的时间复杂度和空间复杂度

常用排序算法复杂度