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

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

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

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

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

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

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

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

1 + 2 + 3 + … + n

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

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

= O(n^2)

,

还有，一定要看看这些

1. https://stackoverflow.com/a/71805214/17112163
2. https://stackoverflow.com/a/71537431/17112163
3. https://stackoverflow.com/a/71146522/17112163
4. https://stackoverflow.com/a/72046825/17112163
5. https://stackoverflow.com/a/72046933/17112163

Answer 2

让我们假设，外部循环的值是n，内部循环的值是内部循环的值。(循环的反转情况)。可以使用公式

计算完整的计数内循环和k = 1 . .N (k) = N * (N +1)/2 = 1/2 * N ^2 +1/2 N

时间复杂度为

O(1/2 * n^2 + 1/2 n) = O(n²+ n) = O(n²)