performance - 计算时间复杂度（输入可被 2 整除）

Question

我将如何计算这部分代码的时间复杂度或 T(n)？

j=1;
while(j<=n/2){
   i=1;
   while(i<=j){
      cout<<j<<i;
      i++;
   }
   j++
}

我想你可以假设 n 可以被 2 整除。

Answer 1

除以常数不会改变O(...). 确切的可分性也不重要。就像j一直到的算法一样n，这是一个O(N^2)算法。

Answer 2

while(j<=n/2){            |      n/2+1
   i=1;                   |      n/2
   while(i<=j){           |      1+n/2(n/2+1)/2 =1+n(n+1)/8
      cout<<j<<i;         |      n(n+1)/8
      i++;                |      n(n+1)/8
   }                      |
   j++                    |      n/2
}                         |

总体： O(n ² )

Answer 3

计算迭代的总数并不难。j 的范围是 j=1, 2, ..., n/2。对于 j 的每个值，i 的范围是 i = 1, 2, ..., j。因此，对于外循环的每个值，内循环都有 j 次迭代。这意味着迭代的总数为：

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

[注意：我在这里使用身份 1 + 2 + ... + k = k(k+1)/2。]

如前所述，此函数为 O(n^2)。