关于两个函数基于输入规模的时间复杂度疑问及答案验证

先明确核心定义：输入规模指的是整数n的二进制位数，设这个规模为k，那么k约等于log₂n（二进制位数实际是⌊log₂n⌋+1，复杂度分析中可忽略这个+1的常数项），也就是 ( n = 2^k )。

问题1分析 #

• 问题描述：给定数值n，函数迭代n次，基于输入规模的复杂度是多少？
• 你的答案存在变量指代混乱，但核心结论方向正确，修正后表述：
  正确复杂度为 ( O(2^k) )（k为输入规模）。推导逻辑：输入规模k对应数值n=2ᵏ，迭代n次等价于迭代2ᵏ次，因此时间复杂度是输入规模k的指数函数 ( O(2^k) )。你之前把输入规模和数值n用了同一个变量n，导致表述混淆，调整变量指代后结论成立。

问题2分析 #

• 问题描述：给定数值n，函数迭代n²次，基于输入规模的复杂度是多少？
• 你的答案错误，正确推导如下：
  输入规模k对应n=2ᵏ，那么n²=(2ᵏ)²=2^{(2k)，迭代n²次就是迭代2}(2k)次，因此时间复杂度为 ( O(2^{2k}) )（也可等价写成 ( O(4^k) )，k为输入规模）。你错误地将输入规模k当成了数值n，才得出 ( O(2^{2n}) ) 的错误结论。

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