1

そのため、1 つではなく 2 つの再帰呼び出しがあるケースに遭遇しました。私は 1 回の再帰呼び出しを解決する方法を知っていますが、この場合、私が正しいか間違っているかはわかりません。

次の問題があります。

T(n) = T(2n/5) + T(3n/5) + n

そして、これの最悪の場合の複雑さを見つける必要があります。（参考までに-これはある種の拡張マージソートです）

私の感覚では、定理の最初の方程式を使用するつもりでしたが、私の考えには何か問題があるように感じます。このような問題を解決する方法についての説明をいただければ幸いです:)

4

1 に答える 1

1

指定された再帰の再帰ツリーは次のようになります。

                                Size                        Cost

                                 n                           n
                               /   \
                             2n/5   3n/5                     n
                           /   \     /    \
                       4n/25  6n/25  6n/25  9n/25            n

                         and so on till size of input becomes 1

ルートからリーフへの longes 単純パスは、n-> 3/5n -> (3/5) ^2 n .. until 1 になります。

 Therefore  let us assume the height of tree = k

            ((3/5) ^ k )*n = 1 meaning  k = log to the base 5/3 of n

 In worst case we expect that every level gives a cost of  n and hence 

        Total Cost = n * (log to the base 5/3 of n)

 However we must keep one thing in mind that ,our tree is not complete and therefore

 some levels near the bottom would be partially complete.

 But in asymptotic analysis we ignore such intricate details.

 Hence in worst Case Cost = n * (log to the base 5/3 of n)

          which  is O( n * log n )

それでは、置換法を使用してこれを確認しましょう。

 T(n) =  O( n * log n)  iff T(n) < = dnlog(n) for some d>0

 Assuming this to be true:

 T(n) = T(2n/5) + T(3n/5) + n

      <= d(2n/5)log(2n/5) + d(3n/5)log(3n/5) + n

       = d*2n/5(log n  - log 5/2 )  + d*3n/5(log n  - log 5/3) + n

       = dnlog n  - d(2n/5)log 5/2 - d(3n/5)log 5/3  + n

       = dnlog n  - dn( 2/5(log 5/2)  -  3/5(log 5/3)) + n

       <= dnlog n

       as long as d >=  1/( 2/5(log 5/2)  -  3/5(log 5/3) )
于 2015-05-04T17:45:42.600 に答える