常见算法优化思路

概述

在ACM竞赛中，算法优化不仅是为了通过时间和空间限制，更是体现算法功底的重要方面。本文将介绍几种常见的算法优化思路，帮助你在竞赛中更高效地解决问题。

时间复杂度优化

预处理与记忆化

核心思想: 减少重复计算，空间换时间。

// 示例: 预处理前缀和优化区间求和
int a[MAXN], prefix[MAXN];

// 预处理 O(n)
prefix[0] = 0;
for (int i = 1; i <= n; i++) {
    prefix[i] = prefix[i-1] + a[i];
}

// 查询区间和 O(1)
int querySum(int l, int r) {
    return prefix[r] - prefix[l-1];
}

应用场景:

• 区间查询问题（前缀和、差分）
• 动态规划记忆化搜索
• 数学问题的预处理（如素数筛法）

数据结构优化

核心思想: 选择更高效的数据结构来降低操作复杂度。

// 示例: 使用平衡树代替数组+排序
set<int> s;  // 有序集合，插入和查询都是O(log n)
s.insert(x);  // 插入 O(log n)
s.erase(x);  // 删除 O(log n)

// 找到第一个大于等于x的元素
auto it = s.lower_bound(x);  // O(log n)

常见优化对比:

1. 链表替代频繁插入/删除操作的数组 - O(n) → O(1)
2. 哈希表替代查找操作 - O(n) → O(1)均摊
3. 堆替代查找最值 - O(n) → O(log n)
4. 平衡树替代有序数组 - 插入O(n) → O(log n)
5. 字典树替代字符串前缀匹配 - O(n*m) → O(m)

算法策略优化

核心思想: 换用效率更高的算法。

常见优化:

1. 分治法: 将问题分解为子问题，递归解决
2. 贪心法: 每步选择局部最优解
3. 动态规划: 消除重叠子问题的递归
4. 二分优化: 在单调函数上应用二分搜索

// 示例: 二分优化查找问题
// 找到数组中第一个大于等于x的位置
int findFirstGreaterEqual(vector<int>& nums, int x) {
    int left = 0, right = nums.size() - 1;
    int result = nums.size();  // 默认没找到

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= x) {  // 满足条件
            result = mid;  // 记录答案
            right = mid - 1;  // 继续寻找更优解
        } else {
            left = mid + 1;
        }
    }

    return result;
}

剪枝技巧

核心思想: 减少搜索空间，提前排除不可能的解。

// 示例: 回溯法中的剪枝
void dfs(int depth, int sum, int target) {
    // 条件剪枝：和已经超出目标，没必要继续
    if (sum > target) return;  

    // 最优性剪枝：当前结果已不可能优于已知最优解
    if (sum + remainingMax < bestSolution) return;

    // 边界剪枝：达到约束条件，得到一个解
    if (depth == n) {
        if (sum == target) updateAnswer();
        return;
    }

    // 搜索过程
    for (int choice : choices) {
        // 可行性剪枝：判断当前选择是否合法
        if (!isValid(choice)) continue;

        dfs(depth + 1, sum + choice, target);
    }
}

常见剪枝策略:

1. 可行性剪枝: 排除不满足约束条件的分支
2. 最优性剪枝: 排除不可能优于当前最优解的分支
3. 对称性剪枝: 排除等价的搜索分支
4. 顺序剪枝: 固定搜索顺序，避免重复状态

空间复杂度优化

原地算法

核心思想: 减少辅助空间，直接在输入数组上操作。

// 示例: 原地反转数组
void reverseArray(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        swap(nums[left++], nums[right--]);
    }
}

滚动数组

核心思想: 当DP状态只依赖于前几个状态时，可以用几个变量代替整个数组。

