多遞歸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的總和，看看你得到了什麼？

。