发现了一个 O(N^N!) 的算法

起因是刷到一张表情包：汤姆猫一脸坏笑——

突然想到一个O(N^N!)的算法

“突然想到一个 O(N^N!) 的算法。”

O(N^N!)——N 的 N! 次方。这个复杂度夸张到什么程度？N=3 时就是 729，N=4 直接冲破四百万，再往上数数都没意义了。猫都能”想到”的算法，那我能不能真的把它写出来？于是有了这个程序：不借助任何数论技巧，用最朴素的递归把这道题画出来。完整代码只有 30 行：

N^N!算法.c

#include <stdio.h>

long long total_sum = 0;

long long factorial(unsigned n)
{
    if (n == 1)
    {
        printf("+1");
        total_sum++;
        return 1;
    }
    long long sum = 0;
    for (unsigned i = 0; i < n; ++i)
    {
        printf("(");
        sum += factorial(n-1);
        printf(")");
    }
    return sum;
}

int main()
{
    int n = 3;
    long long end = 1;
    for (long long i = 1; i <= n; ++i)
    {
        end *= i;
    }

    for (long long i = 1; i <= end; ++i)
    {
        printf(" and %ld!=%ld\n", i, factorial(i));
    }
    printf("\n\n\ntotal_sum = %d",total_sum);
    getchar();
    return 0;
}

递归的另一种输出

普通递归只返回数值；这个 factorial 一边递归一边打印括号：进入一层打 (，出来打 )。于是 factorial(1) 打印 +1；factorial(2) 打印 2 份 factorial(1) 各包一对括号——(+1)(+1)；factorial(3) 再翻倍——((+1)(+1))((+1)(+1))((+1)(+1))。

主函数里 n = 3，先算出 end = 3! = 6，然后把 i 从 1 到 6 逐个打印 i! 的括号画像。真机运行：

+1 and 1!=1
(+1)(+1) and 2!=2
((+1)(+1))((+1)(+1))((+1)(+1)) and 3!=6
(((+1)(+1))((+1)(+1))((+1)(+1)))(((+1)(+1))((+1)(+1))((+1)(+1)))(((+1)(+1))((+1)(+1))((+1)(+1))) and 4!=24
((((+1)(+1))((+1)(+1))((+1)(+1)))(((+1)(+1))((+1)(+1))((+1)(+1)))(((+1)(+1))((+1)(+1))((+1)(+1)))(((+1)(+1))((+1)(+1))((+1)(+1)))) and 5!=120
...（第六行的括号海已经漫出屏幕，共 720 份 "+1"）

一行比一行膨胀——1!=1 干干净净，6!=720 的括号海里沉着 720 个 +1。递归的结构被直接画在了屏幕上：3! 是三个括号包着 2!，2! 是两个括号包着 1!——教科书里”3! = 3 × 2!”的每一层展开，都对应着屏幕上的一对括号。

结尾的 total_sum 统计的是 base case（+1）被打印的次数：打完六行，它正好等于所有阶乘结果的总和。递归深度、调用次数、数值结果，全部可视化在一场括号雨里。

表情包里的复杂度：猫居然没吹牛

现在回应猫的宣言。这个程序的输出总量是多少？main 要打印 1! 到 N! 的括号画像，第 i 行是 factorial(i) 的递归树——它的调用次数约为 e·i!，打印量约 2e·i! 个字符。总输出量：

1	Σ (i!)，i 从 1 到 N!

最后一项 N! 的括号海就占据 (N!)! 级别的字符。和表情包声称的 O(N^N!) 正面对比：

N	本程序：Θ((N!)!)	猫的说法：N^N!	谁大
3	6! = 720	3⁶ = 729	猫略大
4	24! ≈ 6.2×10²³	4²⁴ ≈ 2.8×10¹⁴	程序碾压
5	120! ≈ 6.7×10¹⁹⁸	5¹²⁰ ≈ 8.9×10⁸³	碾压且甩开一个宇宙