什么是pascal三角形算法的时间复杂度

Question

解决以下问题（帕斯卡三角形）的任务看起来像这样。

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

我已经成功地实施了代码（见下文），但我有一个艰难的时间搞清楚的时间复杂度会是什么这个解决方案。按列表操作的次数是1 + 2 + 3 + 4 + .... + n将操作数减少到n^2数学如何工作并转化为大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：

大小，的isEmpty，获取，设置迭代器和操作的ListIterator在固定时间内运行 。添加操作以摊销后的恒定时间运行

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