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

Question

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

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

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

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

帕斯卡三角形有一个特定的性质，称为帕斯卡推论 8。该性质表明给定行 r 上的所有系数之和等于 2^r，r 从 0 开始。

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

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

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

利用几何级数的求和性质，这个级数可以重写为:form .

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

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

Answer 1

简单的答案是“变量太多”。首先，您的分析完全正确:复杂性取决于所有计算值的总和。同样的逻辑也是 O(2^n/sqrt(n)) 答案的基础。

有两个问题:

• 小问题:斯特林的近似就是这样:省略了一些术语。我认为当你组合所有循环时它们就会脱落，但我必须解决令人讨厌的细节才能确定。
• 大问题:您组合的n值并不相同n。您合并的最后一个 n 值是从 0 到 size 的 i；对于 getValueAtPoint 的初始调用，i 的每个值都变为 n。

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

.