负责解决以下问题(帕斯卡三角形),它看起来像这样。
[
[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;
}
}