私はこの機能を与えられており、時間の複雑さを知りたいです:
int f2(int n) {
if(n<2) return 1;
return f2(n/2)+f2(n-2);
}
テレスコピック展開法を使用して、ランタイムを O(n 2 ) と計算しました。これは正しいです？
編集:再考した後、この関数は複雑度 Θ(n log n) を持つマージソートと同様の構造を持っていることがわかりました。あれは正しいですか？
1981 次
6 に答える
1
TL;DR: 再帰は n O(log n)だと思います。これは超多項式ですが指数関数的ではありません。一致する下限がなく、これが厳しいとは思えませんが、進歩です!
指数関数的ではないが超多項式の上限を取得できると思います。多項式の境界がないことを示す@Adam Rosenfieldの回答と組み合わせると、これは次のことを示しています
- 再帰には多項式の範囲はありませんが、
- 指数境界は弱くなければなりません。
解決したい再発は
T(n) = T(n - 2) + T(n / 2) + 1
T(1) = T(2) = 1
私が持っていたアイデアの 1 つは、この再発を特定の順序で評価できるかもしれないというものでした。T(n) を評価したいとします。これを 1 ステップ実行すると、
T(n - 2) + T(n / 2) + 1
ここで、T(n - 2) 項を展開するとします。これは与える
T(n - 4) + T(n / 2 - 1) + T(n / 2) + 2
次に、n - 4 項を展開します。これを行うと
T(n - 6) + T(n / 2 - 2) + T(n / 2 - 1) + T(n / 2) + 3
減算項 (T(n - 2k) の形式の項) を展開するプロセスを何度も繰り返すことができます。では、n - 2k が約 n / 2 になる点まで展開するとどうなるでしょうか? それは約n / 4回起こります。これを行うと、それが得られます
T(n) = T(n / 2) + T(n / 2) + T(n / 2 - 1) + T(n / 2 - 2) + ... + T(n / 2 - n / 4 ) + n / 4
T(n) は非減少であると仮定します。これを行うと、それが得られます
T(n) ≤ T(n / 2) + T(n / 2) + T(n / 2) + ... + T(n / 2) + n / 4
T(n) ≤ (n / 4 + 1) T(n / 2) + n / 4
ここで数学を少し大まかにして、別の単純化を行います。T(n / 2) の係数を (n / 4 + 1) にする代わりに、n / にするだけです。 4. これが安全ではないことは承知していますが、結果をそれほど混乱させることはないと推測します。ただし、それを行った後も残りの部分がまだ機能することを再確認することをお勧めします!
これは、上記の再帰を（大まかに）単純化して、それを得ることができることを意味します
T(n) ≤ (n / 4) T(n / 2) + n / 4
これは非常に扱いやすく、直接解決を試みることができます。反復法を使用し、パターンを見つけるまで何度も何度もそれ自体にプラグインし続けます。これを行うと、次のパターンが表示されます。
T(n) ≤ (n / 4) T(n / 2) + n / 4
≤ (n / 4)((n / 8) T(n / 4) + n / 8) + n / 4
= (n 2 / 32) T(n / 4) + n / 4 + n 2 / 32
≤ (n 2 / 32) ((n / 16) T(n / 8) + n / 16) + n / 4 + n 2 / 32
= (n 3 / 512) T(n / 8) + n / 4 + n 2 / 32 + n 3 / 512
≤ (n 3 / 512) ((n / 32) T(n / 16) + n / 32) + n / 4 + n 2 / 32 + n 3 / 512
= (n 4 / 16384) T(n / 16) + n / 4 + n 2 / 32 + n 3 / 512 + n 4 / 16384
出現するパターンを見てみましょう。これを k 回実行すると、T(n / 2 k ) の係数は n kを 2 のべき乗で割った値になります。これまでのところ、これらの 2 のべき乗は 4、32、512、16384 です。これらの数値には明確なパターンはないように見えますが、2 2、2 5、2 9、2 14と書き直すと、0、2、5、9、14、... のパターンに従っていることがわかります。これは、三角数 1, 3, 6, 10, 15, ... より 1 少ない数です。これは偶然ではありません. したがって、k回の反復後の分母は次の式で与えられると予想されます。
2 (k + 1)(k + 2) / 2 - 1
それを行った後、残りの項は、さまざまな三角数に累乗された 2 の累乗で除算された n のべき乗の合計です。したがって、物事を k 回展開すると、次のようになります。
T(n) ≤ (n k / 2 (k + 1)(k + 2) / 2 - 1 ) T(n / 2 k ) + Σ i = 0 k (n i / 2 (i + 1)(i + 2) / 2 - 1 )
わかった！それは混乱ですが、それほど悪いことではありません。n / 2 k = 1 になるとすぐに再帰が停止することがわかっています。これは、k = lg n のときに発生します。もう少し簡単にするために、基本ケースを変更して、n / 2 k = 2 のときに再帰が停止するようにします。これは、k = lg n - 1 のときに発生します。これにより、定数以上の変化はありません。要素。したがって、上記の式に k = lg n - 1 を代入すると、単純化して上限の閉じた形式の式を得ることができます。これを行うと、次のようになります。
T(n) ≤ (n k / 2 (k + 1)(k + 2) / 2 - 1 ) T(n / 2 k ) + Σ i = 0 k (n i / 2 (i + 1)(i + 2) / 2 - 1 )
= (n lg n - 1 / 2 (lg n)(lg n + 1) / 2 - 1 ) T(2) + Σ i = 0 lg n - 1 (n i / 2 (i + 1)(i + 2) / 2 - 1 )
うーん、それはきれいではありません。しかし、見た目ほど悪くはありません。第 1 項の分母を見てみましょう。
2 (lg n)(lg n + 1) / 2 - 1
指数の基本法則を使用すると、
2 (lg n)(lg n + 1) / 2 - 1
= (2 lg n ) (lg n + 1) / 2 - 1
= n (lg n + 1) / 2 - 1
それはそれほど悪くありません！したがって、次の式を使用すると、
n lg n - 1 / 2 (lg n)(lg n + 1) / 2 - 1
次のように単純化されることがわかります。
n lg n - 1 / 2 (lg n)(lg n + 1) / 2 - 1
= n lg n - 1 / n (lg n + 1) / 2 - 1
= n (lg n - 1 - ((lg n + 1) / 2 - 1))
= n (lg n - (lg n + 1) / 2)
= n (2 lg n - lg n - 1) / 2)
= n (lg n - 1) / 2)
= n O(lg n)
気の利いた！その先頭の項は、最終的に n O(lg n)の形式になります。
残りはどうですか？さて、私たちはこのひどい総和に対処する必要があります:
Σ i = 0 lg n - 1 (n i / 2 (i + 1)(i + 2) / 2 - 1 )
幸いなことに、注意できることの 1 つは、
ニ/ 2 (私+ 1)(私 + 2) / 2 - 1
≤ n i / 2 (i + 1)(i + 2)
≤ n i / 2 (i + 1)
≤ n i / 2 i
= (n / 2)私
したがって、合計の上限を設定したいだけであれば、このはるかに単純な合計を使用してそれを行うことができます。
Σ i = 0 lg n - 1 (n / 2) i
n / 2 > 0 であるため、この合計の上限は次のようになります。
Σ i = 0 lg n - 1 (n / 2) lg n - 1
= (lg n)(n lg n - 1 ) / (2 lg n - 1 )
= (2 lg n)(n lg n - 1 ) / n
= (2 lg n)n lg n - 2
= n O(lg n)
そしてビンゴ、そのひどい合計の第 2 項も n O(lg n)です! これは、T(n) = n O(log n)であることを意味します。この境界は必ずしも厳密ではありませんが、 n O(log n)はどの指数関数よりもゆっくりと成長するため、再帰が間違いなく準指数関数的であることを示しています。
お役に立てれば！
于 2013-09-18T07:39:35.857 に答える
0
于 2013-09-17T17:49:49.793 に答える
-1
指数関数的だと思います。なんで？すべての f(n) は、f(n/2) と f(n-2) の呼び出しにつながります。
詳細については、この質問を確認してください。
これがフィボナッチ順序の複雑さです。関数構造は似ています。
于 2013-09-17T17:25:44.857 に答える