1 算法效率的度量方法

事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。

一个程序在计算机上运行时所消耗的时间取决于下列因素：

• 算法采用的策略、方法

• 编译产生的代码质量

• 问题的输入规模

• 机器执行指令的速度

根据以上因素，抛开与计算机硬件、软件有关的因素，一个程序的运行时间，依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少。

// 执行了1+(n+1)+n+1=2n+3次
int i, sum = 0, n = 100; // 执行1次
for (i = 1; i <= n; i++) { // 执行了n+1次
	sum = sum + i; // 执行了n次
}
printf("%d", sum); // 执行1次

// 执行了1+1+1=3次
int sum = 0, n = 100; // 执行1次
sum = (1 + n) * n/2; // 执行1次
printf("%d", sum); // 执行1次

int i, j, x = 0, sum = 0, n = 100; // 执行1次
for (i = 1; i <= n; i++) { // 内循环每一次都执行n次，两个循环执行n x n次
	for (j = 1; j <= n; j++) {
		x++;
		sum = sum + x;
	}
}
printf("%d", sum); // 执行1次

上面的程序，同样的输入规模n，求和算法的第一种，求1+2+…+n需要一段代码运行n次。那么这个问题的输入规模使得操作数量是 f(n)=n，显然运行100次的同一段代码规模是运算10次的10倍；而第二种，无论n为多少，运行次数都为1，即 f(n)=1；第三种，运算100次是运算10次的100倍，因为它是 f(n)=n²。

2 函数的渐进增长

假设有两个算法，算法A要做2n+3次操作（可以认为是有两次n循环，然后三次赋值或打印代码），算法B要做3n+1次操作，哪种算法更快。

根据上表的数据，输入规模n在没有限制的情况下，只要超过一个数值N，这个函数就总是大于另一个函数，我们称为函数是渐进增长的。

渐进增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐进快于g(n)

随着n的增大，后面的算法A是+3还是算法B是+1已经不影响最终的算法变化，所以我们可以忽略这些加法常数。看最终的算法A′和算法B′就可以得出哪种算法优劣。

算法C是4n+8，算法D是2n²+1，哪个算法更快。

根据上表的数据，随着n的增大，算法C的优势越来越优于算法D了，即使我们去掉常数发现其实结果没有发生改变，即算法C变成4n，算法D变成2n²，结果还是算法C优于算法D；甚至我们去掉与n相乘的常数，结果也没有发生改变，即最终的算法C′和算法D′展示的结果。也就是说，与最高次项相乘的常数并不重要。

算法E是2n²+3n+1，算法F是2n³+3n+1，哪个算法更快。

根据上表的数据，可以发现，最高次项的指数大的，函数随着n的增长，结果也会增长特别快。

算法G是2n²，算法H是3n+1，算法I是2n²+3n+1，哪个算法更快。

根据上表的数据，当n的值越来越大时，算法H已经没法和算法G和算法I相比较了，最终几乎可以忽略不计，而算法G已经很趋近于算法I。所以可以得出结论，判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。

3 算法时间复杂度

算法时间复杂度定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间度量，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。其中f(n)是问题规模n的某个函数。

用大写 O() 来体现算法时间复杂度的记法，称之为大O记法。

一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。

3.1 推导大O阶方法（如何计算时间复杂度）

推导大O阶可以通过以下三个步骤推算：

• 用常数1取代运行时间中的所有加法常数

• 在修改后的运行次数函数中，只保留最高阶项

• 如果最高阶项存在且不是1，则去除与这个项相乘的常数

得到的结果就是大O阶。

比如使用上面的算法G是2n²，算法H是3n+1，算法I是2n²+3n+1，经过第一二步骤后，算法G为2n²，算法H是3n，算法I是2n²，经过第三个步骤后，算法G为n²，算法H为n，算法I为n²，所以就推导出：算法G和算法I的时间复杂度为 O(n²)，算法H的时间复杂度为 O(n)。

