7

私は再発の時間計算量を見つけようとしています:

T(n)= 2T(n 1/2)+ log n

私は解決策にかなり近づいていますが、障害にぶつかりました。私は解決する必要があります:

n (1/2 k = 1

kの場合、置換パターンを単純化します。私は再発に対する答えを探しているのではなく、ただの解決策を探していますk

4

4 に答える 4

7

再帰の展開を開始すると、次のようになります。 ここに画像の説明を入力してください


ここにいくつかの追加手順を加えた同じことがあります:

ここに画像の説明を入力してください

ここで、再帰の境界条件を使用すると(0と1として選択された番号2は意味がありません)、次のようになります。

ここに画像の説明を入力してください

方程式kに戻すと、次のようになります。

ここに画像の説明を入力してください

同じアイデアを使用する再帰がいくつかあります。

于 2015-12-15T07:04:58.737 に答える
3

解決することは不可能です

n (1/2 k = 1

kの場合、n> 1の場合、ゼロ以外のxの場合はnx>1ですこれを解決できる唯一の方法は、1/2 k = 0となるようにkを選択した場合ですが、それは不可能です。

ただし、これは解決できます。

n (1/2 k = 2

まず、両側のログを取ります。

( 1/2 k)lg n = lg 2 = 1

次に、両側に2kを掛けます。

lg n = 2 k

最後に、ログをもう一度取得します。

lg lg n = k

したがって、この再発はk = lglgnになると停止します。

kの値を求めただけですが、求めてから1年が経ちましたので、この問題を解決するために変数置換ができることを指摘したいと思います。k = 2nに設定してみてください。次に、k = lg nであるため、漸化式は次のようになります。

T(k)= 2T(k / 2)+ k

これは(マスター定理を使用して)T(k)=Θ(klog k)に解かれ、k = lg nであるという事実を使用して、全体的な繰り返しはΘ(log n log log n)に解かれます。

お役に立てれば!

于 2013-10-26T05:52:33.720 に答える
0

それが方程式だったクイックソートだったら男:

ここに画像の説明を入力してください

これに対する解決策はO(n*log(n))、今ではさらに小さくなっているため(T(n) ~ n^1/2N、複雑さが。未満であることを意味しますO(n*log(n))

あなたの限界を証明するために誘導を使用してみてください

于 2012-10-27T20:34:56.787 に答える
0

1の対数ベースは0です。

それで

n ^((1/2)^ k)= 1

log(n)(n ^((1/2)^ k))= log(n)(1)

1/2 ^ k = 0

log(1/2)((1/2)^ k)= log(1/2)(0)

対数基数0は、負の無限大です。

k=-無限大。

nには、1とだけ言うのではなく、別の「最終番号」を使用する必要があると思います...

于 2012-10-27T20:52:25.073 に答える