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

Question

负责解决以下问题(Pascal Triangle),看起来像这样.

[
     [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访问是常量时间操作,也是插入,分摊的常量时间.来源:

size,isEmpty,get,set,iterator和listIterator操作以恒定时间运行.添加操作以分摊的常量时间运行

你的三角形有1 + 2 + ... + n元素.这是算术进展,总结为n*(n+1)/2,即O(n^2)