algorithm - 以下算法的复杂性

Question

我试图找到以下算法的复杂性:

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

Answer 1

由于您的 k 以“i”开头并上升到“j”，因此最坏情况下的时间复杂度为 O(n²)。让我们举个例子看看。对于 i=4，j 从 1 到 4，k 只针对 j 的每个值运行一次(j=4 除外，它恰好运行 2 次)。因此，对于 j 的每个值，内部循环在 O(1 ) 时间。外面的两个循环需要 O(n²) 时间。另外，考虑到最内层循环中的 (//code) 在 O(1) 时间内运行。因此，该算法的时间复杂度为O(n²)。