什麼是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)