java – pascal三角形算法的时间复杂度
发布时间:2020-12-14 06:04:44 所属栏目:Java 来源:网络整理
导读:负责解决以下问题(Pascal Triangle),看起来像这样. [ [1],[1,1],2,3,4,6,1]] 我已经成功实现了代码(见下文),但我很难搞清楚这个解决方案的时间复杂度.列表的操作次数是1 2 3 4 …. n操作次数减少到n ^ 2数学如何工作并转换为Big-O表示法? 我认为这类似于高
负责解决以下问题(Pascal Triangle),看起来像这样.
[ [1],[1,1],2,3,4,6,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; } } 解决方法
复杂度是O(n ^ 2).
代码中每个元素的计算都是在恒定时间内完成的. ArrayList访问是常量时间操作,也是插入,分摊的常量时间. Source:
你的三角形有1 2 …… n个元素.这是arithmetic progression,总和为n *(n 1)/ 2,其为O(n ^ 2) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |