打印整数的时间复杂度：O(1)还是O(log n)？

针对你给出的这段Python代码：

n = 123456789
print(n)

直接给结论：print(n)的时间复杂度是O(log n)，不是O(1)，具体原因拆解如下：

• 打印整数的核心过程不是单一的"常数时间操作"：Python需要先将整数n转换为对应的十进制字符串，再将这个字符串的每一个字符输出到控制台。这两个步骤都和n的位数直接相关。
• n的位数与log n成正比：十进制下，n的位数m满足m ≈ log₁₀(n) + 1。大O复杂度分析中，对数的底数不影响最终结果（不同底数的对数仅相差一个常数系数），因此m的复杂度等价于O(log n)。
• 每一位的处理是O(1)，但总共有O(log n)位：不管是拆解整数的每一位转成字符，还是输出每个字符，单步都是O(1)操作，但总共有O(log n)个这样的步骤，所以整体时间复杂度为O(log n)。

你最初误以为是O(1)的常见误区：

• 如果n的取值被限定在固定范围（比如32位整数，最多10位），此时位数是常数，确实可以近似按O(1)处理；
• 忽略了打印操作背后的字符转换与输出过程，误以为是一个原子性的常数时间动作。

但在Python这种支持任意大整数的语言中，当n可以无限增大时，必须按照O(log n)来分析该操作的时间复杂度。

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