質問

私は、再帰とbig-O表記法を含む最近のコンピューターサイエンスの宿題に取り組んできました。私はこれをかなりよく理解していると思います（しかし、完全にではありませんが！）。しかし、特に私に最も問題を与えている質問が1つあります。奇妙なことは、それを見ると、宿題で最も単純なものに見えることです。

次の再発の解決策にビッグオー表記を使用して、最高の成長率を提供しますか？

T（1）= 2

T（n）= 2T（n-1）+ 1はn＆gt; 1

また、選択肢は次のとおりです。

  • O（n log n）
  • O（n ^ 2）
  • O（2 ^ n）
  • O（n ^ n）

私は、大きなOが上限として機能し、そのプログラムまたはプロセスにかかる計算の最大量、または最長の実行時間を記述することを理解しています。この特定の再帰はO（n）である必要があります。なぜなら、最大で再帰はnの各値に対して1回しか発生しないからです。 nは使用できないため、O（nlogn）よりも優れているか、他の3つのオプションであるかのどちらかです。

だから、私の質問は次のとおりです。なぜこのO（n）ではないのですか？

役に立ちましたか？

解決

繰り返しを解決するには、置換、繰り返しツリー、マスター定理の2つの方法があります。マスター定理はマスター定理形式に適合しないため、ケースでは機能しません。

他の2つの方法を使用できますが、この問題の最も簡単な方法は、反復的に解決することです。

T（n）= 2T（n-1）+ 1
T（n）= 4T（n-2）+ 2 + 1
T（n）= 8T（n-3）+ 4 + 2 + 1
T（n）= ...

パターンを参照してください

T（n）= 2 n-1 ＆＃8901; T（1）+ 2 n-2 + 2 n-3 + ... + 1
T（n）= 2 n-1 ＆＃8901; 2 + 2 n-2 + 2 n-3 + ... + 1
T（n）= 2 n + 2 n-2 + 2 n-3 + ... + 1

したがって、最も厳しい境界は＆＃920;（2 n ）です。

他のヒント

質問を少し誤解したと思います。再発を解決するのにどれくらい時間がかかるかは尋ねません。ソリューション自体のbig-O（漸近境界）が何であるかを尋ねています。

あなたがしなければならないことは、閉じた形式のソリューションを思いつくことです。 e。 T（n）の非再帰的な式を使用して、その式のbig-Oを決定します。

問題は、再発の計算コストではなく、再発の解決策の大オー表記を求めていることです。

別の言い方をすれば、繰り返しの結果：

  1 -> 2
  2 -> 5
  3 -> 11
  4 -> 23
  5 -> 47

シーケンス2、5、11、23、47、...を最もよく表す大王表記法

それを解決する正しい方法は、回帰方程式を解くことです。

これは指数関数的だと思います。 nを増やすごとに、値が2倍になります。

T(2) = 2 * T(1) = 4
T(3) = 2 * T(2) = 2 * 4
...

T（x）は、次のプログラムの実行時間です（例）：

def fn(x):
 if (x == 1):
  return    # a constant time
 # do the calculation for n - 1 twice
 fn(x - 1)
 fn(x - 1)
  

これは指数関数的だと思います。 nの増分ごとに2倍の計算が行われます。

いいえ、そうではありません。それどころか：

n 回の反復では、実行時間は R になると考えてください。次に、 n + 1回の反復に対して、正確に R + 1を取得します。

したがって、成長率は一定であり、全体の実行時間は確かに O （ n ）です。

しかし、Dimaの質問に対する仮定は正しいと思いますが、彼の解決策は非常に複雑です：

  

あなたがしなければならないことは、閉じた形式のソリューションを思いつくことです。 e。 T（n）の非再帰的な式を使用して、その式のbig-Oを決定します。

T （ n ）と T （ n + 1）の相対的なサイズを調べるだけで十分です。繰り返し、相対的な成長率を決定します。量は明らかに2倍になり、漸近的な成長を直接与えます。

まず、4つの答えはすべてO（n）よりも悪いです... O（n * log n）は、従来のO（n）よりも複雑です。大きいもの：8または8 * 3、16または16 * 4など...

実際の質問について。再帰を行わない場合、一般的な解決策は明らかに一定の時間で解決できます

（T（n）= 2 ^（n-1）+ 2 ^（n）-1）、彼らが求めているものではありません。

そして、ご覧のように、再帰コードを書くと：

int T( int N )
{
    if (N == 1) return 2;
    return( 2*T(N-1) + 1);
}

明らかにO（n）です。

それで、それはひどい言葉遣いの質問のように見えます、そして、彼らはおそらくあなたにコードの複雑さではなく、関数自体の成長を求めています。それは2 ^ nです。さあ、残りの宿題をして... O（n * log n）を調べてください

再帰に対する閉形式解の計算は簡単です。 調べてみると、ソリューションは次のように推測されます

T(n) = 3*2^(n-1) - 1

その後、帰納法により、これが実際に解決策であることを証明します。ベースケース：

T(1) = 3*2^0 - 1 = 3 - 1 = 2. OK.

誘導：

Suppose T(n) = 3*2^(n-1) - 1. Then
T(n+1) = 2*T(n) + 1 = 3*2^n - 2 + 1 = 3*2^((n+1)-1) - 1. OK.

最初の等式は繰り返し定義に由来し、 そして、帰納的仮説からの二番目。 QED。

3 * 2 ^（n-1）-1は明らかにTheta（2 ^ n）なので、正しい答えは3番目です。

O（n）と答えた人々へ：Dimaにはこれ以上同意できませんでした。この問題は、T（n）を計算するためのアルゴリズムの計算の複雑さの厳密な上限を要求しません（閉じた形式が提供されているため、O（1）になります）。この問題は、T（n）自体の最も厳密な上限 を求めますが、これは指数関数です。

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