从小卖部批发辣条到算法复杂度分析
概览
1.为什么需要复杂度分析2.大O复杂度表示法3.时间复杂度4.空间复杂度
为什么需要复杂度分析
复杂度分析对数据结构和算法来说很重要，据说占了大半的江山，不知道实际是不是这样子的。我们先来聊聊为什么要学习复杂度分析，最直接的说，我们把代码运行一遍，不就得到结果了，而且比分析出来的结果还要准确。我们先从小卖部聊起，因为学校的规定，所有的零食都需要从学校门口运到宿舍，这时候我们需要最高效的运输方法，每次运送多少，运送多少次。这时候难道我们还要去实际体验几趟吗？来回把东西搬运几次，这第二天要上校园头条了：六栋门口惊现矿水哥，来回抱着几提矿泉水往返宿舍和校园门口……代码的运行速度受限于电脑配置，就像邮寄东西的速度受限于快递，我们接着从豆豆的小卖部下手，家在海南的小伙伴在小卖部订购了一箱干脆面，豆豆同学使用快递寄送，可选择的快递有顺丰和邮政，顺丰第二天到，邮政下周到，你说这个复杂度是二还是七呢？同一个算法同一个机器的结果一定是一样的吗？假定小卖部使用同一个小拖车运货，小拖车标准承载重量为2Kg，运货路线使用A路线不改变，供应商第一次送来1KG的辣条，运送了一次。第二次送来了5KG的辣条，小拖车拼死拼活超载两趟运完了。请问一下，这个小拖车A路运货的复杂度怎么讲呢？
这时候，如果有一个能估算出不同选择的执行效率的方法是不是更好呢？
大 O 复杂度表示法
假设我们对实际的情况进行抽象处理，不考虑复杂的显示情况，把一些条件简单化，得出一个方案或者一段代码的执行时间。
假设一个方案里面的每一步的消耗时间都是一样的，每一步操作都是1个时间单位，那么小卖部每次用小拖车搬货就分为三步：装箱，运输，卸货。每次补货需要消耗的时间就跟这三步走的次数相关了。一个方案的执行时间与每个拆分步骤的执行次数成正比。
从小卖部回到代码上来，一段代码的运行的时间也和每行代码的运行时间相关，以下面的代码为例：
public void sum(int n){ int sum = 0; for(int i = 1;i <= n; ++i){ sum = sum + i; } System.out.println(sum); }
忽略细节上的差异，假定每一句代码的执行时间为1时间单位t，上面这段代码的总共时间消耗是多少呢？
这段代码有两次初始化操作，分别是 i 和 sum，消耗时间就是 2 * t ；
i <= n、 ++i 和 sum = sum + i 这三段代码处于循环之中，执行时间和循环次数 n 相关，执行时间可以记作 3n 。这一段代码的执行时间就可以记作3n+2。
我们用公式表达出来就如下所示：
T(n) = O(f(n)) = O(3n+2)
这种表达方式也就是大O时间复杂度表示法，这种方式并不能表达出来代码的实际执行时间，表达的是代码执行时间随数据规模增长的变化趋势，所以也称作渐进时间复杂度，简称时间复杂度。
当表达式中的n越来越大时，整个表达式结果就会由其中一个变化最大的一部分的影响， 这时候我们就可以忽略掉一些影响不大的参数，比如表达式中的常量、系数等，这时候上面的表达式就可以简单记为：T(n)=O(n)。
当我们遇到更加复杂的表达式时，例如遇到包含平方，三次方这种更高级的存在时，我们也可以把低阶去除掉，比如：T(n) = O(3n²+2n+1)，这时候就可以写成T(n) = O(n²) 。
时间复杂度分析
我们在上面已经讲过了大O复杂度的表示方式，接下来补充一些简单的分析方法。
1. 相同变化级別寻找最大量级的代码块
相对于整个结果来说，我们可以根据实际忽略掉表达式中的常量、系数、低阶等，最终的结果相当于最大阶的量级。就像搬货的过程中，去了一趟厕所，整个搬运零食的过程就可以忽略掉这次上厕所的时间，只记搬运货物的次数消耗的时间。
依旧使用上面的代码，我们用这个方法分析一下：
public void sum(int n){ int sum = 0; for(int i = 1;i <= n; ++i){ sum = sum + i; } System.out.println(sum); }
只关注运算量级最大的那一部分，是不是只需要关注循环的那一部分就可以了，这时候忽略系数，只要记作O(n)，也就是这段代码的时间复杂度。
当一段代码包含多个代码块时，如果变化的量都相同时，我们只需变化量最大的那一块。比如卡卡吃辣条，吃n包辣条，吃完以后需要喝n/2杯矿泉水，那么这个时间复杂度该怎么表示呢？
2. 不同变化级别的代码段求和
同样是吃辣条，豆豆吃了n包辣条，然后喝了m杯水，假设吃一包辣条和喝一杯水的时间相同，那么此时的时间复杂度是多少呢？在不确定m和n到底哪个比较大的情况下，我们就要把两个值加起来，那么这个复杂度就是O(n+m)。
转化为代码如下所示：
public void sum(int n, int m){ int sum = 0; // 豆豆吃了n包辣条 for(int i = 1;i <= n; ++i){ sum = sum + n; } // 豆豆喝水的次数 for(int j = 1;i <= m; ++i){ sum = sum + m; } System.out.println(sum); }
3. 不同变化级别的嵌套代码求积
比如，豆豆去搬运辣条，从校门口到寝室的次运输次数记做n，每次搬运到寝室以后，不急着去搬运第二趟，还要休息一会，会把运到的辣条进行分类，放到指定的位置，这时候分类的操作需要的时间记做m，那么这么一次完整的操作，总的下来的复杂度就是O(n*m)。
转化为代码如下所示：
public void sum(int n, int m){ int sum = 0; // 豆豆搬运的辣条次数 for(int i = 1;i <= n; ++i){ // 豆豆分类辣条的次数 for(int j = 1;i <= m; ++i){ sum = sum + i * m; } } System.out.println(sum); }
常见的算法复杂度
我们经常接触的算法中有一些常见的算法复杂度需要了解一下，如下图所示：
在上面的复杂度里面，可以划分为多项式量级和非多项式量级两种，非多项式量级只有两个：指数阶和阶乘阶。
简单的聊聊其中的两个，常量阶和对数阶。
常量阶O(1)
常量阶并不真的就是1，它是一种指代，只要能确定代码的运行的次数，并不会随着数据量的提升而变的更复杂，这就是常量阶的复杂度，简称就是O(1)。
对数阶O(logn)
对数阶的复杂度不容易理解，但这个也是很常见的算法。很简单的来说，豆豆要把辣条放到货架上，每只手可以拿一包辣条，一次就能放上去两包辣条，那么n包辣条需要多少次呢？这个算不算对数阶段的操作呢？
转化成对应的代码如下所示：
int i = 1； while(i <= n) { i = i * 2; }
这个掰下手指头算一算，是不是一个很熟悉的操作，好像在哪见过。
不管这个底数是2还是10，当我们使用大O标记复杂度时，都会记为O(logn)，这是为什么呢？
在最最最开始的时候，我们讲过，大O方法表示复杂度的时候，是可以忽略系数的，那么这个算法就可以做一次转换。
如上图所示，忽略系数的情况下，不管是几为底的对数阶时间复杂度，最终的结果都是一样的，所以最后被记做为O(logn)，那么O(nlogn)也是同样的道理。
空间复杂度
相对来说空间复杂度就会简单很多，时间复杂度全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。同样的道理，空间复杂度就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
空间的复杂度主要是计算变量的存储空间大小，辣条运送到小卖部的路途中是不是需要地方存储， 这时候是不是需要一些空间，这个空间的复杂度理解起来和时间复杂度类似。甚至来说会更简单。
空间复杂度主要集中在变量的占用，在同样忽略常量、系数、低阶的情况下，我们得到一个大概的空间复杂度。常见的空间复杂度主要包括：常量阶O(1)、 线性阶O(n)、 O(n²)，这里少了对数阶复杂度，学习起来也没有那么难。
