嵌套循环时间复杂度

for (i = 0; i <= n; i = i +2) 
    for (j = n; j >= i; j - -)

我知道外部循环运行的N/2 + 1次嵌套循环时间复杂度

我找不出多少次会内循环运行

if we assume n = 10 

the inner loop runs for 10 times when i = 0 
the inner loop runs for 8 times when i = 2 
and so on but i cant figure out what time complexity would that be?

来源

2015-09-07 Fahdie

它可能有助于知道'1 + 2 + ... + n = n *（n + 1）/ 2'。请参阅[三角形数字]（https://en.m.wikipedia.org/wiki/Triangular_number） –

貌似平均数内循环内的迭代次数为n/2。然后：

(n/2 +1) * n/2

来源

2015-09-07 22:29:30 Jurlie

让我们假设一个任意n和考虑的i这样0 <= i <= n。你说得对，外环将运行n/2+1次。

我们来看看对于给定的n和i，内循环将运行多少次。内环的的J值从我去到n喜欢这个

i, i+1, i+2, i+3, ..., n 
|______________________| 
      | 
     n-i+1 terms

所以基本上的步骤的内部循环需要的数量是这个顺序，如果你看一下这方面的数量n-i+1（你实际上有一个错误你的问题;如果n = 10和i = 0，内循环需要11步而不是10）。

因此，要获得两个循环的总步数，我们需要sum n-i+1 for i=0 to i<=n, i+=2。让S(n-i+1)表示这个总和。然后：

S(n-i+1) 
= S(n+1) - S(i) 
= (n+1)*S(1) - S(i) # since n+1 is a constant we can pull it out 
= (n+1)*(n/2 + 1) - S(i) # S(1) is just equal to the number of steps of the outer loop which is n/2+1 
= (n+1)*(n/2 + 1) - (0 + 2 + 4 + ... + n)

现在S(i) = 0 + 2 + 4 + ... + n这是一个arithmetic progression。这样做的总和n*(n/4+1/2)因此我们的总金额是

= (n+1)*(n/2 + 1) - n*(n/4+1/2) 
= n^2/2 + n + n/2 + 1 - n^2/4 -n/2 
= n^2/4 + n + 1

这样一来，主项是导致的O(n^2)复杂n^2。

来源

2016-08-21 05:13:41 gowrath

嵌套循环时间复杂度

回答

相关问题