两个 for 循环的大 O 表示法是什么

Question

我很难分析这段代码：

public int example(int[] arr){
    int n = arr.length, total = 0 ; 
    for (int i=0; i < n; i++) 
        for (int j=0; j <= i; j++) 
            total += arr[j];
    return total;
}

这两个循环没有花括号。我无法分析它们的时间复杂度。我需要帮助计算他们两个的操作时间。

Answer 1

是O(n<sup>2</sup>)，因为有两层循环。没有大括号并不重要。

外循环执行O(n)次，内循环先执行一次，再执行两次，直至执行n次。这是从 1 到 n 的等差数列，其中公差为 1。因此其总和为

(1 + n) * (n) / 2

= (n^2 + n) / 2

= O(n^2)

该代码可以用花括号重写如下：

  for (int i=0; i < n; i++) {
      for (int j=0; j <= i; j++) {
         total += arr[j];
      }
  }

Answer 2

第一个循环执行了 O(n) 次。嵌套循环执行 O(n) 次。

总的来说 O(n^2)。

两个 for 循环的大 O 表示法是什么

What's the big O Notation for the two for loops

java

algorithm

big-o