算法分析刷新帮助

Question

我已经很长一段时间没有接触到算法复杂性了，所以我想做一次复习。

我试图在下面的for循环中找出步骤的数目。

for(i = 0; i < n; i++){  
  //code  
  for(j = i + 1; j < n; j++){  
     //code  
  }  
}  

内循环将被执行。

《时代》

我指的是j的每一个值的t次，对吗？

在最坏的情况下，tj将等于n。因为它将运行n-(i+1)-1次。

那么，我对这一分析的方法正确吗？

Answer 1

内部代码将执行(n-1)*(n/2)次。

查看前几次迭代和结束条件有助于提供一个通用模式。

当i=0时，内部代码将从1到n- (n-1次)

当i=1时，内部代码将从2到n- (n-2次)

。

。

当i=n-2时，内部代码将从(n-1)到n- (n-(n-1))

(n-1) + (n-2) +.+ (n-(n-1)) = (n-1)*(n/2)