龟速阶乘算法

bluewindde · 2024-11-14 20:47:00 · 算法·理论

摘要

本论文介绍一种在 \Theta \left( \sum\limits_{i = 1}^{\lceil \log n \rceil} T \left( \frac n i \right) + \log n \right) 时间内求 n! 的方法，T(n) 取决于具体实现。

引入

引理 1（组合数公式^{[1]}） 对于满足 0 \leqslant m \leqslant n 的整数 n, m，有

证明 根据组合意义，证毕。

这启示我们将较大的数的阶乘与较小的数的阶乘建立关系，以优化计算阶乘的时间。

算法

不妨 n 是偶数，n 是奇数的情况可以通过计算 (n - 1) ! \cdot n 计算。

定理 1（龟速阶乘算法） 把 m = \frac n 2 代入引理 1，即 \binom n {\frac n 2} = \frac {n!} {(\frac n 2 !)^2}，移项得到

复杂度分析

为了分析复杂度，引入等比数列求和公式。

定理 2（等比数列求和公式^{[2]}） 对公差 q \ne 1 的等比数列，设首项为 a_1，其前 n 项和为

证明 构造长为 n 的数列 b 满足 b_i = a_i q，数列 b 的前 n 项和 T_n = q S_n。令数列 c 满足 c_i = b_i - a_i，数列 c 的前 n 项和 W_n = T_n - S_n = (q - 1) S_n。因为对于 1 \leqslant i < n 有 b_i = a_i q = a_{i + 1}，所以 W_n = (a_2 + a_3 + a_4 + \cdots + a_n + b_n) - (a_1 + a_2 + a_3 + a_4 + \cdots + a_n) = b_n - a_1 = a_n q - a_1，所以 S_n = \frac {W_n} {q - 1} = \frac {a_n q - a_1} {q - 1} = \frac {a_1 q^{n - 1} q - a_1} {q - 1} = a_1 \frac {q^n - 1} {q - 1} = a_1 \frac {1 - q^n} {1 - q}。证毕。

定理 3（龟速阶乘算法的时间复杂度） 设计算 \binom {2n} n 的时间为 T(n)。发现问题每次被分解成规模为 \lfloor \frac n 2 \rfloor 的子问题，因此至多递归 \log n 层可以求得结果。根据等比数列求和公式，龟速阶乘算法的时间复杂度为

实现

实现 1 若使用线性算法计算 \binom {2n} n，即 T(n) = \Theta(n)，则龟速阶乘算法时间复杂度为

实现 2 若使用快速阶乘算法算法实现龟速阶乘算法，即 T(n) = O(\sqrt n \log n)，则龟速阶乘算法时间复杂度为

应用

本算法可以用于一切需要计算阶乘的地方，适用性极强。

前景

目前，本算法时间复杂度瓶颈在计算 \binom {2n} n。随着计算组合数方面研究的深入，本算法将有望变得更为厉害。

总结

龟速阶乘算法是一种优秀的计算阶乘的方式，它充分利用分治思想，并因此具有极高的可拓展性。

致谢

感谢 modfisher^a，Rainchr^b，_zdc^c 对本论文重要结论作出的贡献。