通过代码示例理解 Big-O：轻松掌握算法复杂度

1. 总概

Big-O 是描述运行时间（或内存）随着输入大小增加而增长速度的方法。本文不用枯燥的数学公式，而是通过真实的 Java 代码走过每一种常见的复杂度等级，并分析哪些代码行引起了性能成本。读完之后，你看一段代码就能立即判断它是 O(1)、O(n)、O(n log n) 还是 O(n²)，不用手工计数。

2. Big-O 是什么，为什么需要关注

Big-O 回答的问题是：“如果输入增加一倍，运行时间会增加多少？” 它忽略常数和小因子，只保留 n（输入大小）趋于无穷大时的增长趋势。

n = 1000      -> O(n) 运行约 1000 步
n = 1000000  -> O(n) 运行约 1000000 步（线性增长）
n = 1000000  -> O(n²) 运行约 10^12 步（极速增长）

两段代码可能“看起来一样”，但如果其中一段在函数调用中隐藏着嵌套循环，复杂度会截然不同。理解 Big-O 能帮助你避免写出对 100 条测试记录表现良好但在生产环境中面对 1000 万条记录就“卡住”的代码。

注意： Big-O 描述的是最坏情况（worst case），这是最常见的约定，除非特别说明是最好情况或平均情况。

3. O(1) – 常数时间

运行时间不变，无论输入多大。

public class InventoryCache {

    private final Map<String, Integer> stockBySku = new HashMap<>();

    public Integer getStock(String sku) {
        return stockBySku.get(sku); // HashMap.get 平均情况下是 O(1)
    }
}

get() 在 HashMap 上计算 key 的哈希，然后直接跳转到相应的桶，不依赖于 map 中元素的数量。同样，使用 array[i] 或 ArrayList 上的 list.get(i) 也是 O(1)，因为只需计算地址偏移。

4. O(n) – 线性时间

运行时间与输入大小成正比增长。

public class OrderValidator {

    public boolean hasExpiredItem(List<Order> orders) {
        for (Order order : orders) {
            if (order.isExpired()) {
                return true; // 可能提前返回，但最坏情况下仍需遍历所有
            }
        }
        return false;
    }
}

for 循环最多遍历 orders 中的 n 个元素。最坏情况发生在没有任何订单已过期时，必须检查整个列表。这是典型的 O(n) 模式：单个循环，不嵌套。

4.1. 常见陷阱：循环中的 contains()

public class DuplicateChecker {

    // O(n²) 因为 List 上的 contains() 是 O(n)，循环 n 次
    public boolean hasDuplicateSlow(List<String> emails) {
        List<String> seen = new ArrayList<>();
        for (String email : emails) {
            if (seen.contains(email)) {
                return true;
            }
            seen.add(email);
        }
        return false;
    }
}

seen.contains(email) 在 ArrayList 上是 O(n)，因为必须线性遍历才能查找。在 for 循环内调用它将整个函数变成了 O(n²) — 当不注意数据结构细节时，这是一个非常常见的错误。

public class DuplicateChecker {

    // O(n) 因为 HashSet.add/contains 是 O(1)
    public boolean hasDuplicateFast(List<String> emails) {
        Set<String> seen = new HashSet<>();
        for (String email : emails) {
            if (!seen.add(email)) { // 如果已存在，add() 返回 false
                return true;
            }
        }
        return false;
    }
}

仅仅将 List 改为 HashSet，复杂度就从 O(n²) 降到了 O(n)。这是一个非常实际的例子，展示了选择正确的数据结构比“微观优化”更重要。

5. O(log n) – 对数时间

每一步都排除搜索空间的一半。

public class PriceLookup {

    // sortedPrices 必须预先按升序排序
    public int findIndex(int[] sortedPrices, int target) {
        int low = 0;
        int high = sortedPrices.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (sortedPrices[mid] == target) {
                return mid;
            } else if (sortedPrices[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

二分查找在每个 while 循环中将数组分成两半，所以对于 n = 1000000，只需大约 20 步（log₂ 1000000 ≈ 20）来找到结果，而不是线性遍历所有 100 万个元素。

class PriceLookupTest {

    @Test
    void shouldFindIndexInSortedArray() {
        int[] prices = {10, 20, 30, 40, 50};
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(prices, 40);

        assertThat(index).isEqualTo(3);
    }

    @Test
    void shouldReturnMinusOneWhenNotFound() {
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(new int[] {1, 2, 3}, 99);

        assertThat(index).isEqualTo(-1);
    }
}

这些测试验证了二分查找的两个关键分支的正确行为：找到时返回索引，未找到时返回 -1。

6. O(n log n) – 线性对数时间

这是高效排序算法（如归并排序、快速排序的平均情况，或 Collections.sort()）的复杂度。

public class RevenueReport {

    public List<Order> sortByAmountDescending(List<Order> orders) {
        List<Order> copy = new ArrayList<>(orders);
        copy.sort(Comparator.comparing(Order::amount).reversed()); // O(n log n)
        return copy;
    }
}

Java 中的 Collections.sort()/List.sort() 使用 Timsort（merge sort 的变体），保证最坏情况下为 O(n log n)。如果你看到 sort() 被调用在一个运行 n 次的循环内，总复杂度会乘以变成 O(n² log n) — 一个需要重构的信号。

7. O(n²) – 平方时间

两个嵌套循环，每个都遍历全部（或几乎全部）输入。

public class PairFinder {

    // 找到所有总价等于 target 的商品对
    public List<int[]> findPairsSlow(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[i] + prices[j] == target) {
                    result.add(new int[] {prices[i], prices[j]});
                }
            }
        }
        return result;
    }
}

外循环运行 n 次，内循环对每个外循环迭代最多运行 n 次 — 比较的总数大约是 n²/2，所以复杂度是 O(n²)。对于 n = 10000，这是 5000 万次比较 — 仍然可以运行，但会明显变慢。

public class PairFinder {

