百练百会 bestWit

Appearance

L8_07 算法时间与空间效率分析 ​

一、算法复杂度的一般分析方法 ​

1.1 时间复杂度定义 ​

时间复杂度描述算法执行所需的时间随输入规模增长的趋势。

1.2 空间复杂度定义 ​

空间复杂度描述算法执行所需的空间随输入规模增长的趋势。

1.3 渐近符号 ​

cpp
// O-表示法：上界
// Ω-表示法：下界  
// Θ-表示法：紧界

// 常见复杂度排序（从小到大）：
// O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

1.4 复杂度计算规则 ​

cpp
// 1. 忽略常数项
// O(2n + 3) = O(n)

// 2. 忽略低阶项
// O(n² + n) = O(n²)

// 3. 乘法规则
// O(n) × O(log n) = O(n log n)

// 4. 加法规则
// O(n) + O(n²) = O(n²)

二、排序算法的时间空间复杂度 ​

2.1 简单排序算法 ​

算法平均时间最坏时间空间复杂度稳定性
冒泡排序O(n²)O(n²)O(1)稳定
插入排序O(n²)O(n²)O(1)稳定
选择排序O(n²)O(n²)O(1)不稳定

2.2 高级排序算法 ​

算法平均时间最坏时间空间复杂度稳定性
快速排序O(n log n)O(n²)O(log n)不稳定
归并排序O(n log n)O(n log n)O(n)稳定
堆排序O(n log n)O(n log n)O(1)不稳定

2.3 线性时间排序 ​

算法时间复杂度空间复杂度适用范围
计数排序O(n + k)O(n + k)整数范围较小
基数排序O(d(n + k))O(n + k)整数、字符串
桶排序O(n)O(n)均匀分布

三、查找算法的时间空间复杂度 ​

3.1 顺序查找 ​

cpp
int sequentialSearch(vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)

3.2 二分查找 ​

cpp
int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
// 时间复杂度：O(log n)
// 空间复杂度：O(1)

3.3 哈希查找 ​

cpp
bool hashSearch(unordered_map<int, int>& map, int target) {
    return map.count(target);
}
// 平均时间复杂度：O(1)
// 最坏时间复杂度：O(n)
// 空间复杂度：O(n)

3.4 查找算法对比 ​

算法平均时间最坏时间空间复杂度有序性要求
顺序查找O(n)O(n)O(1)无
二分查找O(log n)O(log n)O(1)有序
哈希查找O(1)O(n)O(n)无
二叉搜索树O(log n)O(n)O(n)有序

四、树和图的遍历算法复杂度 ​

4.1 树遍历 ​

遍历方式时间复杂度空间复杂度
前序遍历O(n)O(h)
中序遍历O(n)O(h)
后序遍历O(n)O(h)
层序遍历O(n)O(n)

其中 h 为树的高度，对于平衡树 h = O(log n)，对于不平衡树 h = O(n)。

4.2 图遍历 ​

算法时间复杂度空间复杂度
DFSO(V + E)O(V)
BFSO(V + E)O(V)
DijkstraO((V+E)logV)O(V)
Floyd-WarshallO(V³)O(V²)

4.3 树的操作复杂度 ​

操作平均时间最坏时间
搜索O(log n)O(n)
插入O(log n)O(n)
删除O(log n)O(n)

五、搜索算法复杂度 ​

5.1 暴力搜索 ​

cpp
// 回溯算法
void backtrack(vector<int>& path, vector<bool>& used, vector<int>& nums) {
    if (path.size() == nums.size()) {
        // 找到一个解
        return;
    }
    
    for (int i = 0; i < nums.size(); i++) {
        if (!used[i]) {
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(path, used, nums);
            path.pop_back();
            used[i] = false;
        }
    }
}
// 时间复杂度：O(n!)
// 空间复杂度：O(n)

5.2 分支限界 ​

