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

算法之旅:复杂度分析

今天正式开启算法之旅!

作为一个合格的技术人员,算法是必备知识。可以这么说,虽然不懂算法的人并不会失业,但如果你想快速晋升摆脱业务工程师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: 每日一算法,由浅入深,欢迎加入一起共勉。

支持一下
赞赏是一门艺术