为什么这道题的大O时间复杂度是C？
Why is the big O time complexity for this questions is C?
The screenshot of the question
我的计算是：
statement | time
------------------------|--------
var value = 0; | 1
for(var i=0;i<n;i++) | 1 + (n+1) + n
for(var j=0;j<i;j++); | n + n*(n(n+1)/2 +1) + n* n(n+1)/2
value += 1; | n*(n(n+1)/2
让我们看看最初的几次迭代计数。
i (counter) j (# of iterations for each value of i)
0th 0
1st 1
2nd 2
. .
. .
(n-1)th n-1
现在前 N 个整数的总和定义为 n(n+1)/2，其中范围从 1 开始，一直到 n。更多详情 here.
在我们的例子中，范围从 0 开始，一直到 n-1（上面的 RHS table）。将求和公式中的 n 替换为 n-1，得到 n(n-1)/2.
Big O 的复杂度是 O(n*n)，所以 n 的平方。
运算次数为n(n-1)/2
Big O 复杂度忽略常量和低阶项。
问题表述不当，因此没有准确答案。事实上，作者并没有说哪个操作“重要”。例如，当i=0时，内层循环执行一次（至少初始化和测试），而它的循环体则不执行。
现在如果我们只计算 value 的递增次数，最内层的循环恰好执行其中的 i 个，而外层循环使 i 从 0 变为 n-1。因此总共有 Tn-1 = n(n-1)/2（三角数）。
The screenshot of the question
我的计算是：
statement | time
------------------------|--------
var value = 0; | 1
for(var i=0;i<n;i++) | 1 + (n+1) + n
for(var j=0;j<i;j++); | n + n*(n(n+1)/2 +1) + n* n(n+1)/2
value += 1; | n*(n(n+1)/2
让我们看看最初的几次迭代计数。
i (counter) j (# of iterations for each value of i)
0th 0
1st 1
2nd 2
. .
. .
(n-1)th n-1
现在前 N 个整数的总和定义为 n(n+1)/2，其中范围从 1 开始，一直到 n。更多详情 here.
在我们的例子中，范围从 0 开始，一直到 n-1（上面的 RHS table）。将求和公式中的 n 替换为 n-1，得到 n(n-1)/2.
Big O 的复杂度是 O(n*n)，所以 n 的平方。
运算次数为n(n-1)/2
Big O 复杂度忽略常量和低阶项。
问题表述不当，因此没有准确答案。事实上，作者并没有说哪个操作“重要”。例如，当i=0时，内层循环执行一次（至少初始化和测试），而它的循环体则不执行。
现在如果我们只计算 value 的递增次数，最内层的循环恰好执行其中的 i 个，而外层循环使 i 从 0 变为 n-1。因此总共有 Tn-1 = n(n-1)/2（三角数）。