algorithm - マスター定理のラムダを求める

Question

次のようなケースがあるとします

T(n)=2T(n/4)+log(n). a=2, b=4, f(n)=log(n)

これはケース 1 である必要がありますn^(1/2)>log(n)。ケース 1 にもラムダがありますf(n)=O(n^((1/2)-lambda)。これは正しいです？そして、どうすればこのラムダを見つけることができますか?

Answer 1

定数ラムダは重要です。その目的は、ケース1とケース2の間にある奇妙なケースを考慮しないようにすることです。big-Oは上限のみであり、下限ではないため、ラムダの選択肢が少ないほど、ある意味で「優れています」。彼らはより多くの機能をカバーしていること。ただし、ラムダは正でなければならないため、ラムダの「最良の」選択はありません。Lambda = 10 ^ -3は、マスター定理のほとんどの処理がラムダの選択から生成を行わない理由を理解するのに十分な例を示しているはずです。

Answer 2

f(n)=logn

Epsilon は 1/4 になる可能性があるため、

n ^{(log _b a-イプシロン)} =n ^{(log ₄ 2-1/4)} =n ^(1/2-1/4) =n ^(1/4) .

f(n)=O(n ^(1/4) )。

したがって、マスター定理のケース 1 により、T(n)=Θ(n ^{log _b a} )=Θ(n ^(1/2) ) となります。