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) 但我没有充分的理由。我确定我错过了一些非常简单的东西，但一些帮助会很好。

标签： algorithmfor-looptime-complexitybig-o

Answer 1

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

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

至于评估两个循环的复杂性，观察对于 的每个值i，第二个循环经历了 ti次迭代，所以迭代的总数是

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

这是O(n^2)。