这个循环的时间复杂度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=50c=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/

10-11 22:06
查看更多