•  21-09-2019
  •  | 
  •  

質問

なぜそのような再発の関係の再帰的要因のアルゴリズム。

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ん。e1,2,3,4......第二次再発の関係を有のfactorialsが正確に計算しないのです。

役に立ちましたか？

解決

この質問は非常に混乱している...あなたの最初の式は階乗ではありません。これは、すべてのnに対して、単にT（N）= N + 1です。 Nの階乗は、第nは正の整数の積である：（1）= 1の階乗（n）は階乗= N *階乗（N-1）。あなたの第二式は、本質的に正しいです。

他のヒント

T（N）のように見えるは、一定時間の乗算を仮定すると、再帰的な階乗アルゴリズムのの時間複雑の漸化式です。おそらく、あなたはあなたのソースを読み違え？

私たちは、一般的に、アルゴリズムの時間の複雑さを見つけることの漸化式を使用します。の

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

<時間> それは、nの階乗を見つけるための手段、それは、n-1の階乗よりも1多くの操作がかかります （すなわち、T（N）= T（N-1）+1）など。

<時間>

再帰階乗アルゴリズムのように正確な漸化式であります T（N）= 1 n = 0で n> 0のためのT（N）= 1 + T（N-1） ないあなたは後述すること。

<時間> ハノイの塔のための再発のような

0> nのT（N）= 2T（N-1）+1

私はあなたが悪いの情報を持っていることを前提としています。あなたが観察しているとあなたが引用二漸化式は、は、の正しいものです。最初のものは、単に自然数を生成します。

あなたが最初のものを見つけましたか？それは完全に間違っています。

はそれが唯一の1の値が何であれ、それぞれの時間を追加するために起こっています。

うませんでしたの要因再帰る時間の複雑さです。
この擬似コードなど再発:

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)
  • 私はこのテール-再帰を消去しない。

2、3のコストを一定時間、c1とc2です。
ライン4コストを一定時間です。しかし、その要因(n-1)を時間T(n-1)です。また、かかる時間が増殖因子(n-1)nのかっこは無視できまT(n-1)を使用します。
時間の関数は、sum:T(n)=c1+c2+T(n-1)です。
これは、big-o記法は減T(n)=1+T(n-1)です。

これは、Diamアセットマネジメントの指摘のように、フラット繰り返し走行時はO(n)そのスペースの複雑さきつつあると見なされているものです。

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

まず、基本的な操作を見つけることがあり、この例では乗算です。乗算は、すべての再帰に一度起こります。そう T（N）= T（N-1）+1 この+1は（この例でmutliplication）基本的な動作であります T（n-1）は、次の再帰呼び出しである。

TL; DR：あなたの質問への答えは実際に依存するのどのような順序のあなたの漸化式はの定義の。それはあなたの問題の配列は、のT <サブ> N のの階乗関数またはの階乗関数の計算の実行時のコストを表しているかどうか、ですの X 。

<時間>

階乗関数

再帰の階乗のdefintion N 、 F <サブ> N の、ある

F <サブ> N = N•F <サブ> N-1 のための N> 0 と F <サブ> 0 = 1

あなたが見ることができるように、それはの方程式のであるから、上記の式は、実際にはの漸化式のある一緒にの初期用語のと、その（すなわち、 F <サブ> 0 = 1 ）、再帰的にの定義A 配列（すなわち、階乗関数、 F <サブ> N ）。

<時間>

階乗

計算の実行時のコストをモデル化 今、私たちはのモデルを見つけるしようとしているのの階乗を計算の実行時のコストを表現するためののN の。レッツ・コールのT <サブ> N ののランニングタイムのコストのコンピューティングののF <サブ> N の。

階乗関数の上記の定義を見ると F <サブ> N 、その走行時のコスト T <サブ> N F <サブ> N-1 の（すなわち、このコストは、 T <サブ> N-1 ）プラス 1、N N と F <サブ>との間の乗算を行うの実行時間コスト。乗算は、一定時間内に達成されます。したがって、我々はそれを言うことができる。 T <サブ> N = T <サブ> N-1 + 1

ただし、のT <サブ> 0 の値は何ですか？ T <サブ> 0 の計算の実行時のコスト F <サブ> 0 を表します。 F <サブ> 0 の値は、最初の定義によって知られているため、計算するための実行時間コスト F <サブ> 0 は実際には定数。したがって、我々は言うことができることのT <サブ> 0 = 1 。

最後に、私たちが入手することはあります：

T <サブ> N = T <サブ> N-1 + 1 のための N> 0 と T <サブ> 0 = 1

この式は、上記にもの漸化式のです。しかし、それは（一緒に最初の用語で）を定義するもの、そのシーケンスはのモデル階乗関数を計算するランニングタイムのコストの。

<時間>

X <サブ>あなたの漸化式でシーケンスが（すなわち、のT <サブ> N の）と呼ばれる方法を考慮して、私はそれを考えます非常に高い後者を表し、すなわち、の階乗関数を計算するランニングタイムのコストの

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top