    // O(n) 因为 HashSet 存储已见的值
    public List<int[]> findPairsFast(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        for (int price : prices) {
            int complement = target - price;
            if (seen.contains(complement)) {
                result.add(new int[] {complement, price});
            }
            seen.add(price);
        }
        return result;
    }
}

与其比较每对数，我们只需一个单一循环和对 HashSet 的 O(1) 查询。这是“用空间换时间”的常见技巧：额外消耗空间来存储 seen，但将复杂度从 O(n²) 降到 O(n)。

8. O(2^n) – 指数时间

运行时间在输入增加 1 时翻倍 — 通常出现在递归函数中计算所有子集的情况。

public class SubsetGenerator {

    public List<List<Integer>> generateAllSubsets(List<Integer> items) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(items, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(List<Integer> items, int index,
                            List<Integer> current, List<List<Integer>> result) {
        if (index == items.size()) {
            result.add(new ArrayList<>(current));
            return;
        }
        // 分支 1：不选择 item[index]
        backtrack(items, index + 1, current, result);

        // 分支 2：选择 item[index]
        current.add(items.get(index));
        backtrack(items, index + 1, current, result);
        current.remove(current.size() - 1);
    }
}

每个元素创建 2 个递归分支（选择或不选择），所以有 n 个元素会产生 2^n 个子集。对于 n = 20，已经是超过 100 万个子集；n = 40 时没有机器能在合理时间内完成。这是寻找动态规划（dynamic programming）替代方案的信号（如果问题允许的话）。

9. 通过实际基准测试进行快速比较

一个简单的测试示例，让你“看到” O(n) 和 O(n²) 之间的差异：

class DuplicateCheckerBenchmarkTest {

    @Test
    void fastVersionShouldHandleLargeInputQuickly() {
        List<String> emails = new ArrayList<>();
        for (int i = 0; i < 100_000; i++) {
            emails.add("user" + i + "@example.com");
        }
        DuplicateChecker checker = new DuplicateChecker();

        long start = System.nanoTime();
        boolean hasDuplicate = checker.hasDuplicateFast(emails);
        long elapsedMs = (System.nanoTime() - start) / 1_000_000;

        assertThat(hasDuplicate).isFalse();
        assertThat(elapsedMs).isLessThan(500); // O(n) 所以即使有 10 万元素也很快
    }
}

如果你尝试将 hasDuplicateFast 改为 hasDuplicateSlow 并用同样的 10 万条邮件，运行时间会远远超过 500ms 阈值 — 在真实数据上直观证明了 O(n) 和 O(n²) 之间的差异。

10. 快速总结表和识别规则

Big-O	代码中的标志	例子
O(1)	没有循环，直接访问（数组索引、HashMap.get）	map.get(key)
O(log n)	每步排除搜索空间的一部分	二分查找
O(n)	单个循环遍历输入	for 遍历 List
O(n log n)	循环配合排序，或分治	Collections.sort()
O(n²)	循环嵌套循环，都遍历输入	比较每一对
O(2^n)	递归有 2 个分支，每步都执行，无剪枝	生成所有子集

快速计数规则：数一下嵌套循环的数量，都遍历输入 — 每个循环层级增加一个“幂次 n”。如果循环内调用库函数（contains、sort、indexOf），先查库函数的复杂度，再加到总和。

注意： Big-O 不会说真实的常数。一个 O(n) 算法如果常数很大（比如每次循环都读一次文件）可能比常数很小的 O(n log n) 算法更慢，至少在 n 不够大的情况下。不要盲目优化 Big-O，除非你测量过（profile）真实表现。

11. 结论

Big-O 是预测趋势的工具，不是绝对数字 — 但正是这个趋势决定了你的代码是否能在数据增长时存活或崩溃。最实用的建议是：每次写循环时，问问自己“这个循环里是否调用了 O(n) 的函数？” — 这是现实中大多数意外 O(n²) 错误的根源。掌握上面 6 种复杂度等级足以让你理解和评审你每天遇到的大部分算法代码。