算法复杂度分析：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
    }
}