我目前正在尝试解决与主定理的这种关系：
T(n) = 2T(n/4) + log n
我已经计算出 a = 2 和 b = 4，但我对 log n 感到困惑。
我的脚本说：c(n)（这里是 log n）是 Big O(n^d) 的元素。
如果我能在这里算出我的 d，我会比较 a 和 b^d 来找出我的主定理案例。
但是，由于它在这里是 log n，我不确定它的 Big O 表示法。
我的意思是我可能会说它是 O(n 1/2 ) 的元素，然后会导致情况二，其中 a 和 b^d 相同，但它也是 O(n 1 ) 的元素，然后是又是一个案例。
一个有用的事实是，对于任何 ε > 0，我们知道
日志 n = O(n ε )。
我们也知道
日志 n = Ω(1)
让我们看看这是否告诉我们什么。我们知道，对于任何 ε > 0，您的递归都受此限制：
S(n) = 2S(n / 4) + n ε
让我们在这里使用主定理。我们有 a = 2、b = 4 和 d = ε。我们需要推理 log b a = log 4 2 = 1/2 以及它与 d = ε 的关系。让 ε 变小 - 比如说，让我们选择 ε = 0.000001。然后我们有 log b a < d，所以主定理说运行时将是
O(n log b a ) = O(n 1/2 )。
接下来，考虑这个递归关系：
R(n) = 2R(n / 4) + 1
此重复周期会降低您的重复周期。使用主定理告诉我们，R(n) = Ω(n 1/2 ) 也是如此。
总体而言，我们看到您的复发是 O(n 1/2 ) 和 Ω(n 1/2 )，通过更大和更小的复发来确定您的复发的上限和下限。因此，即使主定理在这里不适用，您仍然可以使用主定理声称运行时间将为 Θ(n 1/2 )。
希望这可以帮助！