cpp
// 使用优先队列的分支限界
int branchAndBound(vector<int>& weights, vector<int>& values, int capacity) {
    priority_queue<Node> pq;
    pq.push(Node(0, 0, 0, 0));
    
    int maxValue = 0;
    while (!pq.empty()) {
        Node node = pq.top();
        pq.pop();
        
        if (node.upperBound <= maxValue) continue;
        
        // 剪枝操作
        if (node.weight + weights[node.level] <= capacity) {
            // 选择当前物品
            int newValue = node.value + values[node.level];
            maxValue = max(maxValue, newValue);
            pq.push(Node(node.level + 1, newValue, node.weight + weights[node.level], calculateBound(...)));
        }
        
        // 不选择当前物品
        pq.push(Node(node.level + 1, node.value, node.weight, calculateBound(...)));
    }
    
    return maxValue;
}
// 时间复杂度：O(b^d)，b为分支因子，d为深度
// 通过剪枝可以大幅优化

5.3 A* 算法 ​

cpp
int aStarSearch(int start, int end, const vector<vector<pair<int, int>>>& graph) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> g(n, INT_MAX); // 实际代价
    vector<int> f(n, INT_MAX); // 估计代价
    
    g[start] = 0;
    f[start] = heuristic(start, end);
    pq.push({f[start], start});
    
    while (!pq.empty()) {
        auto [cost, u] = pq.top();
        pq.pop();
        
        if (u == end) return g[u];
        
        for (auto [v, w] : graph[u]) {
            if (g[v] > g[u] + w) {
                g[v] = g[u] + w;
                f[v] = g[v] + heuristic(v, end);
                pq.push({f[v], v});
            }
        }
    }
    return -1;
}
// 时间复杂度：O(b^d)，但通常比BFS/DFS快很多

六、分治及动态规划算法复杂度 ​

6.1 分治算法 ​

cpp
// 递归式：T(n) = a*T(n/b) + f(n)

// 主定理求解：
// 1. 如果 f(n) = O(n^c) 且 c < log_b(a)，则 T(n) = O(n^log_b(a))
// 2. 如果 f(n) = Θ(n^c) 且 c = log_b(a)，则 T(n) = O(n^c log n)
// 3. 如果 f(n) = Ω(n^c) 且 c > log_b(a)，则 T(n) = Θ(f(n))

// 例子：归并排序
// T(n) = 2*T(n/2) + O(n)
// a=2, b=2, c=1, log_b(a)=1, c=log_b(a)
// T(n) = O(n log n)

6.2 动态规划 ​

cpp
// 一维DP
// 时间复杂度：O(n)
// 空间复杂度：O(n)，可优化到 O(1)

// 二维DP
// 时间复杂度：O(n*m)
// 空间复杂度：O(n*m)，可优化到 O(min(n,m))

// 状态压缩DP
// 时间复杂度：O(n^2 * 2^n)
// 空间复杂度：O(n * 2^n)

// 例子：背包问题
// 0-1背包：O(n*C)
// 完全背包：O(n*C)
// 多重背包：O(n*C)（二进制优化后）

6.3 分治与动态规划对比 ​

特性分治动态规划
子问题独立重叠
求解方式自顶向下自底向上
时间复杂度通常较低通常较高
空间复杂度通常较低通常较高

七、复杂度分析实例 ​

7.1 斐波那契数列 ​

cpp
// 递归版本
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}
// 时间复杂度：O(2^n)
// 空间复杂度：O(n)

// 迭代版本
int fibonacci(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)

// 矩阵快速幂版本
// 时间复杂度：O(log n)
// 空间复杂度：O(1)

7.2 阶乘 ​

cpp
// 递归版本
int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n-1);
}
// 时间复杂度：O(n)
// 空间复杂度：O(n)

// 迭代版本
int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)

7.3 矩阵乘法 ​

cpp
vector<vector<int>> multiply(const vector<vector<int>>& a, const vector<vector<int>>& b) {
    int n = a.size();
    vector<vector<int>> result(n, vector<int>(n, 0));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                result[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return result;
}
// 时间复杂度：O(n³)
// 空间复杂度：O(n²)

八、算法复杂度总结 ​

复杂度描述常见算法
O(1)常数时间数组访问、哈希查找
O(log n)对数时间二分查找、快速幂
O(n)线性时间顺序查找、线性扫描
O(n log n)线性对数时间快速排序、归并排序
O(n²)平方时间冒泡排序、插入排序
O(n³)立方时间矩阵乘法、Floyd-Warshall
O(2ⁿ)指数时间子集生成、暴力搜索
O(n!)阶乘时间全排列生成

百炼成钢，融会贯通

© 2026 百练百会（bestwit）GESP备考一站式平台 | 京ICP备16040576号-5