系列文章请查看 「数据结构&算法」必知必会系列:1. 开篇#计划路线

Why

先举个简单 🌰,1+2+3 … + 10 = ? 如果不知道求和公式,我们只能循环做加法计算。

那如果不是 +10,而是加到 n 呢?程序可帮我们实现此算法,参考 go 代码如下:

s := 0
for i := 1; i <= n; i++ {
    s = s + i
}

那如果使用数学公式,是不是简单呢? s=(1+n)*n/2

凭感觉,你觉得是循环快还是公式快?🙌 公式快 =》相信感觉,算法复杂度分析个人认为感觉很重要 😁

再举个 🌰,两个数和是 10,差是 2,这两个数分别是几?可能会想到这么两种方式(二元 & 一元方程)

x + x + 2 = 10 => x=4, x+2=6

x + y = 10

x - y =2

依然凭感觉,觉得哪个占用了更多的空间?🙌 二元 =》在程序中,引入更多变量的确更占内存空间 😝

言归正传,数据结构&算法本质就是解决「快」和「省」,如何评判算法好坏的重要考察因素就是其执行效率,而衡量的标准就引出了本文的主题「时间复杂度」和「空间复杂度」。

可能,有人会想搞得那么复杂干嘛… 写完程序后测试其执行的时间不就可以了? 的确,这是一种方法。如,通过统计、监控得到算法执行的时间和占用的内存大小。像 LeetCode 会给出一个参考运行时间和内存消耗。

但是,实际测试非常依赖测试环境以及测试数据规模。

那么,算法好坏与否怎样在除去环境(硬件执行,编译效率)因素,来进行评判呢?

不用具体的测试数据来测试,粗略地估计算法的执行效率的方法 =》时间 & 空间复杂度分析方法。

What

时间复杂度

回到第一个 🌰 循环累加 1+2+3 … + n = ?,参考 go 代码如下:

s := 0
for i := 1; i < n; i++ {
    s = s + i
}

假设每个语句的执行时间是 unit_time。那这段代码的总执行时间 T(n) 是多少呢?

🙌 2n - 1 次

💡 第一行 1 次;第二行代码运行了 n-1 次,第三行也运行了 n-1 次

T(n) = (1 + n - 1 + n - 1) * unit_time = (2n - 1) * unit_time


再举个略有点复杂 🌰 参考 go 代码如下:

sum := 0
for i := 1; i <= n; i++ {
    for j := 1; j <= n; j++ {
        sum = sum + i*j
    }
}

总执行时间 T(n) 是多少呢?

🙌 1 + n*2n 次

💡 第二行 n 次;在第一个循环的每次执行中,第三、四行分别都运行了 n 次

T(n) = (1+n*2n) * unit_time = 1 + 2n² * unit_time

大O 表示法

我们发现:代码的执行时间 T(n) 与每行代码的执行次数(unit_time)成正比,把这个规律总结成一个公式。

注意!!大名鼎鼎的 「大O」 表示法

大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

当 n 很大时,你可以把它想象成 1000000、100000000 =》∞。而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录一个最大量级就可以了。

如果用大O 表示法表示上面两个 🌰 代码的时间复杂度,可以记为:T(n) = O(n) 以及 T(n) = O(n²) 。

如果有数学极限值相关的思想可能比较容易理解。低阶、常量、系数不左右趋势 =》仅记录 最大量级

空间复杂度

时间复杂度表示算法的执行时间与数据规模之间的增长关系。类比一下,空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系。

还是那个 🌰 ,参考 go 代码如下:

sum := 0
for i := 1; i <= n; i++ {
    for j := 1; j <= n; j++ {
        sum = sum + i*j
    }
}

随着n的变化,所需内存空间并不会随着n的变化而变化(有限个变量,本例为3个),整体为 O(1)

但是,如果我们引入数组,参考 go 代码如下(go 中可变数组为切片,此代码可直接执行 https://play.golang.org/p/NyzlNGhcpyD):

package main

import (
    "fmt"
)

func printSlice(s []int) {
    fmt.Printf("len=%d cap=%d %v\n", len(s), cap(s), s)
}

func main() {
    var s []int
    printSlice(s)

    n := 10
    for i := 1; i <= n; i++ {
        s = append(s, i)
        printSlice(s)
    }
}

非 go 语言使用者可能有点难读,仅理解为向切片 s 中加入累加变量 i 即可,打印长度及容量跟随 n 增长而增长。其空间复杂度为 O(n)

常见的空间复杂度就是 O(1)、O(n)、O(n² )。相对来说,空间复杂度分析比时间复杂度分析要简单很多。

How

看完上面的 What ,有没有觉得「时间复杂度」和「空间复杂度」已经有点概念和感觉了?

很好,下面该具体介绍如何分析「时间复杂度」和「空间复杂度」。

但是,本文篇幅已经略长了,预知如何,请看下回分解 (づ ̄3 ̄)づ╭❤~

计划的内容预告 👀 ↓