时间与空间复杂度详解：算法效率的度量衡

一、为什么需要复杂度分析？

想象你正在开发一个手机通讯录应用，需要实现联系人搜索功能。你有两种算法可以选择：

// 算法A：线性搜索
public Contact linearSearch(List<Contact> contacts, String name) {
    for (Contact c : contacts) {
        if (c.getName().equals(name)) {
            return c;
        }
    }
    return null;
}

// 算法B：二分搜索（需要排序）
public Contact binarySearch(List<Contact> contacts, String name) {
    // 先排序（假设已实现）
    Collections.sort(contacts, Comparator.comparing(Contact::getName));
    
    int left = 0, right = contacts.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cmp = contacts.get(mid).getName().compareTo(name);
        if (cmp == 0) return contacts.get(mid);
        if (cmp < 0) left = mid + 1;
        else right = mid - 1;
    }
    return null;
}

问题：当联系人数量很少时（如100人），两种算法都很快。但当联系人增长到10万人时：

• 算法A可能需要10秒
• 算法B可能只需0.01秒

复杂度分析就是帮助我们预测算法在数据量增长时的表现，避免上线后才发现性能问题

二、时间复杂度：算法执行时间的增长趋势

1. 基本概念

时间复杂度不是计算具体时间，而是描述算法执行时间随数据规模增长的变化趋势

2. 大O表示法

我们使用大O表示法描述时间复杂度，常见的有：

• O(1)：常数时间
• O(log n)：对数时间
• O(n)：线性时间
• O(n log n)：线性对数时间
• O(n²)：平方时间
• O(2ⁿ)：指数时间

// 示例1：数组随机访问
int getElement(int[] arr, int index) {
    return arr[index]; // 只需一次操作
}

// 示例2：判断奇偶
boolean isEven(int num) {
    return num % 2 == 0; // 一次计算
}

3. 常见时间复杂度详解

(1) O(1)：常数时间

特点：执行时间不随数据规模变化

// 示例1：数组随机访问
int getElement(int[] arr, int index) {
    return arr[index]; // 只需一次操作
}

// 示例2：判断奇偶
boolean isEven(int num) {
    return num % 2 == 0; // 一次计算
}

(2) O(log n)：对数时间

特点：数据量翻倍时，操作数只增加1

// 示例：二分查找
int binarySearch(int[] arr, int target) {
    int left = 0;
    int 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;
}

操作次数：每次循环数据量减半，N个元素最多需要log₂N次操作

(3) O(n)：线性时间

特点：执行时间与数据规模成正比

// 示例：遍历数组
int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

// 示例：遍历数组
int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

操作次数：N个元素需要N次比较

(4) O(n log n)：线性对数时间

特点：常见于高效排序算法

// 示例：归并排序
void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);     // T(n/2)
        mergeSort(arr, mid + 1, right); // T(n/2)
        merge(arr, left, mid, right);  // O(n)
    }
}
// 时间复杂度：T(n) = 2T(n/2) + O(n) = O(n log n)

(5) O(n²)：平方时间

特点：数据量翻倍时，时间增加4倍

// 示例1：冒泡排序
void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}
// 操作次数：(n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ O(n²)

// 示例2：矩阵乘法
int[][] multiply(int[][] A, int[][] B) {
    int n = A.length;
    int[][] C = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}
// 三重循环 → O(n³)

(6) O(2ⁿ)：指数时间

特点：数据量增加1，时间翻倍

// 示例：斐波那契递归
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
// 时间复杂度：T(n) = T(n-1) + T(n-2) + O(1) ≈ O(2ⁿ)

4. 时间复杂度计算规则

1. 忽略常数：O(2n) → O(n)
2. 取最高阶：O(n³ + n² + n) → O(n³)
3. 忽略系数：O(3n²) → O(n²)
4. 对数底数忽略：O(log₂n) → O(log n)

三、空间复杂度：算法占用内存的增长趋势

1. 基本概念

空间复杂度描述算法运行过程中临时占用存储空间随数据规模增长的变化趋势

2. 常见空间复杂度

(1) O(1)：常数空间

特点：占用固定内存，不随数据规模变化

// 示例：数组元素求和
int sum(int[] arr) {
    int total = 0;           // 1个变量
    for (int num : arr) {
        total += num;        // 无新空间
    }
    return total;
}

(2) O(n)：线性空间

特点：占用空间与数据规模成正比

// 示例1：数组复制
int[] copyArray(int[] arr) {
    int[] newArr = new int[arr.length]; // 长度为n的数组
    for (int i = 0; i < arr.length; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}

// 示例2：递归深度
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1); // 递归深度n → O(n)栈空间
}

(3) O(n²)：平方空间

特点：常见于二维数据结构

// 示例：矩阵存储
int[][] generateMatrix(int n) {
    int[][] matrix = new int[n][n]; // n×n的矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = i * j;
        }
    }
    return matrix;
}
// 占用空间：n² → O(n²)

四、复杂度分析实战

案例1：两数之和

// 方法1：暴力枚举
int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[0];
}
// 时间复杂度：O(n²)  空间复杂度：O(1)

// 方法2：哈希表
int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}
// 时间复杂度：O(n)  空间复杂度：O(n)

案例2：归并排序

void mergeSort(int[] arr) {
    if (arr.length <= 1) return;
    int mid = arr.length / 2;
    int[] left = Arrays.copyOfRange(arr, 0, mid); // O(n)
    int[] right = Arrays.copyOfRange(arr, mid, arr.length); // O(n)
    mergeSort(left);
    mergeSort(right);
    merge(arr, left, right);
}
// 时间复杂度：O(n log n)
// 空间复杂度：O(n)（递归栈O(log n) + 临时数组O(n)）

五、复杂度优化策略

1. 时间优化技巧

• 空间换时间：使用哈希表减少查找时间
• 分治策略：归并排序、快速排序
• 动态规划：避免重复计算
• 双指针：减少不必要的遍历

2. 空间优化技巧

• 原地操作：冒泡排序、堆排序
• 迭代替代递归：减少栈空间
• 数据压缩：位图代替布尔数组

六、常见算法复杂度总结

七、实际开发中的复杂度分析

1. 数据库查询优化

-- O(n) 全表扫描
SELECT * FROM users WHERE name LIKE '%john%';

-- O(log n) 索引查询
SELECT * FROM users WHERE id = 10086;

2. 系统设计考虑

• 用户量从1万到1000万时：
  • 时间复杂度O(n²)的算法会慢10000倍
  • 空间复杂度O(n)需要1000倍内存

3. 性能测试与复杂度验证

// 测试不同规模数据下的执行时间
void testPerformance() {
    for (int n = 1000; n <= 1000000; n *= 10) {
        int[] arr = generateArray(n); // 生成n个元素的数组
        long start = System.nanoTime();
        algorithm(arr); // 运行算法
        long duration = System.nanoTime() - start;
        System.out.printf("n=%d, time=%.2f ms%n", n, duration / 1e6);
    }
}

八、复杂度分析的局限性

1. 忽略常数因子：O(100n)和O(n)视为相同
2. 不考虑硬件差异：SSD vs HDD
3. 不反映实际时间：只描述增长趋势
4. 不适用于小数据量：小数据时简单算法可能更快