4

再帰階乗アルゴリズムの漸化式はなぜこれなのですか？

T(n)=1 for n=0
T(n)=1+T(n-1) for n>0

なんでこれじゃないの？

T(n)=1 for n=0
T(n)=n*T(n-1) for n>0

nの値、つまり1,2,3,4 ......を置くと、最初の漸化式ではなく、2番目の漸化式が成り立ちます（階乗は正しく計算されます）。

4

9 に答える 9

11

通常、アルゴリズムの時間計算量を見つけるために漸化式を使用します。

ここで、関数T（n）は実際には階乗の値を計算するためのものではありませんが、階乗アルゴリズムの時間計算量について教えてくれます。

これは、nの階乗を見つけるために、n-1の階乗（つまり、T（n）= T（n-1）+1）よりも1多くの操作が必要になることを意味します。

したがって、再帰的階乗アルゴリズムの正しい漸化式は、n = 0の場合はT（n）= 1、n> 0の場合はT（n）= 1 + T（n-1）です。これについては、後で説明します。

ハノイの塔の漸化式のように、n> 0の場合はT（n）= 2T（n-1）+1です。

更新：一般的に実装とは何の関係もありません。しかし、繰り返しはプログラミングパラダイムの直感を与えることができます。たとえば、T（n）= 2 * T（n / 2）+ n（マージソート）の場合、nを半分にダイビングしているため、分割統治の直感が得られます。

また、方程式を解くと、実行時間に制限があります。たとえば、ビッグオー表記です。

于 2014-09-12T17:19:26.557 に答える
7

T（n）は、一定の時間乗算を想定した、再帰的階乗アルゴリズムの時間計算量の漸化式のように見えます。おそらくあなたはあなたの情報源を読み間違えましたか？

于 2009-09-04T16:59:52.460 に答える
5

彼が述べたのは階乗の再帰ではなく、時間の複雑さでした。
これがそのような再発の擬似コードであると仮定します。

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)
  • 末尾再帰の除去は含まれていないと思います。

2行目と3行目は、一定の時間c1とc2を要します。
4行目も一定の時間かかります。ただし、factorial（n-1）を呼び出すため、T（n-1）の時間がかかります。また、T（n-1）を使用すると、factorial（n-1）にnを掛けるのにかかる時間は無視できます。
関数全体の時間は、T（n）= c1 + c2 + T（n-1）の合計です。
これは、big-o表記では、T（n）= 1 + T（n-1）になります。

これは、Diamが指摘したように、フラットな再帰であるため、実行時間はO（n）である必要があります。ただし、そのスペースの複雑さは非常に大きくなります。

于 2011-03-18T04:51:16.303 に答える
4

私はあなたが悪い情報を持っていると思います。あなたが引用した2番目の漸化式は、あなたが観察したように正しいものです。最初のものは自然数を生成するだけです。

于 2009-09-04T15:27:21.407 に答える
3

この質問は非常に紛らわしいです...あなたの最初の公式は階乗ではありません。すべてのnについて、単純にT（n）= n+1です。nの階乗は、最初のn個の正の整数の積です。factorial（1）=1。factorial（n）= n * factorial（n-1）。2番目の式は本質的に正しいです。

于 2009-09-04T15:31:39.183 に答える
3

T（n）= T（n-1）+ 1は、nの階乗の正しい漸化式です。この方程式は、nの階乗の値ではなくnの階乗を計算する時間を与えます。

于 2015-01-09T21:23:10.460 に答える
2

最初のものはどこで見つけましたか？それは完全に間違っています。

値が何であれ、毎回1を追加するだけです。

于 2009-09-04T15:27:59.143 に答える
2

まず、基本的な操作を見つける必要があります。この例では、乗算です。乗算は、再帰ごとに1回発生します。したがって、T（n）= T（n-1）+1この+1は基本的な操作です（この例では多重化）T（n-1）は次の再帰呼び出しです。

于 2019-04-12T18:30:21.347 に答える
1

TL; DR：あなたの質問に対する答えは、実際には、漸化式が定義しているシーケンスによって異なります。つまり、質問のシーケンスT nが階乗関数を表すのか、階乗関数Xを計算するための実行時間コストを表すのかを示します。

階乗関数

n、f nの階乗の再帰的定義は、次のとおりです。

f n =n•fn -1（n> 0、 f 0 = 1の場合） 。

ご覧のとおり、上記の方程式は実際には漸化式です。これは、初期項（つまり、f 0 = 1）とともに、シーケンス（つまり、階乗関数、f n ）を再帰的に定義する方程式だからです。

階乗を計算するための実行時コストのモデリング

ここで、nの階乗を計算するための実行時コストを表すためのモデルを見つけます。Tnを計算の実行時間コストfnと呼びましょう。

上記の階乗関数fnの定義を見ると、その実行時間コストT nは、f n-1を計算する実行時間コスト（つまり、このコストはT n-1）と実行時間コストで構成されます。 nとfn -1の間の乗算を実行します。乗算は一定時間で達成されます。したがって、 T n = T n-1 +1と言えます。

しかし、T 0の値は何ですか？T 0は、 f0を計算するための実行時コストを表します。f 0の値は最初は定義上既知であるため、f0を計算するための実行時のコストは実際には一定です。したがって、 T 0 =1と言えます。

最後に、取得するものは次のとおりです。

T n = T n-1 + 1（n> 0、T 0 = 1の場合） 。

上記の方程式も漸化式です。ただし、それが（最初の項とともに）定義するのは、階乗関数を計算する実行時のコストをモデル化するシーケンスです。

X漸化式のシーケンスがどのように呼ばれるか（つまり、 T n ）を考慮すると、後者、つまり階乗関数を計算するための実行時間コストを表す可能性が非常に高いと思います。

于 2019-01-27T14:37:01.527 に答える