3.2 常数阶

int sum = 0, n = 100; // 执行1次
sum = (1+n) * n / 2; // 执行1次
printf("%d", sum); // 执行1次

上面的算法运行次数函数是f(n)=3，根据推导大O阶的方法，发现它根本没有最高阶项，所以这个算法时间复杂度为 O(1)。

无论添加执行多少次 sum=(1+n) * n / 2，无论n为多少，总是该句代码的执行次数，而与n的大小无关，执行时间恒定的短发，称之为具有O(1)时间复杂度，又叫常数阶。

3.2 线性阶

要确定某个算法的阶次常常需要确定某个特定语句或某个语句集的运行次数。因此，我们要分析算法的复杂度，关键就是要分析循环结构的运行情况。

int i;
for (i = 0; i < n; i++) { // 执行了n次，时间复杂度为O(n)
	// 时间复杂度为O(1)的程序步骤序列
}

3.3 对数阶

// 每次count*2后距离n更近一分，即有多少个2相乘后大于n则会退出循环
// 2x=n(x为次方）,x = log2n，所以时间复杂度为O(logn)
int count = 1;
while (count < n) {
	count = count * 2;
	// 时间复杂度为O(1)的程序步骤序列
}

3.4 平方阶

// 外循环执行n次，时间复杂度为O(n)
// 内循环每次都执行n次，时间复杂度为O(n)
// 总共执行n²次，整个算法的时间复杂度为O(n²)
int i, j;
for (i = 0; i < n; i++) {
	for (j = 0; j < n; j++) {
		// 时间复杂度为O(1)的程序步骤序列
	}
}

// 外循环执行m次，时间复杂度为O(m)
// 内循环每次执行n次，时间复杂度为O(n)
// 总共执行了nxm次，时间复杂度为O(nxm)
for (i = 0; i < m; i++) {
	for (j = 0; j < n; j++) {}
}

// i=0，内循环执行了n次;i=1，内循环执行了n-1次；i=n-1时，执行了1次
// 总执行次数为n+(n-1)+(n-2)+...+1= n²/2 + n/2
// 根据大O推导，经过第一二步骤后，算法为n²/2，第三步骤去除和最高阶相乘或相除的常数
// 所以该算法的时间复杂度为O(n²)
for (i = 0; i < n; i++) {
	for (j = i; j < n; j++) {}
}

4 常见的时间复杂度

常用的时间复杂度所耗费的时间从小到大依次是：

在实际的项目中，一般不会去处理立方阶之后的算法也不切实际，最常见的就是常数阶、线性阶、平方阶、对数阶、nlogn阶。

5 最坏情况和平均情况

在算法的分析中，比如查找一个有n个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法复杂度为O(1)，但也有可能这个数字就在最后一个位置，那么算法的时间复杂度就是O(n)。

最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。

而平均运行时间也就是从概率的角度看，这个数字在每一个位置的可能性是相同的，所以平均的查找时间为n/2次后发现这个目标元素。

平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。在实际项目中很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来。

6 算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间时间，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。所算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称次算法为原地工作，空间复杂度为O(1)。

一般我们提到复杂度，都是说的时间复杂度，在实际的工作中，主要的还是会分析时间复杂度。

时间复杂度

为什么要有时间复杂度？

第一、在我们的测试环境里面，不同的硬件跑出来的结果是不一样的，比如，i7与i3的机器跑同样的代码花的时间就不一样。

第二、用不同的数据去测试，那么花的时间也是不一样的。

通用公式

所以我们需要一套公式去计算复杂度，通用公式：T = O(N)，T表示代码执行的时间，N表示每行代码执行的次数总和，O表示所有代码的执行时间T与每行代码的执行次数总和成正比。（假设每行代码执行的时间是一样的）

O表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

开始运用方法：

方法一. 只关注循环执行次数最多的一段代码

