蛮力法

蛮力法（Brute Force）按问题定义直接枚举、尝试所有（或足够多）候选解，再用条件筛选出答案。它往往不是最快的，但通常最容易想出来、最容易写对。

本文解决什么问题

• 什么时候该用蛮力
• 如何把「枚举空间」写清楚
• 用代码建立正确基准，再谈优化

核心思想

1. 明确解空间（所有可能答案长什么样）
2. 逐个生成或遍历候选
3. 检查是否合法 / 是否更优
4. 返回满足条件的结果

当数据规模 $n$ 很小，或你需要一个正确基准（用来对照优化算法）时，蛮力非常有用。

典型场景

场景	蛮力做法	常见代价
两数之和	两重循环检查所有数对	$O(n^2)$
字符串匹配	每个起点对齐比较	$O(n\cdot m)$
全排列 / 子集	递归枚举	$O(n!)$ / $O(2^n)$
最短路径（边很少）	枚举路径	很快爆炸

例子：两数之和（是否存在）

/* 蛮力：是否存在两数之和为 target */
int two_sum_exists(const int *a, int n, int target) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] + a[j] == target) {
                return 1;
            }
        }
    }
    return 0;
}

• 时间：$\Theta(n^2)$（总是扫完所有无序数对，或提前返回时最好更好）
• 空间：$O(1)$ 额外空间

后续可用排序 + 双指针，或哈希表做到平均 $O(n)$，但蛮力版适合先验证题意与边界（负数、重复元素、空数组）。

例子：找最大子段和的朴素版

「连续子数组的最大和」——三重或两重循环的蛮力版常被用来对照 Kadane 算法：

int max_subarray_brute(const int *a, int n) {
    int best = a[0];
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += a[j];
            if (sum > best) best = sum;
        }
    }
    return best;
}

时间 $O(n^2)$。优化到 $O(n)$ 属于动态规划 / 贪心思想的经典题；没有蛮力对照时，优化版很容易在「全负数」等边界上写错。

优点与代价

	说明
优点	思路直接、实现简单、适合做正确性对照与单元测试 oracle
代价	解空间一大就爆炸，常见 $O(n^2)$、$O(n!)$、$O(2^n)$

工程习惯

先写一个小规模可跑的蛮力版，用随机小数据对比优化版输出；很多「巧妙算法」的 bug 都是这样抓出来的。

和本教程其他思想的关系

• 优化常来自：换数据结构（哈希）、换范式（分治 / DP）、或剪枝（减少无用枚举）
• 模式匹配、部分图算法入门，都建议先会蛮力再学加速版

常见误区

• 一上来就追求最优解法，题意都没对齐
• 枚举时重复或遗漏（下标 i、j 边界）
• $n$ 已经到 $10^5$ 仍用 $O(n^2)$ 蛮力却不自知

小结

蛮力法优先保证正确。$n$ 可控时完全可用；$n$ 变大时，再考虑分治、贪心、动态规划或更好的数据结构。

下一篇：分治法。