这篇文章你能得到哪些知识：
1.复杂度分析方法大O表示法介绍
2.常见的几种复杂度实例和拟合曲线
3.详细分析Leetcode第一题的相关复杂度
通过以上几点，让你对复杂度分析有一个全面的认知。
文章目录
- 为什么要进行复杂度分析？
- 什么是大O表示法？
- 几种常见的时间复杂度实例和拟合曲线：
- 最好、最坏和平均情况下的复杂度分析
- LeetCode第一题实战分析：
- 小结
为什么要进行复杂度分析？
讨论数据结构和算法，必然涉及复杂度分析。包括时间复杂度分析和空间复杂度分析。研究算法和数据结构的最终目的就是为了 “快” 和 “省”，快是指速度快，省是指耗费的内存等硬件资源少。那用什么指标去衡量快和省？
我们可以设计出算法，然后放在机器上运行，测试它的运行时间，内存消耗等各种指标，然后给出结论。这种方案我们称为事后统计法。这个方案存在一些弊端：
-
1.受测试环境影响大，不同的硬件配置，可能结论差异很大。
-
2.测试受数据规模影响很大，测试的数据量范围可能覆盖有限
备注：这些缺点并非说实际中就不需要这样的测试方法，实际开发这种事后统计很有必要，和下面要谈的并不冲突。
那能否有一种方法，在设计算法时，就能大致估算算法的性能？ 没错，大O表示法就可以。
什么是大O表示法？
假如有一段代码：
public void print(int n){
int a = 1; //执行1次
for(int i=0;i<n;++i){//执行n次
System.out.println(a+i);//执行n次
}
}
假设我们执行一行代码平均需要用时是一个常数 t = unit_time，那计算上面代码（算法）的用时，就是执行总行数乘以unit_time。上面的代码总时间就是：
T ( n ) = ( 1 + 2 n ) u n i t _ t i m e T(n) = (1+2n)unit\_time T(n)=(1+2n)unit_time
其中n是方法参数，代表算法的数据规模。可以看出，执行用时和(1+2n)成正比。我们用大O表示法表示该算法的时间复杂度就是：
O
(
1
+
2
n
)
O(1+2n)
O(1+2n)
大O表示法会忽略常量、低阶和系数，所以记作：
O
(
n
)
O(n)
O(n)
大O表示法描述的是随着数据规模n增长时，算法的增长变化趋势。并不代表实际的执行时间。
如果算法的执行时间和数据规模n无关，则是常量阶，计作 :
O
(
1
)
O(1)
O(1)
一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)
备注：空间复杂度分析，就是算法在执行的过程中额外引入的内存空间消耗，非常简单，所以直接在下文的实战分析中使用，不做过多介绍。
几种常见的时间复杂度实例和拟合曲线：
常见的时间复杂度和其数学特性：
| 复杂度量级 | 大O表示法 |
|---|---|
| 常量阶 | O(1) |
| 对数阶 | O(logn) |
| 线性阶 | O(n) |
| 线性对数阶 | O(nlogn) |
| 平方阶、立方阶、…k次方阶 | O(n2)、O(n3)、…O(n^k) |
| 指数阶 | O(2^n) |
| 阶乘阶 | O(n!) |
通过曲线的变化，能够直观了解几种时间复杂度的情况。
其中最后两个，指数和阶乘是非多项式量级，其余都是多项式量级。我们把时间复杂度是非多项式量级的算法问题称为NP(Non-Deterministic-Polynomial,非确定多项式)问题。简言之，就是随着数据规模增长，时间复杂度失控，会非常复杂耗时很久的一类问题，有关NP更详细的细节请参考《算法导论》中的章节。有关 “失控”，看下文的拟合曲线直观感受下。
为了更加直观我们取一组样本数据，来拟合一些曲线，更准确直观的感受一下。
首先对比 n的6次方阶底数为2的指数阶 随数据规模n的变化曲线：
可以看到，随着横坐标n的增长,指数阶很快就超过了6次方阶，而且数值会变成天文数字。按照之前的分析，如果单位用时unit_time = 0.0001毫秒，则当 n = 30 时，用时将达到 107 秒，而随着n的增大，用时将“失控”。
下面在对比 指数和阶乘的量级：
上面我们已经感受了指数量级的恐怖，但是阶乘更加凶残，和阶乘相比，指数让你觉得有一种常量的错觉。具体分析我就不再计算了。
通过上面拟合曲线的直观感受，我们就可以理解指数和阶乘这种时间复杂度，是很恐怖的，我们平时讨论的算法很少涉及到。
最好、最坏和平均情况下的复杂度分析
在分析时间复杂度时，我们有时需要分析最好或最坏情况下的时间复杂度，除此之外还有平均时间复杂度，和均摊时间复杂度。我们利用分析下面这段代码说明这几种都代表什么含义：
//n是数组nums的长度
public int find(int[]nums,int n,int target){
for(int i=0;i<n;++i){
if(nums[i]==target){
return i;
}
}
return -1;
}
-
最好情况，就是最理想的情况下的复杂度。上边最理想的情况就是第一个就是要找的，所以最好情况下时间复杂度是O(1)
-
最坏情况时间复杂度。上边代码，最坏的情况，就是要找的数在最后一个，所以需要遍历n次，最坏情况下时间复杂度是O(n)
-
平均时间复杂度。
分析：为了方便说明，我们假设数组中一定存在要找的数。而要找的数在0 - n-1这些位置出现的概率相同，都是 1/n ,所以考虑每种情况下总共要查找的次数，求出总数，然后再除以 可能的情况数，就是平均要查找的次数：
S u m ( n ) = 1 n × 1 + 1 n × 2 + . . . + 1 n × n = 1 n × ( 1 + 2 + . . . + n ) = n + 1 2 Sum(n) = \frac{1}{n} \times 1 +\frac{1}{n} \times2+...+\frac{1}{n} \times n =\frac{1}{n} \times(1+2+...+n) = \frac{n+1}{2} Sum(n)=n1×1+n1×2+...+n1×n=n1×(1+2+...+n)=2n+1
去除常量和系数就是：O(n)
- 均摊分析法。平时不太常用，它指的是算法大部分时间是一种复杂度，偶尔会出现复杂度加剧，可以通过将这些偶发情况均摊到出去，计算均摊后的时间复杂度。一般经验告诉我们，均摊后还是一般情况下的复杂度。就好像被“稀释”了。比如栈在动态扩容时，入栈操作时间复杂度由O(1)退化到O(n), 但是扩容是在内存到临界点时才触发一次，所以总的时间复杂度还是O(1).
LeetCode第一题实战分析：
题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
链接
我们取其中一个采用双层循环求解的进行分析最好、最坏、和平均时间复杂度分析, 这里我们不讨论这道题本身，只用于复杂度分析。算法代码如下：
public int[] twoSum(int[] nums, int target) {
//初始化一个数组存放结果
int[] re =new int[2];
for(int i=0;i<nums.length-1;++i){
int num1 = nums[i];
for(int j=i+1;j<nums.length;++j){
int nums2=nums[j];
//如果找到，就返回结果，避免多余循环
if((num1+nums2)==target){
re[0] = i;
re[1] = j;
return re;
}
}
}
return re;
}
代码本身比较简单，总共是两层循环，如果未找到，数组是空数组。我们这里 数组长度：就是数据规模n
分析：
我们先做两个假设：
1.数组中能够找到这样的结果，找完发现不存在这种情况并不影响算法的复杂度。因为计算的步骤不会变化。
2.在1的基础上，我们为了简化分析，我们假设只存在一对这样的数。
备注：任何算法问题，一些边界是要做划分的，工程问题的求解就是找到更多这样的假设，简化条件，进行建模，所以这里的假设并非没有意义。
最好情况：
最好情况很简单，那就是我们要找的两个数，刚好就是第一个和第二个数。所以外循环循环一次，内循环循环一次就完成了查找。时间复杂度是：
O
(
1
)
O(1)
O(1)
但是我们知道这种概率很小。所以我们需要继续分析其他情况。
最坏情况：
最坏情况就是，找遍到最后一个元素，才找到。我们注意：
- 外层循环是从0循环到n-2
- 内层循环和外层循环的值有关，从外层当前的值，循环到n-1
所以总的比较次数就是 每个外层循环时，内层循环的次数 之和。比如外层i=0时，内层从1循环到n-1循环了n-1次，外层i=1时，内层从2循环到n-1循环了n-2次 …直到最后一次，内层只需要循环1次 所以：
S
u
m
(
n
)
=
(
n
−
1
)
+
(
n
−
2
)
+
(
n
−
3
)
+
.
.
.
+
1
Sum(n) = (n-1)+(n-2)+(n-3)+...+1
Sum(n)=(n−1)+(n−2)+(n−3)+...+1
这是一个等差数列，每个括号中的看做一个整体，求和得到：（首项加末项）x 项数 /2
S
u
m
(
n
)
=
(
n
−
1
)
+
1
2
×
(
n
−
1
)
=
n
2
−
n
2
Sum(n) =\frac{(n-1)+1}{2} \times (n-1) =\frac{n^2-n}{2}
Sum(n)=2(n−1)+1×(n−1)=2n2−n
去掉常量、系数和低阶，时间复杂度就是：
O
(
n
2
)
O(n^2)
O(n2)
平均情况 :
分析：我们最终的目的是要找到两个数，满足我们的条件。代码的外层循环显然是找第一个数，内层循环在找第二个数。根据假设，这对数存在并且唯一。（其他情况，比如有重复，复杂度会介于最好和平均之间，因为更容易找到，所以这里我们只分析唯一的情况）
我们假设第一个要找的数 出现在下标 0 - n -2 的概率相等，都是 1/(n-2) , 所以外层循环的次数可能出现的情况如下：
1
n
−
2
,
2
n
−
2
,
3
n
−
2
,
.
.
.
n
−
2
n
−
2
,
\frac{1}{n-2},\frac{2}{n-2},\frac{3}{n-2},...\frac{n-2}{n-2},
n−21,n−22,n−23,...n−2n−2,
当外层循环的次数是 1/(n-2) 时，内层需要循环n-1次，因为内层循环次数和外层的当前i有关。所以加权平均情况下的总的比较次数就是：
S
u
m
(
n
)
=
1
n
−
2
×
(
n
−
1
)
+
2
n
−
2
×
(
n
−
2
)
+
.
.
.
+
1
n
−
2
Sum(n) = \frac{1}{n-2} \times (n-1) + \frac{2}{n-2} \times (n-2) +...+\frac{1}{n-2}
Sum(n)=n−21×(n−1)+n−22×(n−2)+...+n−21
求和结果是：
S
u
m
(
n
)
=
n
(
1
+
2
+
3
+
.
.
.
+
n
−
1
)
−
(
1
+
2
2
+
3
2
+
4
2
+
.
.
.
+
(
n
−
1
)
2
)
n
−
2
Sum(n) =\frac{n(1+2+3+...+n-1)-(1+2^2+3^2+4^2+...+(n-1)^2)}{n-2}
Sum(n)=n−2n(1+2+3+...+n−1)−(1+22+32+42+...+(n−1)2)
对分子的等差数列和平方和数列分别求和：平方和公式 = n(n+1)(2n+1)/6
S
u
m
(
n
)
=
(
n
−
1
)
(
3
n
2
−
2
n
2
+
n
)
6
(
n
−
2
)
Sum(n) =\frac{(n-1)(3n^2-2n^2+n)}{6(n-2)}
Sum(n)=6(n−2)(n−1)(3n2−2n2+n)
分子和分母的n-1 与n-2可以近似约掉，最后去掉系数和低阶 所以最终结果就是：
O
(
n
2
)
O(n^2)
O(n2)
小结
我们通过引入时间复杂度的一些概念，谈了大O表示法，直观感受了一些复杂的的曲线，最后用一个例子演示了如何进行时间复杂度分析，一般平均时间复杂度的分析要引入一些概率相关的东西，有可能会很复杂。例子中的演示也只是一个近似估算。对于这类复杂度分析，我们实际中还会采用别的手段，比如递归树分析等。