int cal(int n) { 
     int sum = 0; 
     int i = 1; 
     for (; i <= n; ++i) { 
        sum = sum + i;
     }
     return sum;
 }

其中2、3行是常量级别的代码与n的大小无关，所有不用管，执行次数最多的事第4、5行代码，所以我们只管这个两行，时间复杂度是O(n).

方法二、乘法法则，嵌套代码的复杂度等于内外嵌套复杂度的乘积

int cal(int n) {
	int ret = 0;
	int i = 1;
	for (; i < n; ++i) { //第一段 这个函数的复杂度是O(n)
		ret = ret + f(i);
	}
}
int f(int n) {
	int sum = 0;
	int i = 1;
	for (; i < n; ++i) {//第段段 这函数的复杂度是O(n),合起来就是O(n^2)
		sum = sum + i;
	}
	return sum;
}

这里单看第一段函数的复杂度是O(n)，单看第二段函数的复杂度也是O(n)，有因为嵌套了，合在一起就是O(n^2)了。

方法三、计算复杂度是总复杂度最多的那段

int cal(int n) {
	int sum_1 = 0;
	int p = 1;
	for (; p < 100; ++p) {//第一段为O(1)
		sum_1 = sum_1 + p;
	}
	int sum_2 = 0;
	int q = 1;
	for (; q < n; ++q) {//第二段为O(n)
		sum_2 = sum_2 + q;
	}
	int sum_3 = 0;
	int i = 1;
	int j = 1;
	for (; i <= n; ++i) {//第三段为O(n^2)
		j = 1;
		for (; j <= n; ++j) { //这里又套了一层循环
			sum_3 = sum_3 +  i * j;
		}
	}
	return sum_1 + sum_2 + sum_3;
}

第一段的执行的次数是常量，所以是O(1),第二段执行了n次所以是O(n)，第三段执行了O(n2)，所以这段代码最终的时间复杂度为O(n^2)

再看看常见的多项式时间复杂度

第一种：O(1)

int i = 8;
int j = 6;
int sum = i + j;

这种情况，主要没有递归、循环，即使有上千万行的代码，时间复杂度也是O(1)

第二种： O(logn)、O(nlogn)

 i=1;
 while (i <= n)  {
   i = i * 2;
 }

由上可知道，它的代码执行轨迹就是：2^1 * 2^2 * 2^3 * 2^4 …… 2^x = n 为止，那么求解这个X，就是以2为底的log函数：x=log2n，所以这段代码的时间复杂度是O(log2n)，如果在外面再套一层循环m，那么时间复杂度就是O(m*log2n)

第三种：O(m+n)、O(m*n)

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {//第一段复杂度为O(n)
    sum_1 = sum_1 + i;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {//第二段复杂度为O(m)
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

第一段和第二段的复杂分别是O(n)和O(m),属于同一级别，都是n级别(大于1，小于N的平方)，所以cal()方法的复杂度是O(m+n)，如果第一段和第二段有嵌套的话，那么可以相乘：O(m*n)

空间复杂度分析

空间复杂度就很简单了，就是一句“占用有多少个变量”就可以解释完毕！

void print(int n) {
  int i = 0;
  int[] a = new int[n]; // 只有这里占用了n个空间所以空间复杂度是O(n)
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

}

从上面可以看出，只有第3行 new的时候占用了n个空间，其它行占用的空间是O(1)，所以答案是O(n)

我们平时能用的空间复杂度一般是是O(1),O(n),O(n^2)，其他的O(logn)、O(nlogn)都是用不到的

继续拓展

=========分割线==========

复杂的时间复杂度该怎么算？有下面的问题：

// n表示数组array的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

这个空间复杂度用上面的方法显示不不行的。

        如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是 O(1)。但如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)。所以，不同的情况下，这段代码的时间复杂度是不一样的。

这个需要用到概率论来解决，想继续钻研的朋友可以扫码下面的二维码，听听专业老师的讲解。