复杂度分析¶

学习目标¶

学完本章后，学习者应该能够：

理解时间复杂度和空间复杂度。
使用大 O 表示法描述代码成本。
区分最好、最坏、平均和摊还复杂度。
能分析常见 Go 代码片段的复杂度。

为什么需要复杂度¶

复杂度用于回答一个问题：当数据规模变大时，程序成本如何增长。

例如，同样是查找一个用户：

遍历 slice：用户越多，查找越慢。
使用 map：通常可以接近常数时间查找。
使用数据库索引：可以避免全表扫描。

在小数据量下，很多写法都能跑。但后端服务经常面对增长的用户、请求、日志、消息和数据表。复杂度意识能帮助我们提前避开明显的性能陷阱。

时间复杂度¶

时间复杂度描述运行时间随输入规模增长的趋势。

常见复杂度：

复杂度	名称	常见场景
O(1)	常数时间	map 查询、数组按下标访问
O(log n)	对数时间	二分查找、堆操作、平衡树查询
O(n)	线性时间	遍历列表
O(n log n)	线性对数时间	快速排序、归并排序、堆排序
O(n²)	平方时间	双重循环、朴素两两比较
O(2ⁿ)	指数时间	没有剪枝的组合枚举

大 O 不关心具体机器跑了多少毫秒，而关心规模增长时的趋势。

空间复杂度¶

空间复杂度描述算法额外使用的内存随输入规模增长的趋势。

例如：

原地交换数组元素：额外空间 O(1)。
复制一份数组：额外空间 O(n)。
构建二维 DP 表：额外空间 O(nm)。

后端工程里，空间复杂度常常直接对应内存压力。一次性把几十万条记录读进内存，复杂度可能只是 O(n)，但 n 足够大时仍然会导致 OOM。

最好、最坏、平均情况¶

同一个算法在不同输入下表现可能不同。

例如线性查找：

最好情况：第一个元素就是目标，O(1)。
最坏情况：最后一个元素才是目标，或不存在，O(n)。
平均情况：大约检查一半元素，仍然是 O(n)。

工程上更关心最坏情况和高峰情况，因为线上事故往往发生在极端输入、异常流量或依赖变慢时。

摊还复杂度¶

摊还复杂度用于分析一组操作的平均成本。

Go 的 slice append 就是常见例子。大多数 append 是 O(1)，但容量不够时会扩容并复制旧数据，这次操作是 O(n)。如果把多次 append 平均来看，单次 append 的摊还复杂度仍可认为是 O(1)。

示例：

nums := make([]int, 0)
for i := 0; i < 1000; i++ {
    nums = append(nums, i)
}

这段代码不是每次都复制整个底层数组，但扩容发生时会有额外成本。

分析 Go 代码复杂度¶

单层循环¶

func sum(nums []int) int {
    total := 0
    for _, n := range nums {
        total += n
    }
    return total
}

时间复杂度是 O(n)，空间复杂度是 O(1)。

双重循环¶

func hasDuplicate(nums []int) bool {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] == nums[j] {
                return true
            }
        }
    }
    return false
}

最坏时间复杂度是 O(n²)，空间复杂度是 O(1)。

可以用 map 优化：

func hasDuplicateFast(nums []int) bool {
    seen := make(map[int]struct{}, len(nums))
    for _, n := range nums {
        if _, ok := seen[n]; ok {
            return true
        }
        seen[n] = struct{}{}
    }
    return false
}

时间复杂度通常是 O(n)，空间复杂度是 O(n)。

这就是典型的“用空间换时间”。

工程实践¶

选择数据结构前先看访问模式¶

如果业务需要按 ID 快速查找，map 通常比 slice 遍历合适。

如果业务需要保持顺序，slice 更简单。

如果业务需要频繁取最大或最小值，堆比每次排序更合适。

如果业务需要范围查询，树或数据库索引比哈希结构更适合。

大数据量下避免隐藏的 O(n)¶

一些看起来很小的操作，在循环里会变成大问题：

循环里不断拼接字符串。
每次请求都全量扫描配置。
对大列表重复排序。
查询结果不分页。
对每个元素都访问一次远程服务。

Go 后端实际应用例子¶

例子一：把批量用户查询从 O(nm) 优化到 O(n+m)¶

假设接口收到一批用户 ID，需要从已经加载的用户列表中筛选出匹配用户。新手容易写出双重循环：

type User struct {
    ID   int64
    Name string
}

func FilterUsersSlow(users []User, ids []int64) []User {
    result := make([]User, 0)
    for _, id := range ids {
        for _, user := range users {
            if user.ID == id {
                result = append(result, user)
                break
            }
        }
    }
    return result
}

