算法复杂度分析（上）

public int sum(int n) {
	int sum = 0;  // 一个unit_time
	int i = 1;	  // 一个unit_time
	for (; i <= n; i++) {	// n个unit_time
		sum += sum + i;		// n个unit_time
	}
	
	return sum;
}

从CPU的角度来看，这段代码的每一行执行着类似的操作：读数据-运算-写数据。尽管每行代码对应的CPU执行的个数和执行的时间都不一样，但是我们这里只是粗略地估计，所以可以假设每行代码执行的时间都一样，为unit_time。所以上面那段代码的总的执行时间是(2n+2)·unit_time。可以看出，所有代码的执行时间与每行代码的执行次数成正比。
尽管我们不知道unit_time的具体值，但是我们可以通过上面那段代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是，代码的执行时间与每行代码的执行次数n成正比。

我们可以把这个规律总结成一个公式。T(n) = O(f(n))
T(n)为代码执行的时间，n为数据规模的大小，f(n) 表示每行代码执行的次数总和。公式中的O表示代码的执行时间T(n)与f(n)表达式成正比。

所以，上面那段代码T(n)=O(2n+2)。这就是大O时间复杂度表示法。大O时间复杂度实际上并具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。

当n很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，所有可以忽略。我们只需要记录一个最大量级就可以了。上面那段代码可以表示为T(n)=O(n)。

时间复杂度分析

只关注循环执行次数最多的一段代码
总复杂度等于量级最大的那段代码的复杂度
嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

几种常见时间复杂度(按数量级递增)

常量阶 O(1)
对数阶 O(logn)
线性阶O(n)
线性对数阶O(nlogn)
平方阶O(n²),立方阶O(n³)等
指数阶O(2ⁿ)
阶乘阶O(n!)

算法复杂度分析（上）

对于刚罗列的复杂度量级，可以粗略地分为两类:多项量级和非多项量级。
其中，非多项量级只有两个：O(2ⁿ)和O(n!)。
我们把时间复杂度为非多项式量级的算法问题叫作NP(Non-Deterministic Polynomical，非确定多项式)问题。
当数据规模n越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

O（1）

O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如以下代码时间复杂度为O(1):

	// 执行了10次，时间复杂度也为O(1)
	for (int i = 1; i <= 10; i ++) {
		sum += i;
	}

只要代码的执行时间不随n的增大而增长，这样代码的时间复杂度都记作O(1)。或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使成千上万行的代码，其时间复杂度也是O(1)。

O(logn)&O(nlogn)

对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。

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

每一次循环i就乘以2。当大于n时，循环结束。也就是2^x=n,x为执行的次数，根据高中的对数知识，很容易得出x=log₂n，所以这段代码的时间复杂度就是O(log₂n).

实际上，不管是以2为底、以3为底还是以10为底，我们可以把所有对数阶的时间复杂度都记为O(logn)。这是根据对数公式得出的：

  				log₃n = log₃2 · log₂n = C · log₂n

C是一个常量，可以忽略。因此，在对数阶时间复杂度的表示方法里，我们可以忽略对数的“底”，统一表示为O(logn)。

现在我们可以很好的理解O(nlogn)，如果一段代码时间复杂度为O(logn),循环执行n遍，时间复杂度就为O(nlogn)。

O(m+n) & O(m*n)

这种复杂度是由两个不同的数据规模来决定的。

空间复杂度分析

时间复杂度全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

常见的空间复杂度有O(1)、O(n)、O(n²)。下面通过代码来说明一下：

	int[] a = new int[10];  // O(1)
	int[] b = new int[n]; 	// O(n)

参考资料

数据结构与算法之美

算法复杂度分析（上）