以下算法的复杂性

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²).