f(n) = n 属于 O(n) 时间复杂度还是 O(1)？循环赋值复杂度疑问

时间复杂度疑问解答 #

1. 列表推导式的复杂度问题 #

你对单步操作的复杂度理解是对的：构造(n,n)元组、赋值这类操作确实是*O(1)*的常数时间操作，单次执行的耗时和n的取值无关。
但你混淆了「单步操作的复杂度」和「整个算法的整体复杂度」：

• 你给出的列表推导式[(n, n) for n in range(1,11)]要循环执行10次单步的O(1)操作，如果把range的上限换成变量N，就要执行N次单步操作
• 总耗时是「单次操作耗时 × 执行次数」，忽略常数系数后整体时间复杂度就是O(N)，O(N)描述的本来就是整个算法运行时间随输入规模增长的整体趋势，不是单步操作的耗时。

2. 验证代码的相关说明 #

你写的这段代码验证的不是两个算法的时间复杂度差异，而是两个数学函数的增长率差异：
你的代码里f = (i / 2) + 10和g = i都是O(1)的单步运算，你得到的「i=21时g超过f」的结果，刚好对应了复杂度分析里忽略常数项、系数的合理性：
当输入规模足够大时，同阶函数的系数、低阶常数项的影响会被抹平，即使f有常数项加成、系数只有0.5，当输入规模足够大时，一阶系数为1的g总会超过f，这就是我们做复杂度分析时会忽略系数、常数项的核心原因——我们关注的是输入规模趋近于无穷大时的增长趋势，而非小输入场景下的实际运行耗时。
另外你这段验证代码本身的时间复杂度是O(1)，因为循环的上限是固定的25，执行次数是固定常数，不会随任何输入规模变化。

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