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

本文较为基础，若跳过可直接查看 「数据结构&算法」必知必会系列：3. 时间 & 空间复杂度（下）

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￣)づ╭❤～

计划的内容预告 👀 ↓