尋找主定理的拉姆達

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)。它是否正確？我怎樣才能找到這個lambda？

Answer 1

常量lambda 是重要的是：它的目的是爲了避免考慮情況1和情況2之間的奇怪情況。由於big-O僅是上限而不是下限，所以較小的lambda選擇是「更好」，因爲它們涵蓋更多功能。由於拉姆達必須是積極的，但是，沒有「最好的」選擇拉姆達。 Lambda = 10^-3應該讓你通過足夠多的例子來看看爲什麼大多數主定理的處理不會選擇lambda生產。

Answer 2

F（N）= LOGN

小量可以是1/4，因爲

Ñ^{（日誌 _b一個基-ε-）} = N ^{（日誌 2-1/4 ）} = n ^{（1/2-1/4）} = n ^（1/4）。

f（n）= 0（n ^（1/4））。

所以由主定理T（N）= Θ（N ^{日誌 _b一個}）= Θ（N ^（1/2））的殼體1。