算法复杂度分析：Big O 与性能评估

这一课你将能做到

1. 用大 O 表示法分析常见代码片段的时间复杂度
2. 估算程序在判题时限（2 秒）内能否通过
3. 理解时间换空间、空间换时间的权衡

为什么要学

复杂度是算法的「成绩单」。同样的功能，O(n) 和 O(n²) 在 n=10 万时差距是 10 万倍。不会分析复杂度，刷题就像蒙眼开车——不知道什么时候会撞墙。

人话：复杂度告诉你「数据量翻倍，时间翻几倍」。O(n) 是翻一倍，O(n²) 是翻四倍，O(log n) 是只加一点点。

先建立图像

n=10    n=100    n=1000   n=10000
O(1)      1        1        1        1
O(log n)  3        7       10       13
O(n)     10      100     1000    10000
O(n log n) 33    700    10000   140000
O(n²)   100    10000  1000000  100000000
O(2^n) 1024  1.3e30  天文数字  天文数字

2 秒时限，Java 大约能跑 2×10^8 次操作。对照上表，O(n²) 在 n=10^4 时就危险，n=10^5 时必死。

跟着做

步骤 1：O(1)——常数时间

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(arr[0]);  // 直接访问，O(1)
        System.out.println(arr.length); // 读属性，O(1)
    }
}

无论数据多大，操作次数固定。

步骤 2：O(n)——线性时间

public class Main {
    public static int sum(int[] arr) {
        int s = 0;
        for (int x : arr) s += x;  // 循环 n 次
        return s;
    }
    
    public static void main(String[] args) {
        int[] arr = new int[100000];
        System.out.println(sum(arr));
    }
}

数据量翻倍，时间翻倍。n=10^8 时大约 1 秒。

步骤 3：O(n²)——平方时间

public class Main {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {        // n 次
            for (int j = 0; j < n - 1; j++) { // n 次
                if (arr[j] > arr[j + 1]) {
                    int t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = new int[10000];
        bubbleSort(arr);  // n=10^4 时约 0.5 秒，n=10^5 时约 50 秒
    }
}

数据量翻倍，时间翻四倍。n=10^5 时必 TLE。

步骤 4：O(log n)——对数时间

public class Main {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 防溢出
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        System.out.println(binarySearch(arr, 7)); // 输出 3
    }
}

每次排除一半。n=10^9 也只要 30 次左右。

步骤 5：O(n log n)——线性对数

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9, 3};
        Arrays.sort(arr);  // 快排/归并，O(n log n)
        System.out.println(Arrays.toString(arr));
    }
}

高效排序的复杂度。n=10^7 时约 2 秒，是排序的极限。

步骤 6：空间复杂度

public class Main {
    // O(1) 空间：只用几个变量
    public static int sum1(int[] arr) {
        int s = 0;
        for (int x : arr) s += x;
        return s;
    }
    
    // O(n) 空间：开了新数组
    public static int[] copy(int[] arr) {
        int[] res = new int[arr.length];
        System.arraycopy(arr, 0, res, 0, arr.length);
        return res;
    }
    
    // O(n²) 空间：二维 DP 数组
    public static int[][] dpTable(int n) {
        return new int[n][n]; // n=10^4 时约 400MB，MLE
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        System.out.println(sum1(arr));
        System.out.println(Arrays.toString(copy(arr)));
    }
}

步骤 7：估算是否通过

public class Main {
    public static void main(String[] args) {
        int n = 100000; // 10^5
        
        // O(n) 约 10^5 次 → 毫秒级，稳过
        for (int i = 0; i < n; i++) { }
        
        // O(n log n) 约 1.7×10^6 次 → 毫秒级，稳过
        // Arrays.sort(arr);
        
        // O(n²) 约 10^10 次 → 100 秒，必挂
        // for (int i = 0; i < n; i++)
        //     for (int j = 0; j < n; j++) { }
        
        System.out.println("估算完成");
    }
}

讲清楚要点

1. 大 O 看趋势：忽略常数和低阶项。O(2n) 就是 O(n)，O(n²+n) 就是 O(n²)。
2. 最好、最坏、平均：快排平均 O(n log n)，最坏 O(n²)；哈希表平均 O(1)，最坏 O(n)。判题系统通常卡最坏情况。
3. 递归的复杂度：用主定理或画递归树。归并排序 T(n)=2T(n/2)+O(n)，解得 O(n log n)。
4. 空间换时间：哈希表用 O(n) 空间换 O(1) 查询；DP 用 O(n²) 空间换 O(n²) 时间（避免指数级）。

你可能会懵的地方

• O(n) 和 O(2n) 有区别吗？ 没有。大 O 表示渐近趋势，常数因子不影响分类。但判题时 2n 就是比 n 慢一倍，卡边界时可能挂。

• 为什么 O(n²) 在 n=10^5 时必死？ 10^5 × 10^5 = 10^10，Java 每秒约 10^8 次，需要 100 秒，远超 2 秒限制。

• O(log n) 的底数重要吗？ 不重要。换底公式 log₂n = log₁₀n / log₁₀2，差一个常数因子，大 O 忽略。

• 递归的栈空间算空间复杂度吗？ 算。递归深度 d 就是 O(d) 空间。深度超过 10^4 可能栈溢出。

• 怎么估算常数因子？ Java 的常数大约是 C 的 2-3 倍。简单循环按 10^8/秒估算，复杂操作（如字符串拼接）按 10^6/秒估算。

错法对照

错法	问题	正解
双重循环就是 O(n²)	内层循环可能只跑常数次	精确计算操作次数
递归就是 O(2^n)	只有无 memo 的斐波那契才是	画递归树或用主定理分析
排序后二分是 O(log n)	排序本身要 O(n log n)	总复杂度 O(n log n)
哈希表一定 O(1)	最坏 O(n)，或哈希函数差时退化	假设平均 O(1)，但考虑最坏情况
空间复杂度只看额外数组	递归栈、返回值都占空间	全面考虑所有内存分配

卡点急救

1. TLE 了：数一下循环层数，估算总操作次数。超过 10^8 就要优化算法，不是优化常数。
2. MLE 了：检查是否开了过大的数组，或递归深度太深。int 数组 10^7 约 40MB，10^8 约 400MB 必挂。
3. 不知道复杂度：代入几个 n 值（10^3, 10^4, 10^5）看运行时间增长趋势。

面试常问

• 什么是大 O 表示法？ 描述算法随输入规模增长的时间/空间增长趋势，忽略常数和低阶项，关注最高阶项。

• O(n) 和 O(n log n) 哪个好？ O(n) 好。但有时候 O(n log n) 的算法实际更快（如排序），因为常数小、缓存友好。

• 如何分析递归算法复杂度？ 三种方法：代入法（猜+归纳）、递归树（展开求和）、主定理（T(n)=aT(n/b)+f(n) 的公式解）。

自测三问

1. 一个三重循环，每层跑 n 次，总复杂度是多少？
2. 为什么二分查找是 O(log n)？
3. 在 2 秒时限下，n=10^5 时哪些复杂度能通过？哪些不能？

小结一句话

复杂度是算法的成绩单，大 O 告诉你数据量翻倍时时间翻几倍；学会分析复杂度，才能在刷题前预判生死。

延伸

• Java 官方文档：算法复杂度
• 下一课：排序算法——快排、归并、堆排的原理与实现。