問題解決復發T（n）= 4T（n/4）+ 3log n

Question

我真的對解決上述復發感到沮喪。我試圖通過使用主方法來解決它，但我只是沒有完成...

我有一個遞歸算法，需要3log n次（三個二進制搜索）問題，每個問題都有n/4的大小，然後單獨解決，直到n小於輸入給定的某個常量。所以，我得到這個復發的結果：

T(n) = 4*T(n/4) + 3*log(n) 

Base-Case if n < c (c = some constant given by program input): 

T(n) = 1 

我試圖找到我的遞歸程序的漸近運行時間，並希望通過使用主定理來解決它。任何人都可以告訴我，如果有可能在這種再發生中使用主定理，並且如果是的話，那麼主定理是哪一種？

所有幫助表示讚賞，謝謝。

Answer 1

T(n) = O(n)，因爲4個鹼基對數的對數是1，而3 * log（n）是O(n^0.5)（0.5 < 1）。它對應於here描述的主定理的第一種情況。