盒子
盒子
文章目录
  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
10
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
17
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
17
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),因为存在nm两个不同规模的数据,所以不能直接合并,只能共存。

举一反三,对于nm嵌套的情况,就可以按照乘法法则进行运行。例如:

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)

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

  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&DataBindingMVVM;项目中使用了ArouterRetrofitCoroutineGlideDaggerHilt等流行开源技术。

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

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

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

支持一下
赞赏是一门艺术