java - 帕斯卡三角算法分析

Question

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

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)
}

Answer 1

你的伪代码看起来很有道理。

对于复杂性

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

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)