0

私はいくつかのアルゴリズムを調べており、方程式を作成するときに複数の再帰的ステップがどのように扱われるかを確認しようとしています。

したがって、展示A： 展示物A

ここでの漸化式は次のとおりです。T（n）= c + 2T（n / 2）これは大きなO表記ではO（n）に簡略化されます。

ただし、ここでも展示物B同様のことが起こっており、最初の呼び出しと同じように2つの再帰呼び出しがあるため、再帰方程式T（n）= n + 2T（n / 2）が得られます。これは、大きなO表記ではOに簡略化されます。 （n）ただし、ここではそうではありません。ここにあるこの2番目の方程式で正しい漸化式を取得する方法に関する入力はありますか？

これを解決する方法についての入力は素晴らしいでしょう。

4

1 に答える 1

2

あなたはマスター定理に興味があるかもしれません：

http://en.wikipedia.org/wiki/Master_theorem

漸化式T(n) = n + 2T(n/2)はTheta(n log n)であり、定理を使用して導出できます。手動で行うには、次のことを想定n = 2^kして実行することもできます。

T(n) = 2T(n/2) + n
     = 2(2T(n/4) + n/2) + n
     = (2^2)T(n/(2^2)) + 2n
     = (2^2)(2T(n/(2^3)) + n/(2^2)) + 2n
     = (2^3)T(n/(2^3)) + 3n
     = ...
     = (2^k)T(n/(2^k)) + kn
     = nT(1) + n log2 n
     = Theta(n log n)
于 2012-12-21T03:37:31.980 に答える