算法时间复杂度分析中任意大小数字加法是否可按O(1)计算？

两种说法都成立，只是适用的计算模型不同，不存在绝对的对错：

两种计算方式的适用场景 #

• 位运算/可变字长模型：该模型假设数字的位数n可以无限增长，不受硬件限制，此时两个n位数字的加法需要逐位执行进位运算，时间复杂度为O(n)。这种模型多用于理论计算机科学、密码学、大整数运算相关的复杂度分析场景，例如大数加法、全同态加密算法等场景的复杂度计算都需要基于该模型。
• RAM（随机存取机器）固定字长模型：这是绝大多数工程类、常规算法分析场景默认使用的模型，该模型假设所有参与运算的数字都在处理器的支持字长范围内（目前通用处理器多为64位），无论数字大小，算术运算都可以在单时钟周期内完成，因此时间复杂度统一按O(1)计算。

科研论文的选择建议 #

你可以根据自己的研究领域和分析对象选择对应规则：

• 如果你的研究属于理论计算机、密码学、大数值计算方向，或者分析的算法涉及超过处理器字长的大整数运算，推荐采用位运算模型的O(n)计算规则，需要在论文的复杂度说明部分明确标注你采用的计算模型，避免歧义。
• 如果你的研究属于常规算法优化、数据结构、工程应用类方向，默认采用RAM模型的O(1)计算规则即可，这也是目前绝大多数算法类科研论文的通用惯例，不需要额外特殊说明。

补充提示：如果你的算法分析中同时涉及固定字长常规运算和大整数运算，需要在文中单独区分两种运算的复杂度计算规则，避免评审产生误解。

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