别再写O(n²)的阶乘求和了！一个变量搞定，效率提升100倍

从O(n²)到O(n)：阶乘求和算法的思维跃迁

在编程竞赛和算法学习中，阶乘求和是一个经典问题。表面上看，它似乎只需要简单的循环和乘法运算就能解决。但当你深入探究，会发现这个看似基础的问题背后隐藏着算法优化的精髓——如何用更简洁的代码实现更高的效率。

1. 问题定义与直观解法

阶乘求和问题通常表述为：给定一个正整数n，计算1! + 2! + 3! + ... + n!的值。对于初学者来说，最直观的解法是使用双重循环：

#include <iostream> using namespace std; int main() { int n; cin >> n; int sum = 0; for(int i = 1; i <= n; ++i) { int factorial = 1; for(int j = 1; j <= i; ++j) { factorial *= j; } sum += factorial; } cout << sum << endl; return 0; }

这种方法虽然正确，但存在明显的效率问题。外层循环执行n次，内层循环在最坏情况下也执行n次，导致时间复杂度达到O(n²)。当n较大时（比如n=10000），这种解法会变得非常缓慢。

2. 算法优化的关键洞察

仔细观察阶乘序列，我们会发现一个重要的数学关系：

• 1! = 1
• 2! = 2 × 1! = 2 × 1
• 3! = 3 × 2! = 3 × 2 × 1
• ...
• n! = n × (n-1)!

这个递推关系意味着，我们不需要每次都从头开始计算阶乘。当前项的阶乘值可以通过前一项的阶乘值乘以当前项数得到。这种性质正是优化算法的突破口。

3. 单变量迭代优化法

基于上述观察，我们可以设计一个仅使用单层循环的优化算法：

#include <iostream> using namespace std; int main() { int n; cin >> n; int sum = 0, current_factorial = 1; for(int i = 1; i <= n; ++i) { current_factorial *= i; // 计算i! sum += current_factorial; // 将i!加入总和 } cout << sum << endl; return 0; }

这个版本的关键在于：

1. 使用current_factorial变量保存当前的阶乘值
2. 每次迭代时，用current_factorial *= i更新阶乘值
3. 将更新后的阶乘值直接加入总和

提示：这种方法的时间复杂度是O(n)，比原始解法提升了n倍的效率。对于n=10000的情况，优化后的算法几乎可以瞬间完成计算。

4. 性能对比与实测数据

为了直观展示两种方法的效率差异，我们进行了一组基准测试：

从测试数据可以看出：

• 当n较小时，两种方法差异不大
• 随着n增大，优化算法的优势呈线性增长
• 在n=10000时，优化后的算法比原始方法快500多倍

5. 算法思维进阶：从具体到抽象

这个优化案例展示了算法设计中几个重要的思维模式：

1. 避免重复计算：识别并利用子问题的重叠性
2. 空间换时间：使用额外变量保存中间结果
3. 数学洞察：发现问题的递推性质
4. 渐进分析：评估算法的时间复杂度

在实际编程竞赛中，这种思维模式可以应用于许多类似问题：

• 斐波那契数列计算
• 动态规划问题
• 累积统计计算
• 滑动窗口问题

6. 常见误区与注意事项

虽然单变量迭代法简洁高效，但在实现时仍需注意几个细节：

1. 变量初始化：确保current_factorial初始值为1
2. 整数溢出：阶乘增长极快，n>12时32位int会溢出
3. 循环边界：确保循环从1开始，包含n
4. 输入验证：处理n≤0的特殊情况

对于大数情况，可以考虑以下改进：

#include <iostream> using namespace std; int main() { int n; cin >> n; long long sum = 0, current_factorial = 1; for(int i = 1; i <= n; ++i) { current_factorial *= i; sum += current_factorial; // 可以添加溢出检测 if(current_factorial < 0) { cout << "溢出警告！" << endl; break; } } cout << sum << endl; return 0; }

7. 扩展应用：算法思维的迁移

掌握这种优化思维后，可以解决许多类似问题。例如，计算以下序列的和：

1. 1 + 1/1! + 1/2! + 1/3! + ... + 1/n!（自然对数的泰勒展开）
2. x + x²/2! + x³/3! + ... + xⁿ/n!（指数函数的泰勒展开）
3. 1 - 1/1! + 1/2! - 1/3! + ... ±1/n!（余弦函数的泰勒展开）

以第一个问题为例，优化后的解法如下：

#include <iostream> #include <iomanip> using namespace std; int main() { int n; cin >> n; double sum = 1.0; // 第一项1 double factorial = 1.0; for(int i = 1; i <= n; ++i) { factorial *= i; // 计算i! sum += 1.0 / factorial; // 添加当前项 } cout << fixed << setprecision(15) << sum << endl; return 0; }

这个例子再次展示了如何利用前一次迭代的结果来简化当前计算，避免重复工作。