1

您认为下面的伪代码对于计算帕斯卡三角形是否正确？它的时间和空间复杂度会是多少？我该如何计算呢？

pascal triangle(n){
    list<list<int>> triangle // double list saving the triangle




    triangle.get(0).add(1)
    for(int i=1; i<n; i++){
        for(int j=0; j<i; j++){
            if(triangle.get(i-1).get(j)==null || triangle.get(i-1).get(j-1)==null)  
                triangle.get(i).add(1)
            else
                triangle.get(i-1).add(triangle.get(i-1).get(j)+triangle.get(i-1).get(j-1))

        }

    }

    print(triangle)
}
4

1 回答 1

2

您的伪代码看起来很有意义。

对于复杂性

您的算法试图计算三角形的每个数字一次。如果我们让每个计算的时间复杂度恒定，那么我们正在做：

sum(i) (0 -> n)

请原谅糟糕的符号 澄清：

如果n为6，那么我们将迭代6 + 5 + 4 + 3 + 2 + 1次。这种实际的复杂性可以简化为：

(n + 1) * (n/2)

有效

O(n^2)

另一种看待复杂性的方式

您本质上是在迭代中做三角形的面积，即b*h/2. 好吧，我们知道帕斯卡三角形的高度是n。三角形（或底）的底部有n 个数字。因此，我们正在生成：

n^2/2

复杂度为O(n^2)

于 2013-09-18T00:00:37.040 回答