面试官最爱问：复杂度怎么分析？一看就懂的图解教程

一、引言

很多刚开始学习算法的同学，常常会陷入“写得出代码，但不知道效率高不高”的困境。
复杂度分析，就是帮助我们回答：

• o 这段代码跑得快不快？
• o 数据规模变大时，它还能跑得动吗？
• o 为什么有的算法能通过面试，有的却超时？

今天，我们用通俗的方式，把复杂度分析从 概念 → 方法 → 实例，逐步讲清楚，让初学者也能轻松入门。

二、为什么要学习复杂度分析？

想象一下：

• o 你写了一个程序，处理 100 条数据很快。
• o 但是当数据量变成 100 万时，程序可能需要几小时。

面试官不会给你那么多时间，他会让你写出在数据规模上升时依旧高效的解法。
所以，复杂度分析就是衡量算法效率的“放大镜”。

配图 1：不同复杂度随规模增长的趋势（对数刻度）

直观看到 O(1)、O(log n)、O(n)、O(n log n)、O(n^2)、O(2) 的增长速度差异。

配图1：常见时间复杂度增长趋势（log 纵轴）

三、复杂度的两大类

复杂度分为两类：

1. 1. 时间复杂度：算法运行需要多少时间。
2. 2. 空间复杂度：算法运行需要多少额外内存。

举例：

• o 遍历数组时，执行了多少次循环，就是时间复杂度。
• o 你是否新建了额外的数组或哈希表，就是空间复杂度。

四、常见时间复杂度等级

从低到高，常见复杂度有：

• o O(1)：常数级，效率最高。
• o O(log n)：对数级，常见于二分查找。
• o O(n)：线性级，最常见。
• o O(n log n)：对数线性级，比如归并排序。
• o O(n^2)：平方级，常见于两层循环。
• o O(2^n), O(n!)：指数级/阶乘级，几乎不可用。

小提示：同一个算法在小数据量下差异不明显，但当 n 很大时，复杂度差异会被“放大”。

五、案例解析

1）O(1) 常数复杂度

只做有限次操作，与输入规模无关。

    
    
    
  # Python
def print_first_element(arr):
    # 只访问一次：常数时间
    print(arr[0])

    
    
    
  // Swift
func printFirstElement(_ arr: [Int]) {
    // 只访问一次：常数时间
    print(arr[0])
}

2）O(n) 线性复杂度

循环一遍数组，每个元素访问一次。

    
    
    
  # Python
def traverse_array(arr):
    for num in arr:
        print(num)

    
    
    
  // Swift
func traverseArray(_ arr: [Int]) {
    for num in arr {
        print(num)
    }
}

3）O(n^2) 平方复杂度

两层循环，常见于查找所有配对。

    
    
    
  # Python
def pair_sum(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i], arr[j])

    
    
    
  // Swift
func pairSum(_ arr: [Int]) {
    for i in 0..<arr.count {
        for j in 0..<arr.count {
            print(arr[i], arr[j])
        }
    }
}

4）O(log n) 对数复杂度 —— 二分查找

二分查找的典型案例。

为什么是 O(log n)？（三步吃透）

1. 1. 过程：每次取中间元素比较，决定只在左半或右半继续找。搜索区间每次减半。
2. 2. 推导：比较了 k 次后，规模从 n 变为 n/2^k。当 n/2^k ≤ 1 时结束，解得 k ≥ log n。
3. 3. 直观：一本 1000 页的字典，顺序查找可能翻 1000 页；二分只需 ≈10 次（log 1000 ≈ 10）。

配图 2：二分查找每轮“区间减半”的过程

配图2：Binary Search 范围逐轮对半缩小

    
    
    
  # Python
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

    
    
    
  // Swift
func binarySearch(_ arr: [Int], _ target: Int) -> Int {
    var left = 0
    var right = arr.count - 1
    while left <= right {
        let mid = (left + right) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

5）O(n log n) 对数线性复杂度 —— 归并排序

“分而治之”的代表：先分成两半，递归排好，再合并。深度约为 log n，每层合并代价约 O(n)，总计 O(n log n)。

配图 3：归并排序——“分解成单个元素，再自底向上合并”

配图3：Merge Sort 的分解与合并结构示意

    
    
    
  # Python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:]); result.extend(right[j:])
    return result

    
    
    
  // Swift
func mergeSort(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    let mid = arr.count / 2
    let left = mergeSort(Array(arr[..<mid]))
    let right = mergeSort(Array(arr[mid...]))
    return merge(left, right)
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var result: [Int] = []
    var i = 0, j = 0
    while i < left.count && j < right.count {
        if left[i] < right[j] {
            result.append(left[i]); i += 1
        } else {
            result.append(right[j]); j += 1
        }
    }
    result.append(contentsOf: left[i...])
    result.append(contentsOf: right[j...])
    return result
}

六、空间复杂度示例

• o O(1)：只用常量空间，例如交换两个数。
• o O(n)：开辟一个额外数组存储结果。

    
    
    
  # Python - O(1) 空间
def swap(a, b):
    a, b = b, a
    return a, b

    
    
    
  // Swift - O(1) 空间
func swap(_ a: inout Int, _ b: inout Int) {
    let temp = a
    a = b
    b = temp
}

七、实战导向的“思维地图”

当你拿到一道题，不知道怎么优化时，可以从这些思路入手：

• o 二分（可否转成“单调 + 判定函数”？）
• o 哈希表（能否用额外空间换时间？）
• o 双指针（有序/区间问题常用）
• o 分治（能拆成相同子问题吗？）
• o 堆/优先队列（随时取最大/最小）
• o 动态规划（最优子结构 + 重叠子问题）

配图 4：常见算法“优化思路”地图

配图4：常见算法优化思路

八、总结与思考

1. 1. 时间复杂度衡量运行速度，空间复杂度衡量内存使用。
2. 2. 写代码时，别只考虑“能跑通”，还要考虑“跑得快”。
3. 3. 面试常考：o 让你分析一段代码的复杂度；o 让你用更优复杂度重写。

练习路径建议：

• o 第 1 阶段：能写出功能正确的暴力解法；
• o 第 2 阶段：学会二分、哈希、双指针等“常用优化”；
• o 第 3 阶段：掌握分治、堆、并查集、图算法、动态规划等“结构化思想”；
• o 第 4 阶段：熟练评估复杂度，能够做取舍与证明（如：为何再优化到 O(n) 不可行）。