算法之旅:复杂度分析
今天正式开启算法之旅！
作为一个合格的技术人员，算法是必备知识。可以这么说，虽然不懂算法的人并不会失业，但如果你想快速晋升摆脱业务工程师CRUD的命运就一定离不开算法。同时不管是对于工作还是面试都是非常有用的。
由于这是算法第一篇，所以我们先从简单的复杂度说起。
任何算法都离不开复杂度分析，衡量一个算法的强与弱，其中一个比较统一的标准就是看它们之间的复杂度。
你可能会有所疑问，为什么要看复杂度呢？我直接跑一下代码看执行时间不就完事了吗？
是的这样也能统计出时间，但这种方法存在非常大的局限性。
试想一下，你在这种情况下得到的结果是否非常依赖于所处的测试环境，例如同一段代码在2G与8G的手机上运行的时间能一样吗？
另外还有一个非常明显的缺陷是样本规模太小，同一算法可能对不同规模的数据会产生不同的效果。
例如对于小规模的排序，插入排序可能比快速排序更快。
所以我们需要一个更科学的方式来衡量算法的强与弱，而这个方法就是复杂度。
而算法的复杂度又分为时间复杂度与空间复杂度两大类。其实难点就是时间复杂度的计算，空间复杂度相对简单许多。
大O表示法
在说复杂度之前，我们再来了解一下它的表示方法。
我们先从一个简单的例子进行分析
fun test(n: Int) {
var i = 0 //1
while (i < n) { //2
var j = 0 //3
while (j < n) { //4
j++ //5
}
i++ //6
}
}
假设执行每一行代码的时间为k，那么上面的代码从上往下依次执行的时间总和为
T(n) = k + n * k + n * k + n^2 * k + n^2 * k + n * k
= (1 + 3 * n + 2 * n^2) * k
这个公式我们分解一下看，左边T(n)代表代码的执行时间，右边(1 + 3 * n + 2 * n^2)部分可以代表代码的执行次数总和，而k是每行代码的执行时间。
试想一下是否不管是什么代码都可以由这三部分组成呢？
答案自然是可以的。
那么上面的表示法就产生了一个重要的概念了：代码执行时间T(n)与代码的执行次数总和成正比。
有了这个规律，我们就可以将上面的表达式转换成大O来表示
T(n) = O(f(n))
其中n代表数据规模，T(n)代表代码的执行时间，f(n)代表代码的执行次数总和，大O代表代码执行时间T(n)与代码的执行次数总和成正比。
将表达式套入到f(n)中，最终表示为
T(n) = O(1 + 3 * n + 2 * n^2)
这就是大O表示法，它代表的并不是代码执行的真正时间，而是一种趋势，即代表执行时间随数据规模变化的趋势，业界称之为渐进时间复杂度，简称时间复杂度。
如果n的规模很大，那么我们就可以将常数、系数与低价进行忽略，因为它们已经不能左右趋势的变化。所以就得到我们日常所看到的结果
T(n) = O(n^2)
时间复杂度
说完大O表示法，现在正式分析时间复杂度。
我们考察一个算法，往往都要分析它的时间复杂度，那么时间复杂度又该如何又快又准的分析出来呢？
其实很简单，我教大家几个个方法，让你更加迅速与准确的得到时间复杂度。
贪心法则
何为贪心法则？简单来说就是找到你认为最复杂的那段代码，或者说循环次数最多的那段代码。
在大O表示法中已经说了，计算时间复杂度都会忽略常数、系数与低价，所以我们只需关注次数最多的那行代码。例如:
fun search(n: Int): Int {
var i = 0
var result = 0
while (i <= n) {
result+=i
i++
}
return result
}
这里一看就知道执行最多的代码在while循序中，所以用大O表示为
T(n) = O(3 * n)
= O(n)
注意这里不管有多少个平级的while循序，最终通过加法合并在一起，然后去掉常数，时间复杂度还是O(n)。例如：
fun search(n: Int): Int {
var i = 0
var result = 0
while (i <= n) {
result+=i
i++
}
var j = 0
while (j <= n) {
result+=j
j++
}
return result
}
求同存异
这种累计的只适用于单个规模的变量，如果处在多个规模的变量，就直接按照正常的加法运算进行保留即可。例如：
fun search(n: Int, m: Int): Int {
var i = 0
var result = 0
while (i <= n) {
result+=i
i++
}
var j = 0
while (j <= m) {
result+=j
j++
}
return result
}
此时时间复杂度为O(n+m),因为存在n、m两个不同规模的数据，所以不能直接合并，只能共存。
举一反三，对于n、m嵌套的情况，就可以按照乘法法则进行运行。例如：
fun search(n: Int, m: Int): Int {
var i = 0
var result = 0
while (i <= n) {
result+=i
i++
var j = 0
while (j <= m) {
result+=j
j++
}
}
return result
}
时间复杂度为O(n*m)
相对来说我们遇到的时间复杂度的样式并不多，主要为以下几种
- O(1)：常数阶
- O(n)：线性阶
- O(n^2)：平方阶
- O(logn)：对数阶
- O(nlogn)：线性对数阶
- O(2^n)：指数阶
- O(n!)：阶乘阶
而用的最多的就是O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)。
我们已经对O(n)与O(n^2)进行了举例，至于常数阶O(1)就不多说了，只要它没有循环体或者递归存在，那它的时间复杂度就是O(1)
下面再来分析下O(logn)与O(nlogn)
对数阶与线性对数阶
var i = 1
while(i < n)
{
i = i * 2
}
每次循环都将当前值乘以2，所以不难得出它的终止表达式为
2^0 , 2^1 , 2^2 , 2^3 , ... , 2^x = n
所以求得x等于log2^n，所以时间复杂度为O(log2^n)
如果我再将i = i * 2改成i = i * 3，其它都不变，此时时间复杂度为O(log3^n)
但是，根据对数之间的相互转换规律，log3^n = log3^2 * log2^n，所以O(log3^n)可以转成O(k * log2^n)。
其中k是常量可以进行忽略，所以转化之后它们都是O(log2^n)。
因此，在对数阶时间复杂度的表示方法里，我们忽略对数的底，统一表示为O(logn)。
那么对应的线性对数阶O(nlogn)也就是一样的，只是对对数阶的代码执行了n遍，原理都是一样的。
你可能还听说过最好时间复杂度、最坏时间复杂度、平均时间复杂度与均摊时间复杂度。其实它们也很好理解，本质就是字面上的意思，具体就不到这过多说明，后续遇到具体算法后再进行具体说明。
最后再附上一张它们之间的曲线图，来更加直观的看它们之间的变化趋势。
空间复杂度
分析完时间复杂度，再来看空间复杂度就简单许多了。
空间复杂度也是用大O来表示，空间复杂度也是渐进空间复杂度，表示算法之间的存储空间与数据规模之间的关系。
简单看一个例子
private fun test(n: Int) {
var i = 0
val temp = IntArray(n)
while (i < n) {
temp[i] = i + 1
}
}
在这里申请了一个n大小的temp数组，只有这一块有额外的空间申请，所以它的空间复杂度就是O(n)。
对于空间复杂度，我们常见的空间复杂度为：O(1)、O(n)与O(n^2)，而对于对数阶、线性对数阶、阶乘阶与指数阶都基本用不到。所以相对于时间复杂度的分析，空间复杂度更加简单。
这个也会在之后的算法中进行同步分析。
关于算法的复杂度今天就聊到这里，对于算法复杂度的分析，我们并不需要刻意的去找算法进行练习，只需在每次遇到的算法的时候有复杂度的这个概念，然后在写完算法之后进行分析对比即可。
为了感谢大家一直以来的支持，我在后台设置了一个粉丝专属抽奖活动，大家可以在公众号中回复公众号名称关键字来获取抽奖资格，开奖截止时间为12月1日。
注意关键字是公众号名称，也就是Android补给站。
在这里预祝大家中奖！