パスカル・トライアングル・アルゴリズムの時間複雑さは何ですか？

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 + 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)あるガウス式nに似ています。

コード内の各要素の計算は、一定の時間内に行われます。 ArrayListへのアクセスは、一定時間操作、挿入、償却された一定時間です。 Source：

サイズ、のisEmpty、取得、セット、イテレータ、および反復子の操作は、一定時間内に を実行します。加算演算は償却された一定時間で実行されます

三角形には1 + 2 + ... + n要素があります。これはarithmetic progressionであり、合計はn*(n+1)/2であり、これはO(n^2)