从O(n²)到O(n)：阶乘求和算法的效率跃迁与竞赛实战解析
1. 阶乘求和问题：从暴力到优雅的算法进化
第一次接触阶乘求和问题时，我像大多数初学者一样直接套用了双重循环的暴力解法。记得当时在OpenJudge平台上提交代码后，虽然通过了测试用例，但当输入n=10000时程序直接卡死了。这个惨痛教训让我意识到：算法效率不是纸上谈兵，而是直接影响程序生死的关键因素。
阶乘求和问题看似简单——计算S=1!+2!+...+n!。但不同解法的时间复杂度可能天差地别。让我们先看最直观的解法：循环嵌套。外层循环遍历1到n，内层循环计算每个数的阶乘。这种解法时间复杂度是O(n²)，当n较大时就像让自行车去跑F1赛道，根本不在一个量级。
# 典型O(n²)解法 def factorial_sum_naive(n): total = 0 for i in range(1, n+1): fact = 1 for j in range(1, i+1): # 每次重新计算阶乘 fact *= j total += fact return total在信息学奥赛(NOI)这类对时间复杂度极其敏感的场合，这样的代码即便逻辑正确，也会因为效率问题被判"时间超限"。这就像考试时虽然最终答案正确，但解题步骤过于繁琐导致没能在规定时间内完成——依然拿不到分数。
2. 时间复杂度：算法竞赛的隐形裁判
在算法竞赛中，时间复杂度就是隐形的评分标准。以OpenJudge平台为例，通常1秒内能处理10^6~10^7次基本操作。对于n=10^5的情况：
- O(n²)算法需要10^10次操作，远超时间限制
- O(n)算法仅需10^5次操作，轻松通过
理解时间复杂度的最好方式是用现实生活类比。假设你要整理图书馆藏书：
- O(n²)相当于每次找书都从头开始遍历整个书架
- O(n)则是建立目录索引，直接定位书籍位置
回到阶乘求和问题，我们发现计算i!时其实已经算过(i-1)!。就像整理图书时，每次都要把之前整理过的书重新翻一遍，这显然是在做无用功。优秀的算法应该避免重复计算，这正是优化效率的关键突破口。
3. 算法优化实战：从O(n²)到O(n)的三级跳
3.1 函数封装法的局限
很多教材会建议将阶乘计算封装成函数，这样代码更清晰：
def factorial(k): res = 1 for i in range(1, k+1): res *= i return res def factorial_sum_func(n): return sum(factorial(i) for i in range(1, n+1))但实测发现，这种写法时间复杂度依然是O(n²)。因为每次调用factorial(i)都要从1开始重新计算，相当于把嵌套循环换成了函数调用，本质没有改变算法效率。这提醒我们：代码美观不等于高效，要真正理解算法本质。
3.2 迭代优化：发现数学规律
仔细观察阶乘的数学性质： i! = i × (i-1)! 这意味着我们可以在计算过程中保留中间结果：
def factorial_sum_optimized(n): total = 0 current_fact = 1 # 保存当前的阶乘值 for i in range(1, n+1): current_fact *= i # 利用前一个阶乘值 total += current_fact return total这个版本的时间复杂度直接降为O(n)，空间复杂度仍是O(1)。在NOI竞赛中，这种优化往往就是满分与零分的分水岭。我曾在一次模拟赛中，用这个技巧将运行时间从2秒降到了0.01秒。
3.3 递归解法的两面性
递归思路也很直观： sum(n) = sum(n-1) + n! 但直接实现会导致重复计算：
def factorial_rec(n): return 1 if n == 1 else n * factorial_rec(n-1) def factorial_sum_rec(n): return 0 if n == 0 else factorial_sum_rec(n-1) + factorial_rec(n)这种写法虽然简洁，但时间复杂度高达O(n²)，且容易导致栈溢出。可以加入记忆化优化，但迭代法仍是更优选择。在竞赛中，过度追求代码简洁而牺牲效率是本末倒置。
4. 竞赛实战技巧：避开性能陷阱
在实际比赛中，我总结出几个关键经验：
- 避免重复计算：像阶乘、斐波那契数列这类有递推关系的问题，一定要利用已有结果
- 警惕隐藏的平方复杂度：看似简单的代码可能暗藏效率陷阱
- 数学规律优先：很多问题都有类似阶乘这样的数学性质可以利用
- 测试极端数据：n=1, n=0, n=1e5等边界情况要特别测试
以OpenJudge 1.5 34题为例，最优解法的核心代码仅需6行：
#include <iostream> using namespace std; int main() { int n, sum = 0, fact = 1; cin >> n; for(int i=1; i<=n; fact*=i, sum+=fact, i++); cout << sum; }这种写法把阶乘计算和求和合并到一个循环中，是典型的竞赛编码风格——在保证可读性的前提下追求极致效率。记住：算法竞赛不是代码美学比赛，而是解决问题的效率竞赛。