嵌套循环时间复杂度 [英] Nested Loop Time complexity

问题描述

 为（i = 0; I＆LT; = N，I = I +2）
     为（J = N; J＆GT; = I;的J  -   - ）
 

我知道外部循环运行的N / 2 + 1次

我无法弄清楚有多少次会内循环运行

 如果我们假设N = 10

内循环运行10次当i = 0
内循环运行了8次当i = 2
等等，但我不能找出时间复杂度会是这样？
 

解决方案

看起来像迭代中内环平均数 N / 2 。然后：

 （N / 2 + 1）* N / 2
 

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

I know the outer loop runs for n/2 + 1 times

i cant figure out how many times would the inner loop runs

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? 

解决方案

Looks like average number of iterations within inner loop is n/2. Then:

(n/2 +1) * n/2

这篇关于嵌套循环时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！