码农常见问题之如何证明自己写的算法是对的

很多初学者不知道如何证明自己写的算法是正确的，通常只能通过提交代码看是否“AC”（Accepted，即通过所有测试用例）来判断。

核心方法（四步验证法）

以“在含10万个元素的数组中，找两数之和等于1024的二元组数量”问题为例，讲解如何验证算法正确性：

1. 数据生成：编写程序生成大量测试用例，每条用例包含一个数组长度 n 和 n 个随机数， n 可取较小值（如1000），将数据输出到文件。

2. 暴力算法跑数据：用暴力解法（双重循环遍历所有数对求和）运行这些测试用例，得到结果并记录。暴力解法虽然时间复杂度高（O(n^2)），但逻辑简单，正确性易保证，且本地运行可控制数据规模避免超时。

3. 优化算法跑数据：用优化后的算法（如先排序再二分查找，时间复杂度O(n\log n)）运行同样的测试用例，得到结果。

4. 数据比对：对比暴力算法和优化算法的结果，若所有数据一致，说明优化算法大概率正确；若有一组不一致，则算法存在错误。

特殊情况说明

该方法在99%的情况下有效，但存在1%的例外——边界情况。例如，某些算法漏洞可能仅在数组长度极大（如10万）时暴露，小数据规模（如1000）的测试用例无法检测到。

方法价值

当对复杂算法的正确性无法判断时，这种“暴力+优化算法结果比对”的方法是通用且有效的验证手段。