为什么需要复杂度分析？
可能对于第一次接触这个概念的同学来说，第一个问题就是，我为什么要需要这个东西呢？我把代码跑一次，统计一下消耗时间不就完了吗？这样不是更准确吗？如果你现在也是这么想的，那么请耐心的往下看
首先来说，直接统计代码的运行时间绝对是没问题的，相应的空间消耗程度也可以通过监控内存来获取。这种统计方法甚至还有一个专门的名字叫"事后统计法"。但是这种方法存在两个很大的弊端
1.受环境影响严重，如机器配置
一个相同的算法，在不同配置的机器上运行时间肯定是不同的。这一点不用多说
2.受数据量影响严重
举个极端的例子如下：
public void demo01(List<Integer> list) { for (Integer integer : list) { System.out.println(integer); } } public void demo02(List<Integer> list) { int count = 0; for (Integer integer : list) { count++; System.out.println(integer); if(count>100000){ try { Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); } } } }
我们可以看到demo01,demo02两个算法（姑且叫它们算法，只是为了说明这种情况，实际情况下没人会这么写）
这两个算法的目的都是为了遍历集合中的所有元素，当元素的数量不高于100000时，这两个算法运行的效率肯定
是差不多的，但是一旦数据规模超出100000时，这两个算法的效率就没有可比性了
综上所述，为了屏蔽外在环境的影响，只是单纯的评判算法的优劣，我们的时间空间复杂度应运而生
如何对一个算法进行复杂度分析？
在知道了为什么会有复杂度的出现后，我们就需要学习下怎么对一个算法进行复杂度的分析。
先来看一个简单的例子：
public int sum(int n) { int sum = 0; for (int i = 0; i < n; i++) { sum += n; } return sum; }
如果对时间复杂度有所了解的话，一眼就能看出结果为O(n)。如果你对复杂度不了解的话，不用急，跟着我的思路来~
我们可以假设每行代码所有消耗的时间都为一个时间单元—u，那么对于这个程序其复杂度不难得出为：(1+n+n+1)*u=(2n+2)*u,第一行程序运行了1次，第二行跟第三行都运行了n次，return语句执行一次，所以结果为(2n+2)*u=n*(2u)+2u(其中u为常数)，那么其时间复杂度就为O(n)
可能有的同学会有疑问:
1.为什么你可以假设每行代码的运行时间都一样呢？很明显for (int i = 0; i < n; i++)比int sum = 0消耗的时间长呀！这样的假设也能成立吗？
2.为什么计算结果为n*(2u)+2u(其中u为常数),其时间复杂度就为O(n)呢？
在这里我们先解释第二个问题，什么是大O？
粗略的讲，大O代表的算法的复杂度变化的趋势，在上面的例子中，我们计算出结果为n*(2u)+2u(其中u为常数)，这是一个一次函数，我们可以称其变化是线性的，当n趋向无穷大时，我们可以忽略常数项，记为O(n)。同样，当我们计算出结果为一个二次函数时，这个时间我们可以忽略其低阶项跟常数项，记为:
这个在之后会再介绍，这里只是提一下
当我们了解到了 什么是大O后，我相信第一个问题也很好解释了
我们可以假设第一行代码消耗的时间为x，那么第二行代码消耗的时间可以表示为k*x(其中k大于0，k为常数)，第三行的代码同样可以表示为z*x（z>0，k为常数）,第四行的同样表示为v*x（v>0，k为常数），那么总消耗时间可以表示为
很明显，这也是一个关于n的1次函数，所以我们也可以记其时间复杂度为O(n)
通过上面的例子，我们已经对时间复杂度及其计算有了一个粗略的了解，下面我们继续通过几个例子来深入了解时间复杂度，并学习几种常见的时间复杂度
几种简单的时间复杂度：
1.常数阶：
O ( 1 ) O(1)
首先，我们要明确一点，O(1)并不代表代码只执行一行，它的意思是说，该算法的执行时间跟外界因素（数据大小，调用次数）无关，举例如下：
public int sum(int n) { int sum = 0; for (int i = 0; i < 3; i++) { sum += n; } return sum; }
在上面的例子中，不如n多大，该方法被调用多少次，每次调用的复杂度永远是1+2*3+1=8，是一个常数，这种情况下，我们记其时间复杂度为O(1)
1.线性：
之前的例子就已经分析过了，这里不再赘述
2.二次：
我们看一个例子：
public int sum(int n) { int sum = 0; for (int i = 0; i < n; i++) { sum += n; for (int j = 0; j < n; j++) { sum += j; } } return sum; }
我们按照我们的方法计算其复杂度:
第一行代码执行一次：1
第二行代码执行n次：n
第三行代码执行n次：n
第四行代码执行：n乘n次（外圈每执行一次，内圈执行n次，所以为n乘n次）
第五行代码也是：n乘n次
return语句执行1次：1
所以时间复杂度为：
根据我们之前说的，忽略其低阶项及常数项，可记为：
到这里我们可以发现，因为我们往往要忽略低阶项跟常数项，只保留最高阶，相当于我们只需统计执行次数最多的代码，在上面的例子中我们很容易发现，执行最多次数的代码就是内嵌的循环，为二次函数，所以很快得出结论，时间复杂度为O(n^2)
1.三次：
在学习了线性及二次时间复杂度了之后，三次也很容易理解了，最简单的例子就是循环嵌套了三层，这里不再赘述
2.指数：（增长速度非常恐怖），这里给出一个简单的例子，读者自行思考即可，不恰当的递归也会导致指数级时间复杂度
public int sum(int n) { int sum = 0; int count = 2; for (int i = 0; i <n ; i++) { count = count*2; } for (int i = 0; i < count; i++) { sum += n; for (int j = 0; j < n; j++) { sum += j; } } return sum; }
稍微复杂点的时间复杂度：
上面的时间复杂度都涉及到了对数，所以为了了解上面几种时间复杂度，我们首先要知道什么情况下会出现对数的时间复杂度，示例如下：
public void test(int n){ int i = 1; while (i<n){ i = i*2; } }
根据我们之前的分析，我们主要关系i=i*2这行代码的运行次数，假设其运行次数为x，则有如下公式：
则：
所以此示例中时间复杂度可记为：
我们知道，任意对数的底是可以替换的，如：
所以，我们统一将这种时间复杂度记为：
到现在，我们已经知道了对数级的时间复杂度的由来，那么形如:
这种形式的时间复杂度又是怎么来的呢？
我们要记住一个公式：
嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，什么意思呢？我们举例说明：
public void test(int n){ for (int i = 0; i < n; i++) { int x = 1; while (x<n){ x= x*2; } } }
可以看到，我们将一个时间复杂度为logn的算法循环执行了n次，那么这个算法的复杂度就为：
同样，我们也能知道：
的由来了，我也不再赘述了
在文章的最后，我想应该将常用的算法复杂度按增长速度从底到高整理了一下，让大家对这些复杂度能有个评判标准，由底到高分别为：
1.长度，O(n)
2.对数，O(logn)
3.对数平方数
4.线性：O(n)
5.
6.二次
7.三次
8.指数
结尾：
在这篇文章中，主要跟大家一起学习了一些基础的时间复杂度的分析，但是知道这些是远远不够的，复杂度的分析是我们学习算法的基石，预计还会有一篇文章，主要对最好，最坏，平均，均摊时间复杂度进行分析，另外会跟大家一起分析一个算法复杂度的题目，希望大家能跟我一起学到东西！