// 示例: 斐波那契数列计算优化
// 原始DP: O(n)空间
int fib(int n) {
    if (n <= 1) return n;
    vector<int> dp(n + 1);
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// 滚动数组优化: O(1)空间
int fibOptimized(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1, curr;
    for (int i = 2; i <= n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return curr;
}

位运算技巧

核心思想: 使用位运算压缩状态表示，减少内存使用。

// 示例: 使用位运算表示集合
int set = 0;
// 添加元素i
set |= (1 << i);
// 删除元素i
set &= ~(1 << i);
// 判断元素i是否在集合中
bool exists = (set & (1 << i)) != 0;
// 遍历集合
for (int i = 0; i < 32; i++) {
    if (set & (1 << i)) {
        // 处理元素i
    }
}

适用场景:

1. 状态压缩DP
2. 集合表示与操作
3. 状态枚举

常数优化技巧

虽然不改变渐进复杂度，但在实际竞赛中常数优化可能是AC与TLE的区别。

编译优化

// 使用 #pragma GCC optimize 提高执行效率
#pragma GCC optimize("Ofast","inline","-ffast-math")

输入输出优化

// 关闭C和C++输入输出同步，提升cin/cout速度
ios::sync_with_stdio(false);
cin.tie(nullptr);

// 或使用快读快写（在输入输出数据量大的情况下）
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

避免函数调用开销

// 使用宏或内联函数减少函数调用开销
#define max(a, b) ((a) > (b) ? (a) : (b))

// 或使用inline
inline int max(int a, int b) {
    return a > b ? a : b;
}

避免不必要的计算

// 示例: 循环中的常量提取
// 优化前
for (int i = 0; i < n; i++) {
    result += a[i] * (n * log(n) + complex_function());
}

// 优化后
double const_part = n * log(n) + complex_function();
for (int i = 0; i < n; i++) {
    result += a[i] * const_part;
}

内存访问优化

// 按行优先顺序访问二维数组（利用缓存局部性）
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        // 处理a[i][j]
    }
}

混合优化案例分析

优化树状数组区间查询

问题: 使用树状数组实现区间查询和修改

优化前: 每次区间查询需要两次调用求前缀和，每次O(log n)

// 优化前: 标准树状数组
void update(int i, int delta) {
    while (i <= n) {
        bit[i] += delta;
        i += (i & -i);
    }
}

int query(int i) {
    int sum = 0;
    while (i > 0) {
        sum += bit[i];
        i -= (i & -i);
    }
    return sum;
}

int rangeQuery(int l, int r) {
    return query(r) - query(l - 1);
}

优化后: 使用差分思想结合树状数组实现O(log n)的区间修改和单点查询

// 优化后: 差分树状数组
void rangeUpdate(int l, int r, int delta) {
    update(l, delta);
    update(r + 1, -delta);
}

int pointQuery(int i) {
    return query(i);
}

优化最短路算法

问题: 计算从一点到其他所有点的最短路径

优化前: 标准Dijkstra算法使用优先队列，O((V+E)log V)

优化后: 对于稠密图，使用邻接矩阵+堆优化，O(V²)更优

// 针对不同图密度的优化版本
void dijkstra(int src) {
    // 图较稀疏时使用优先队列+邻接表
    if (E < V * log(V)) {
        priority_queue<pair<int,int>> pq;
        // 标准Dijkstra实现
    } 
    // 图较稠密时使用数组+邻接矩阵
    else {
        bool visited[MAXV] = {0};
        // O(V²)的Dijkstra实现
    }
}

实战优化案例

【案例1】最大子数组和优化

问题: 寻找一个数组中和最大的连续子数组

暴力解法: O(n³)，枚举所有子数组

int maxSubArray(vector<int>& nums) {
    int n = nums.size(), maxSum = INT_MIN;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int sum = 0;
            for (int k = i; k <= j; k++) {
                sum += nums[k];
            }
            maxSum = max(maxSum, sum);
        }
    }
    return maxSum;
}

优化1: O(n²)，枚举起点和终点，使用前缀和

int maxSubArray(vector<int>& nums) {
    int n = nums.size(), maxSum = INT_MIN;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            maxSum = max(maxSum, sum);
        }
    }
    return maxSum;
}

优化2: O(n)，动态规划，Kadane算法

int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0], currentSum = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        // 关键决策: 是加入当前元素还是重新开始
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }
    return maxSum;
}

【案例2】素数筛法优化

问题: 计算1到n的所有素数

埃氏筛: O(n log log n)

vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }
}

线性筛（欧拉筛）: O(n)

vector<bool> isPrime(n + 1, true);
vector<int> primes;
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push_back(i);
    // 关键优化: 每个合数只被其最小质因子筛掉一次
    for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
        isPrime[i * primes[j]] = false;
        if (i % primes[j] == 0) break;
    }
}

总结与建议

1. 分析问题瓶颈：首先识别算法中的耗时部分，有针对性地优化。

2. 优化策略选择：

   • 时间复杂度瓶颈：考虑更高效的算法或数据结构
   • 空间复杂度瓶颈：考虑原地算法或压缩存储
   • 常数优化：在不影响逻辑的前提下减少操作次数

3. 测试验证：优化后务必验证结果正确性，避免过度优化引入错误。

4. 权衡取舍：

   • 时间与空间的权衡
   • 代码简洁性与执行效率的权衡
   • 预处理成本与查询效率的权衡

5. 实际应用提示：

   • 在确定算法正确后再考虑优化
   • 根据题目数据范围判断需要优化的程度
   • 保持良好的代码组织，避免过度优化导致难以维护