嵌套Big-O场景下阶乘结果存列表程序的总时间复杂度计算

你的推导存在的错误 #

• 核心前提错误：你认为ans ∈ O(N)，实际ans是N的阶乘N!，阶乘的增长速度远快于线性、甚至指数级，不存在常数C使得N! ≤ C*N对所有足够大的N成立。
• 总复杂度推导错误：你直接忽略了第一步O(N)循环的开销，同时错误推导了d的量级：d=log10(N!)不是O(log N)，而是更高的量级。

正确的时间复杂度推导（基于入门算法分析的常见假设：所有算术运算为O(1)） #

首先通过斯特林公式可以计算出阶乘的位数d的量级：

斯特林公式：$\ln(N!) \approx N\ln N - N$
转换为以10为底的对数：$d = \lfloor \log_{10}(N!) \rfloor + 1 \approx \frac{N\ln N}{\ln 10} = O(N \log N)$

三部分操作的时间加总：

1. 第一步阶乘计算循环：共执行N-1次，每次都是O(1)运算，总开销O(N)
2. 第二步取各位数字循环：执行d次，总开销O(d) = O(N log N)
3. 第三步列表反转：执行d/2次，总开销O(d) = O(N log N)

高阶项为O(N log N)，因此总时间复杂度为O(N log N)，你提到的「d的量级大于N」是对的，所以总复杂度确实由位数相关的操作主导。 #

关于嵌套Big O写法的说明 #

不存在O(log10(O(N)))这种写法，Big O表示的是复杂度上界，必须化简为关于输入规模N的表达式，不能嵌套Big O符号。这里log10(N!)可以直接通过斯特林公式化简为O(N log N)。 #

补充：实际运行的时间复杂度（考虑Python任意精度整数的乘法开销） #

上面的推导是入门级的简化假设，实际Python的int是任意精度的，当N很大时N!的位数d会非常大，两个d位整数相乘的时间复杂度至少是O(d)（朴素乘法），因此第一步阶乘计算的实际时间复杂度远高于O(N)，整体复杂度会更高。这类大数阶乘场景一般会直接用数组存储阶乘的各位数字计算，避免大数乘法的额外开销。 #

代码小问题提示 #

你注释里写的ans_digits = str(ans).split()是错误的，split()默认按空白符分割，不会把字符串拆成单个字符，正确写法是ans_digits = [int(c) for c in str(ans)]。 #

内容的提问来源于stack exchange，提问作者karahbit