递归帕斯卡三角算法的多时间复杂度解决方案？

Question

我在 Java 中创建了以下简单算法，它以二维整数列表的形式以递归方式计算 Pascal 三角形：

public class PascalTriangleRec{
    private final int[][] points;

    public PascalTriangleRec(int size){
        points = new int[size][];
        for (int i =0;i<size;i++){
            int[] row  = new int[i+1];
            for (int j = 0;j<=i;j++){
                row[j]=getValueAtPoint(i,j);
            }
            points[i]=row;
        } 
    }
    public static int getValueAtPoint(int row, int col){
        if (col == 0 || col == row) return 1;
        else return getValueAtPoint(row-1,col-1) + getValueAtPoint(row-1,col);
    }
}

我需要知道这个算法的时间复杂度。我在 Whosebug 上发现 another question 给出了 getValueAtPoint 函数的时间复杂度为 O(2^n/sqrt(n))。我算了一下，由于这个函数嵌入了两个嵌套的for循环，所以整个Pascal三角形的时间复杂度是O(sqrt(n^3)*2^n)。我很确定这个推理是正确的。

另一方面，我设计了一种完全不同的方式来思考这个问题，如下所示：

有一个特定的属性帕斯卡三角形称为帕斯卡推论 8。这个属性指出给定行 r 上所有系数的总和等于 2^r，其中 r从 0 开始。

您还可以注意到，我的代码示例中的 getValueAtPoint 函数将不断递归调用自身，直到它在某个时刻 returns 1 为止。这意味着帕斯卡三角形中的所有系数都是通过将该系数的值加 1 的次数形成的。

由于加 1 需要常数时间，因此可以说计算三角形中给定行所需的时间等于某个常数时间乘以该行中所有系数的组合值。这意味着三角形中给定行 r 的时间复杂度必须是 2^r.

计算整个三角形所需的时间等于计算三角形中所有行所需时间的总和。这会产生一个几何级数，计算 r 从 0 到 n-1 的所有 2^r 的总和。

利用几何级数的求和属性，这个级数可以改写成下面的form。

这意味着根据最后这个推导算法的时间复杂度是O(2^n)。

这两种方法产生不同的结果，尽管它们对我来说似乎都是合乎逻辑且正确的。我的问题首先是这两种方法是否正确，是否可以同时将两者视为正确？在我看来，它们都是正确的，但第二个更准确，因为对于第一个，最坏情况是针对 getValueAtPoint 函数，并应用于所有系数，现实中显然不是这样。这是否意味着第一个变得不正确，即使其背后的逻辑是正确的，只是因为存在更好的方法？

Answer 1

简单的答案是 "too many variables"。首先，您的分析是完全正确的：复杂性取决于所有计算值的总和。同样的逻辑是得到你 O(2^n/sqrt(n)).

的答案的基础

有两个问题：

小问题: Stirling 的近似就是：省略了一些项。我认为当你组合所有循环时它们会消失，但我必须处理这些令人讨厌的细节才能确定。
大问题：你合并的n的值不一样n。您合并的最后一个 n 值是 i 运行从 0 到大小； i 的每个值变为 n 用于初始调用 getValueAtPoint.

尝试对之前的复杂度进行从 0 到 n 的求和，看看会得到什么？

.

递归帕斯卡三角算法的多时间复杂度解决方案？

Multiple time complexity solutions for recursive Pascal triangle algorithm?

java

recursion

time-complexity

pascals-triangle