java - 帕斯卡三角算法的时间复杂度是多少

Question

任务是解决以下问题(帕斯卡三角形)，看起来像这样。

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

我已经成功地实现了代码(见下文)，但我很难弄清楚这个解决方案的时间复杂度。列表的操作数是 1 + 2 + 3 + 4 + .... + n 操作数会减少到 n^2 数学如何工作并转化为 Big-O 符号？

我认为这类似于高斯公式 n(n+1)/2 所以 O(n^2) 但我可能错了非常感谢任何帮助

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        if(numRows < 1) return new ArrayList<List<Integer>>();;
        List<List<Integer>> pyramidVal = new ArrayList<List<Integer>>();

        for(int i = 0; i < numRows; i++){
            List<Integer> tempList = new ArrayList<Integer>();
            tempList.add(1);
            for(int j = 1; j < i; j++){
                tempList.add(pyramidVal.get(i - 1).get(j) + pyramidVal.get(i - 1).get(j -1));
            }
            if(i > 0) tempList.add(1);
            pyramidVal.add(tempList);
        }
        return pyramidVal;
    }
}

Answer 1

复杂度为 O(n^2)。

代码中元素的每个计算都是在常数时间内完成的。 ArrayList 访问是恒定时间操作，以及插入，摊销恒定时间。 Source :

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time

您的三角形有 1 + 2 + ... + n 个元素。这是 arithmetic progression总和为 n*(n+1)/2，在 O(n^2)

中