再帰ツリーを使用して、指定された再帰を解決しようとしています。T(n) = 3T(n/3) + n/lg n.
最初のレベルで(n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3))。
2番目のレベルでは、であることがわかりますn/(log(n/9))。
上記の方程式を次の形式で一般化できますか？n.loglogn
これは私が持っている一般的な疑問です、私はこれについての洞察が必要です。
注：Theta(n^k log^k (n))その関数kに含まれている必要のある関数は、>=1である必要があります。そしてこの場合、kは-1であるため、マスター定理は思い浮かびません。
確かに、マスター定理は適用されません。
T（n）= 3T（n / 3）+ n/logn。
g（n）= T（n）/nとします。
次に、n g（n）= 3（n / 3）* g（n / 3）+ n/logn。
したがって
g（n）= g（n / 3）+ 1 /logn。
これにより、g（n）= Sum 1 / log n + 1 / log n / 3 + 1 / log n / 9+..が得られます。
= Theta（Sum 1 / logn + 1 /（logn -1）+ 1 /（log n-2）+ ...）= Theta（Integral 1 / x between 1 and logn）= Theta（log log n）。
したがって、T（n）= n g（n）= Theta（n log logn。）
あなたはそれを正しく推測しました。
ツリーを使用して質問を視覚化すると、各ランクの合計が次のようになります。
（これはn / log（n）に等しい）-ランク1：
など、各ランクの一般的な合計でn/log(n/(3^i))、iが現在のランクになります。だから、すべて一緒に私たちは得ます：
方程式を開くと、次のようになります。
（最後から始めて逆方向に進みます。最初にi = log（base3）nの場合、次に戻ります）
シータでは対数ベースは重要ではないので、次のようになります。
これは：
これは（シグマで）：
これは調和級数であり、次のようになります。
lnはeを底とする対数であり、ログの底はシータでは重要ではないため、最終的に次のようになります。
これは次のようになります。
つまり、theta（n log log n）です。
T(n)=3T(⌊n3⌋)+2nlogn基本条件1の場合、n<=1
置換方法による場合：
回答ページ1
回答ページ2
