多递归Pascal三角算法的时间复杂性解决方案？

Question

我已经在Java中创建下列简单的算法，计算以递归的方式帕斯卡三角，在INTS的二维列表的形式：

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

我需要知道该算法的时间复杂度。我在StackOverflow上发现了another question，它将getValueAtPoint函数的时间复杂度设置为O（2^n/sqrt（n））。我认为，由于这个函数嵌入到两个嵌套for循环中，整个Pascal三角形的时间复杂度为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

简单的答案是“变量太多”。首先，你的分析是完全正确的：复杂性取决于所有计算值的总和。同样的逻辑基础得到你的答案（2^n/sqrt（n））。

有两个问题：

• 小问题：斯特灵公式就是：一些术语省略。我想认为当你结合所有的循环，他们会掉出来，但我必须通过讨厌的细节来确定。
• 大问题：中n个值你结合是不一样的ñ。最后n你加入的价值是i运行从0到大小; i的每个值变为n初始呼叫getValueAtPoint。

试着对你之前的复杂度做0到n的总和，看看你得到了什么？

。