这个循环的时间复杂度O(n ^ 2)如何?
for (int i = n; i > 0; i -= c)
{
for (int j = i+1; j <=n; j += c)
{
// some O(1) expressions
}
}
谁能解释?
最佳答案
假设条件
n > 0
c > 0
第一循环
第一个循环以
i=n
开始,并在每个步骤中都从c
减去i
。一方面,如果c
大,则第一个循环将仅重复几次。 (尝试使用n=50
,c=20
,您将看到)。另一方面,如果c
小(假设c=1
),则它将迭代n
次。第二循环
第二个循环是相同的推理。如果
c
大,则仅迭代几次,如果c
小,则多次迭代,最坏的情况是n
次。组合/大O
大O表示法为算法的
upper bound
提供了time complexity
。在您的情况下,第一和第二循环上限相结合,它为您提供了一个O(n*n)=O(n^2)
。关于c - 这个循环的时间复杂度O(n ^ 2)如何?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/53773463/