O(n) 和给定代码的时间复杂度函数

Question

如果以下循环结构处于上限分析中，它是否仍然计算为 O(n^2)？我很困惑，因为内部循环依赖于外部循环，并且每次外部迭代时，内部 for 循环都会少循环一次。除了 O(n) 是什么之外，时间复杂度函数是否会是“n!.n+C”（其中 C 是常数）？我假设n！因为内循环。

for(int i=n;i>0;i--)
{
 for(int j=i;j>=1;j--)
  {
     count++;
  }
}

Answer 1

该代码与问题中的代码具有相同的时间复杂度。

\n

for(int i = 0; i < n; i++){  // outer loop\n    for(int j = 0; j < i; j++){  // inner loop\n        count++;\n    }\n}\n

在外循环的第一次迭代中 (i = 0)，内循环不执行\xe2\x80\x99t。

\n

在外循环的第二次迭代中 (i = 1)，内循环执行once。

\n

在外循环的第三次迭代中 (i = 2)，内循环执行twice。

\n

因此，在外循环的最后一次迭代 (i = n) 中，内循环执行n times。

\n

因此，该代码执行的总次数为

\n

1 + 2 + 3 + \xe2\x80\xa6 + n

\n

= n(n + 1) / 2（自然数之和公式）

\n

= ((n^2) + n) / 2

\n

= O(n^2)

\n

\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94

\n

另外，请看看这些

\n