盒子
盒子
文章目录
  1. 大O表示法
  2. 时间复杂度
    1. 贪心法则
    2. 求同存异
    3. 对数阶与线性对数阶
  3. 空间复杂度
  4. 项目

算法之旅:复杂度分析

2020.12.03 Rouse 算法  热度 ℃

今天正式开启算法之旅！

作为一个合格的技术人员，算法是必备知识。可以这么说，虽然不懂算法的人并不会失业，但如果你想快速晋升摆脱业务工程师CRUD的命运就一定离不开算法。同时不管是对于工作还是面试都是非常有用的。

由于这是算法第一篇，所以我们先从简单的复杂度说起。

任何算法都离不开复杂度分析，衡量一个算法的强与弱，其中一个比较统一的标准就是看它们之间的复杂度。

你可能会有所疑问，为什么要看复杂度呢？我直接跑一下代码看执行时间不就完事了吗？

是的这样也能统计出时间，但这种方法存在非常大的局限性。

试想一下，你在这种情况下得到的结果是否非常依赖于所处的测试环境，例如同一段代码在2G与8G的手机上运行的时间能一样吗？

另外还有一个非常明显的缺陷是样本规模太小，同一算法可能对不同规模的数据会产生不同的效果。

例如对于小规模的排序，插入排序可能比快速排序更快。

所以我们需要一个更科学的方式来衡量算法的强与弱，而这个方法就是复杂度。

而算法的复杂度又分为时间复杂度与空间复杂度两大类。其实难点就是时间复杂度的计算，空间复杂度相对简单许多。

大O表示法

在说复杂度之前，我们再来了解一下它的表示方法。

我们先从一个简单的例子进行分析

1
2
3
4
5
6
7
8
9
10
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，那么上面的代码从上往下依次执行的时间总和为

1
2
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来表示

1
T(n) = O(f(n))

其中n代表数据规模，T(n)代表代码的执行时间，f(n)代表代码的执行次数总和，大O代表代码执行时间T(n)与代码的执行次数总和成正比。

将表达式套入到f(n)中，最终表示为

1
T(n) = O(1 + 3 * n + 2 * n^2)

这就是大O表示法，它代表的并不是代码执行的真正时间，而是一种趋势，即代表执行时间随数据规模变化的趋势，业界称之为渐进时间复杂度，简称时间复杂度。

如果n的规模很大，那么我们就可以将常数、系数与低价进行忽略，因为它们已经不能左右趋势的变化。所以就得到我们日常所看到的结果

1
T(n) = O(n^2)

时间复杂度

说完大O表示法，现在正式分析时间复杂度。

我们考察一个算法，往往都要分析它的时间复杂度，那么时间复杂度又该如何又快又准的分析出来呢？

其实很简单，我教大家几个个方法，让你更加迅速与准确的得到时间复杂度。

贪心法则

何为贪心法则？简单来说就是找到你认为最复杂的那段代码，或者说循环次数最多的那段代码。

在大O表示法中已经说了，计算时间复杂度都会忽略常数、系数与低价，所以我们只需关注次数最多的那行代码。例如:

1
2
3
4
5
6
7
8
9
fun search(n: Int): Int {
    var i = 0
    var result = 0
    while (i <= n) {
        result+=i
        i++
    }
    return result
}

这里一看就知道执行最多的代码在while循序中，所以用大O表示为

1
2
T(n) = O(3 * n)
     = O(n)

注意这里不管有多少个平级的while循序，最终通过加法合并在一起，然后去掉常数，时间复杂度还是O(n)。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
}

求同存异

这种累计的只适用于单个规模的变量，如果处在多个规模的变量，就直接按照正常的加法运算进行保留即可。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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嵌套的情况，就可以按照乘法法则进行运行。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)

相对来说我们遇到的时间复杂度的样式并不多，主要为以下几种

  1. O(1)：常数阶
  2. O(n)：线性阶
  3. O(n^2)：平方阶
  4. O(logn)：对数阶
  5. O(nlogn)：线性对数阶
  6. O(2^n)：指数阶
  7. 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)

对数阶与线性对数阶

1
2
3
4
5
var i = 1
while(i < n)
{
    i = i * 2
}

每次循环都将当前值乘以2，所以不难得出它的终止表达式为

1
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来表示，空间复杂度也是渐进空间复杂度，表示算法之间的存储空间与数据规模之间的关系。

简单看一个例子

1
2
3
4
5
6
7
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)，而对于对数阶、线性对数阶、阶乘阶与指数阶都基本用不到。所以相对于时间复杂度的分析，空间复杂度更加简单。

这个也会在之后的算法中进行同步分析。

关于算法的复杂度今天就聊到这里，对于算法复杂度的分析，我们并不需要刻意的去找算法进行练习，只需在每次遇到的算法的时候有复杂度的这个概念，然后在写完算法之后进行分析对比即可。

项目

android_startup: 提供一种在应用启动时能够更加简单、高效的方式来初始化组件，优化启动速度。不仅支持Jetpack App Startup的全部功能，还提供额外的同步与异步等待、线程控制与多进程支持等功能。

AwesomeGithub: 基于Github的客户端，纯练习项目，支持组件化开发，支持账户密码与认证登陆。使用Kotlin语言进行开发，项目架构是基于JetPack&DataBinding的MVVM；项目中使用了Arouter、Retrofit、Coroutine、Glide、Dagger与Hilt等流行开源技术。

flutter_github: 基于Flutter的跨平台版本Github客户端，与AwesomeGithub相对应。

android-api-analysis: 结合详细的Demo来全面解析Android相关的知识点, 帮助读者能够更快的掌握与理解所阐述的要点。

daily_algorithm: 每日一算法，由浅入深，欢迎加入一起共勉。

支持一下
赞赏是一门艺术