time-complexity - 时间复杂度：简单的循环计算

Question

我有一个像这样的简单循环：

for (int i = 0; i < n; i++) {
  // constant time operation
}

很容易看出它的时间复杂度为 O(n)，但如果我们计算它，为什么它是2*n + 2 + c*n（给定答案）而不是(1+ (n+1) + 2*n + c*n) = (3+c)*n + 2？我认为i++有 2 个操作：加法和赋值；因此，它应该是2*n，并且常数操作是执行n次数，所以它是c*n。

标签： time-complexity

Answer 1

2*n

（n比较 ( i<n) +n增量 ( i++)）== 2*n

2

（i=0 1分配+1分配i）== 2

c*n

（n恒定时间操作）== c*n