私は再発の時間計算量を見つけようとしています:
T(n)= 2T(n 1/2)+ log n
私は解決策にかなり近づいていますが、障害にぶつかりました。私は解決する必要があります:
n (1/2 k) = 1
kの場合、置換パターンを単純化します。私は再発に対する答えを探しているのではなく、ただの解決策を探していますk
。
私は再発の時間計算量を見つけようとしています:
T(n)= 2T(n 1/2)+ log n
私は解決策にかなり近づいていますが、障害にぶつかりました。私は解決する必要があります:
n (1/2 k) = 1
kの場合、置換パターンを単純化します。私は再発に対する答えを探しているのではなく、ただの解決策を探していますk
。
解決することは不可能です
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)に解かれます。
お役に立てれば!
それが方程式だったクイックソートだったら男:
これに対する解決策はO(n*log(n))
、今ではさらに小さくなっているため(T(n) ~ n^1/2
)N
、複雑さが。未満であることを意味しますO(n*log(n))
。
あなたの限界を証明するために誘導を使用してみてください
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とだけ言うのではなく、別の「最終番号」を使用する必要があると思います...