嵌套循环中的时间复杂度计算

Question

我有以下代码

1 for (i = 0; i < n; i++) 
2  for (j = 0; j < i; i++)
3    result = result + 1;

我知道时间复杂度是 O(n^2)，但我无法按照我们收到的材料所解释的方式计算时间复杂度。

根据上述资料，一个循环的时间复杂度是

T = T1 + n(T1 + T2)

其中T1是循环条件，T2是循环内的指令。将其应用于练习时，我得到：

T = T1 + n(T1 + T2-3) 
  = T1 + n(T1 + T2 + (1+2+3...+n)(T2 + T3)).

由于T1、T2和T3都是O(1)，我们得到

T = n * (1+2+3+...+n)
  = n * n * (n+1) / 2 
  = n^3.

但这显然是错误的，所以...我做错了什么？

Answer 1

你的推导在 T2-3 的展开是错误的：

T2-3 = T2 + i * ( T2 + T3 )
     < T2 + n * ( T2 + T3 )
     = O(n)

您没有单独分析内循环，而是在写下求和时第二次考虑了外循环迭代。因此你想出了一个额外的因素 n.

Time complexity calculation in a nested loop