如果 users 和 ids 都很大，这就是 O(nm)。更好的方式是先用 map 建索引：

func FilterUsersFast(users []User, ids []int64) []User {
    userByID := make(map[int64]User, len(users))
    for _, user := range users {
        userByID[user.ID] = user
    }

    result := make([]User, 0, len(ids))
    for _, id := range ids {
        if user, ok := userByID[id]; ok {
            result = append(result, user)
        }
    }
    return result
}

优化后时间复杂度通常是 O(n+m)，代价是额外 O(n) 内存。这种模式在权限匹配、批量补全用户信息、订单列表补齐商品信息时很常见。

例子二：接口返回列表时预分配 slice¶

如果能提前知道结果数量，可以预分配容量，减少扩容次数：

func UserNames(users []User) []string {
    names := make([]string, 0, len(users))
    for _, user := range users {
        names = append(names, user.Name)
    }
    return names
}

这不是算法题技巧，而是 Go 后端里非常常见的低成本优化。

常见误区¶

误区一：复杂度只在算法题里有用。

实际上，接口慢、内存高、数据库压力大，很多都和复杂度有关。

误区二：O(1) 一定比 O(log n) 快。

大 O 忽略常数因子。小数据量下，简单的 O(n) 可能比复杂结构更快、更容易维护。

误区三：只看时间复杂度。

后端服务也要关注空间复杂度、网络 IO、数据库 IO 和锁竞争。

实战任务¶

分析下面函数的时间复杂度和空间复杂度，并尝试优化：

func countExists(a []int, b []int) int {
    count := 0
    for _, x := range a {
        for _, y := range b {
            if x == y {
                count++
                break
            }
        }
    }
    return count
}

要求：

写出原始复杂度。
用 map 优化。
写出优化后的复杂度。
思考这种优化付出了什么代价。

参考答案

原始实现中，外层遍历 a，内层遍历 b，最坏情况下需要比较 len(a) * len(b) 次，所以时间复杂度是 O(nm)，空间复杂度是 O(1)。

可以先把 b 转成 set，再遍历 a：

func countExistsFast(a []int, b []int) int {
    set := make(map[int]struct{}, len(b))
    for _, y := range b {
        set[y] = struct{}{}
    }

    count := 0
    for _, x := range a {
        if _, ok := set[x]; ok {
            count++
        }
    }
    return count
}

优化后时间复杂度通常是 O(n+m)，空间复杂度是 O(m)。代价是额外内存，以及 map 构建成本。若 b 很小或只执行一次，原始写法可能也可以接受；若数据量大或高频调用，map 优化更合适。

面试题¶

1. 什么是时间复杂度？它解决什么问题？¶

参考答案

时间复杂度描述算法运行时间随输入规模增长的趋势。它不关心具体机器上的毫秒数，而是关心数据量变大时，运行成本按什么速度增长。

它解决的问题是帮助工程师在设计代码时预估性能风险。例如 O(n²) 的逻辑在 100 条数据时可能没问题，但在 10 万条数据时可能完全不可用。

2. 什么是空间复杂度？为什么后端工程师也要关心？¶

参考答案

空间复杂度描述算法额外占用内存随输入规模增长的趋势。后端工程师需要关心它，因为服务运行内存有限，尤其在容器和 Kubernetes 中通常有明确 memory limit。

查询大量数据、不分页导出、缓存无限增长、构建大 map 或大数组，都可能带来内存压力，严重时导致 OOM。

3. 如何理解“用空间换时间”？¶

参考答案

用空间换时间是指通过额外数据结构减少计算成本。例如判断重复元素时，双重循环是 O(n²)，使用 map 记录已见元素后，通常可以变成 O(n)，但额外使用 O(n) 内存。

工程上要判断是否值得。如果数据量小，简单遍历可能更清晰；如果数据量大或请求频繁，额外内存换取更低延迟通常是合理的。

4. 为什么不能只看大 O？¶

参考答案

大 O 忽略常数因子、硬件差异、缓存局部性、网络 IO、数据库 IO、锁竞争和实现复杂度。两个同样 O(n) 的算法，实际性能可能差很多。

工程中应该把复杂度作为第一层判断，再结合基准测试、压测、可读性和维护成本做最终选择。

5. Go 中 slice append 的摊还复杂度是什么？¶

参考答案

多数情况下，append 只是把元素写入已有容量，成本接近 O(1)。当容量不足时，运行时会分配更大的底层数组并复制旧元素，这次操作是 O(n)。

把多次 append 平均来看，单次 append 的摊还复杂度通常认为是 O(1)。如果能预估大小，使用 make([]T, 0, n) 预分配容量可以减少扩容和复制成本。