1

さまざまな数値を保持する正方形の領域がある場合、各再帰関係の結果はどうなりますか?:

T(n) = 3T(n/2) + c および T(n) = 2T(n/2) + cn

最初の結果がクアッド パーティションになり、2 番目のパーティションがバイナリ パーティションになることはわかっていますが、なぜそうなのかを直感的に理解することはできません。最初のケースで 3 回、2 番目のケースで 2 回の再帰呼び出しを行っているのはなぜですか? +c または +cn が、問題に対して行っていることに影響するのはなぜですか?

4

1 に答える 1

1

これがあなたが探しているものだと思います

http://leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html

あなたの質問が再帰の説明に関するものである場合は、再帰ツリーとマスターメソッドを使用した再帰の解決について読むことをお勧めします

http://courses.csail.mit.edu/6.006/spring11/rec/rec08.pdf

2回目の再発とその方法について説明します。基本的に、高さ (lgn) と各レベルのコストが n に等しい再帰ツリーが作成されます。

最初のものでは、再帰ツリーの実行時間はツリー内のノード数のオーダーになります。高さは lgn のままですが、各レベルのコストは 3^h * c です。これを合計すると、複雑さが得られます

于 2013-02-27T22:03:40.633 に答える