algorithm - T（n）= 2T（n / 2）+ n lg lg nの漸近的な上限と下限は何ですか？

Question

漸化式

T（n）= 2T（n / 2）+ n lg lg n

（lgは2を底とする対数です）マスター定理を使用して解くことができますが、答えについてはよくわかりません。私は自分の答えを見つけましたが、情報のカスケードを防ぐためにここでは言及していません。上記の大きなOとΩを見つけるのを手伝ってください。

Answer 1

マスター定理の3つのケースのいずれも適用されません

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

（任意のベースで、それは実際には重要ではありません）

ケース1：f（n）= n log（log n）はnよりも「大きい」^{log2 2} = n ¹

^{ケース2：f（n）がn log k}（n）に適合しない

^{ケース3：f（n）がn 1+e}よりも小さい

U(n)=2 U(n/2) + n log n
L(n)=2 L(n/2) + n

あなたはそれを示すことができます：U(n) >= T(n)そしてL(n) <= T(n)。したがって、Uは上限を与え、LはTの下限を与えます。

U（n）にマスター定理を適用すると、次のようになります。

ケース2：f（n）= n log n =Θ（n1 ^log 1 ⁿ）したがって、U（n）=Θ（nlog ² n）

L（n）にマスター定理を適用すると、次のようになります。

ケース2：f（n）= n =Θ（n1 ^log 0 ⁿ）したがって、L（n）=Θ（nlog n）

したがってL(n)<=T(n)<=U(n)、T（n）= O（n log ² n）およびT（n）=Ω（nlog n）

_{また、O（log 2} n）= O（（log n）/ log 2）= O（（log n）* c）= O（log n）であることに注意してください。