关于阿拉伯数字转罗马数字函数的Big O时间复杂度分析咨询

核心结论 #

这个函数的时间复杂度是O(1)，而非O(n)。

具体分析 #

1. 时间复杂度的本质逻辑
   时间复杂度描述的是算法执行步骤随输入规模无限增长时的变化趋势。如果输入存在固定、有限的上限，那么算法的执行步骤数有明确的最大值，属于常数时间范畴，即O(1)。

在你的代码中，已经明确标注了输入范围：// 1 <= num <= 3999，num的取值被严格限制在一个有限区间内，不存在“输入规模无限扩大”的场景。

2. 针对两种观点的拆解

• 支持O(1)的合理性：
  外层for循环的迭代次数固定为12次（对应romanNumerals数组的长度）；内层while循环的总次数在最坏情况下（比如num=3999）也是固定的常数——即使极端情况每次只减去最小的1，总次数最多也只有3999次，但这个数值是固定的上限，不会随输入增长而变化。无论输入num在1-3999之间取何值，函数的执行步骤数都不会超过这个固定上限，因此属于常数时间。

• O(n)观点的适用场景：
  这种观点的前提是输入num可以无限增大，此时while循环的迭代次数会和num值呈线性正相关，时间复杂度才会是O(n)。但你的代码明确限定了num的范围，这个前提不成立，所以O(n)的结论不适用。

3. 结合代码的实际执行逻辑
   代码采用贪心算法，每次优先减去最大的罗马数字对应值，因此实际的while循环总次数远小于3999：比如num=3999时，只需要7次while循环迭代（3次M、1次CM、1次XC、1次V、1次IV）就能完成转换，完全是常数级的步骤数。

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