algorithm - 再帰的メソッドの実行時間

Question

パスカルの三角形の行 i、列 j のエントリを計算するメソッドの擬似コードを作成しました。

Pascal(i,j)
  if(i==j or j==0)
     return 1;
  return Pascal(i-1,j-1) + Pascal(i-1,j)

私の問題は、実行時間を把握できないことです。指数関数的であることは知っていますが、再帰関係を解くことによってそれを証明する方法がわかりません。

Answer 1

いくつかの例を試して、どれだけ遡るかを確認することをお勧めします。三角形があることを忘れないでください。行 i から始めて、行 i-1 にいます。次のステップでは、行 i-2 にいます。最悪の場合、何行前に戻る必要がありますか?

絵を描き、例を挙げて直感を構築します。i=6 のいくつかの例から証明を見つけるのは非常に簡単です。