如何计算该算法的时间复杂度？

Question

我一直在尝试计算这个算法的时间复杂度，但我认为我是对的。

因为不可能是n^2，所以我想出了一个O(n*(j*(1+j)*50)的公式，但我还是不太确定

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i ; j++)
        for (int k = 1; k <= 100; k++)
           cout << "Hello";

如有任何帮助，我们将不胜感激。

Answer 1

这确实是O(n²)。内部循环以恒定时间运行。与

相同

for(int i = 1;i<=n;i++)
  for(int j = 1;j<=i;j++) {
      cout << "Hello";
      cout << "Hello";
      cout << "Hello";
      cout << "Hello";
      /* repeats 96 mores times */
  }

更具体地说，您可以将步数计算为

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

常数无关紧要，所以这个函数在 O(n² + n) 中增长，这就是 O(n²).

您可以将所有内容乘以 100，而不是展开内部循环，但这不会改变复杂性。

如何计算该算法的时间复杂度？

How do I calculate the time complexity of this algorithm?

time

complexity-theory