递归 Pascal 三角程序成本分析

Question

#include<iostream>
using namespace std;

int pascal(int row, int col) 
{
  if (col == 0 || col == row) 
  {
    return 1;
  } 
  else
  {
    return pascal(row - 1, col - 1) + pascal(row - 1, col);
  }
}


int main()
{
    system("cls");
    int row;
    cout<<"Enter n : ";
    cin>>row;

    
    for (int i=0;i<row;i++)
    {
        for(int col =0;col<=i;col++)
            cout<<pascal(i,col);

        cout<<"\n";
    }

    return 0;
}

我看懂了Main Function的成本分析，但是我看不懂Recursive Function的成本分析。递归部分pascal(i-1,j-1) + pascal(i-1,j) 运行?

有多少次

Answer 1

首先，我不确定您要计算的确切内容，但您可能需要更多地关注边缘情况，例如row < col.

的否定论据或案例

现在，如果没有 col == row 条件（假设 col >= 0），总调用次数将是帕斯卡三角的总和，大致为 pow(2, col+1) - 1。因此，这是成本的简单上限。

在 col == row 处（假设最初 row > col），您的树被“截断”。从这一点计算复杂度是一个有趣的数学问题，它超出了 Stack Overflow 的范围（尽管您可能想尝试 Math Stack Exchange）。

请注意，此代码效率极低 - 在大多数情况下，指数运行时间的成本过高，并且可以使用 memoization 以显着更低的成本（小于 pow(col, 2)).

递归 Pascal 三角程序成本分析

Cost Analysis of Recursive Pascal Triangle Program

c++

recursion

big-o