algorithm - 这个嵌套for循环算法的时间复杂度？

Question

我在计算该算法的 bigO 时遇到了一些麻烦:

public void foo(int[] arr){
  int count = 0;
  for(int i = 0; i < arr.length; i++){
    for(int j = i; j > 0; j--){
      count++;
    }
  }
}

我知道第一个 for 循环的时间复杂度为 O(n)，但我不知道什么是嵌套循环。我在想 O(logn) 但我没有可靠的推理。我确信我错过了一些非常简单的事情，但一些帮助会很好。

Answer 1

让我们注意n数组的长度。

如果单独考虑第二个循环，它只是一个函数 f(i) ，并且因为它将迭代 i 中的所有元素至1 ，其复杂度为 O(i) 。既然你知道j<n ，你可以说它是 O(n) 。然而，不涉及对数，因为在最坏的情况下，即j=n ，您将执行n迭代。

至于评估两个循环的复杂性，请观察 i 的每个值，第二个循环经过 i迭代，所以总迭代次数为

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

这是 O(n^2) .