时间复杂度和空间复杂度怎么算？大 O 表示法看完就懂

刚开始学算法那会儿，我老把时间复杂度和空间复杂度搞混，背了一堆 O(n)、O(log n) 却不知道怎么从代码里推出来。

这篇就把怎么算讲清楚，全程用 Go 代码举例，看完你自己就能估算一段代码跑得快不快、占多少内存。

时间复杂度是什么？怎么算

时间复杂度衡量的是算法运行时间随数据规模 n 增长的变化趋势，不是真实秒数。

我们一般只看最坏情况，也就是最大执行次数，用大 O 表示法记成 O(f(n))。

算的时候记住三步：

1. 找出算法里执行次数最多的关键操作
2. 数这个操作随 n 增长大概执行了多少次
3. 只保留最高阶项、去掉系数，写成 O(…)

第三步是关键。

比如某段代码执行了 3n² + 5n + 100 次，n 一大，n² 起决定作用，常数和低阶项直接丢掉，结果就是 O(n²)。

常见时间复杂度速查表

下面这张表按增长速度从慢到快排，n 越大，越靠右的算法越吃亏。

记一个直觉：n = 1000 时，O(log n) 大约才 10，O(n) 是 1000，O(n²) 已经一百万，O(2ⁿ) 直接天文数字。

所以面试里看到指数级解法，基本就是在提示你「该优化了」。

O(1) 常数阶

不管 n 多大，操作次数固定，这就是 O(1)。

func sum(n int) int {
    s := 0          // 执行一次
    s = (1 + n) * n / 2 // 执行一次
    return s        // 执行一次
}

这里用等差数列公式直接算，跟 n 没关系，永远是几次操作。

O(log n) 对数阶

循环里变量每次翻倍（或减半），执行次数就是 log₂n。

func logN(n int) {
    i := 1
    for i < n {
        i = i * 2 // 每次翻倍，跑 log2(n) 次后退出
    }
}

n = 10 时，i 走 1→2→4→8→16，做了 4 次乘法就跳出，log₂10 约等于 3.32，对得上。

二分查找就是这个量级，每次砍掉一半数据。

O(n) 线性阶

关键操作总共执行 n 次。

func linear(arr []int) int {
    s := 0
    for i := 0; i < len(arr); i++ {
        s += arr[i] // 执行 n 次
    }
    return s
}

一层循环走完整个数组，最常见的情况。

O(n log n) 线性对数阶

外层 n 次，内层 log n 次，乘起来就是 n log n。主流的高效排序基本都卡在这个量级。

func nLogN(n int) {
    for i := 0; i < n; i++ { // 外层 n 次
        j := 1
        for j < n {
            j = j * 2 // 内层 log n 次
        }
    }
}

O(n²) 平方阶

两层嵌套循环，里外都是 n。

func square(n int) {
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            // 执行 n*n 次
        }
    }
}

冒泡、选择、插入排序都是 O(n²)。数据量一上来就明显卡。

O(n³) 与 O(2ⁿ)

三层嵌套是 O(n³)，朴素矩阵乘法是典型。

而像下面这种不加记忆化的递归斐波那契，每次分裂成两个子调用，复杂度直接到 O(2ⁿ)：

func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2) // 每层翻倍，O(2^n)
}

算 fib(40) 还能忍，到 fib(50) 就慢到怀疑人生。这种一般用动态规划或记忆化优化到 O(n)。

空间复杂度怎么算

空间复杂度衡量算法运行时额外占用的内存随 n 的增长趋势，同样取最坏情况，记成 O(…)。

注意两个字：额外。输入数据本身占的空间不算，只算算法过程中新开的内存。

主要看两块：

• 新申请的变量、数组、栈、队列等数据结构
• 递归调用占用的栈空间（递归有多深，栈就压多深）

O(1)：只用了几个变量

func space1(arr []int) int {
    s := 0 // 不管 arr 多大，只多一个变量
    for _, v := range arr {
        s += v
    }
    return s
}

虽然遍历了整个数组，但额外空间只有 s 一个，所以是 O(1)。

这里很容易踩坑——时间复杂度是 O(n)，空间复杂度却是 O(1)，两者是分开算的。

O(n)：开了一个和 n 同规模的数组

func spaceN(n int) {
    // 额外申请长度 n+1 的切片，空间复杂度 O(n)
    sli := make([]int, n+1)
    _ = sli
}

make([]int, n) 这种和输入规模成正比的额外结构，就是 O(n)。

递归的空间别忘了栈

递归虽然没显式开数组，但每层调用都要在调用栈上留一帧。

比如前面那个 fib，递归最深到 n 层，所以它的空间复杂度是 O(n)，而不是 O(1)。

这块我刚学时也忽略过，以为没 new 东西就是 O(1)，结果实际跑深递归直接栈溢出。

关键数据一览

• 去系数去低阶：3n² + 5n 记作 O(n²)
• 嵌套循环相乘，并列循环相加
• 时间和空间分开算，互不影响
• 递归时间看调用总次数，空间看递归最大深度
• 同一份输入，最坏情况才是我们关心的上界

常见问题 FAQ

时间复杂度和空间复杂度有什么区别？

时间复杂度衡量运行时间随数据规模的增长趋势，空间复杂度衡量额外内存的增长趋势。

两者独立计算，一个算法完全可能时间 O(n)、空间 O(1)。

为什么大 O 要去掉系数和低阶项？

因为大 O 描述的是 n 趋于无穷时的增长量级。

n 足够大时，最高阶项占绝对主导，常数和低阶项的影响可以忽略，这样不同算法之间才好横向比较。

O(log n) 里的对数是以几为底？

通常是以 2 为底，因为很多算法每步把问题规模减半。

不过在大 O 记法里底数其实无所谓——换底只差一个常数系数，会被一并省略，所以一般直接写 O(log n)。

怎么快速判断一段代码的时间复杂度？

数循环层数最直接： 单层循环大概率 O(n)，双层嵌套 O(n²)；

循环变量每次翻倍或减半是 O(log n)；

递归则看「调用总次数」。

把这几条对着代码套一遍基本够用。

递归算法的空间复杂度怎么算？

看递归的最大深度。

每深一层就在调用栈上多压一帧，深度为 n 的递归空间复杂度就是 O(n)。

如果还在递归里开了数组，再把那部分加进去取最高阶。

写在最后

复杂度分析说白了就两件事：看循环和递归的增长趋势，然后只留最高阶。

多对着代码推几遍就形成肌肉记忆了。

这篇里的例子都是我自己学的时候反复绕过弯的点，尤其是「时间和空间要分开算」「递归别忘了栈空间」，建议重点记一下。

如果你对某个量级的推导还有疑问，或者遇到拿不准复杂度的代码，欢迎在评论区贴出来一起聊～～～