用 log n 求解主定理：T(n) = 2T(n/4) + log n
Solving master theorem with log n: T(n) = 2T(n/4) + log n
我目前正在尝试用主定理解决这个关系：
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，我不确定它的大 O 表示法。
我的意思是我可能会说它是 O(n1/2) 的元素，这将导致情况二，其中 a 和 b^d 相同，但它也是 O(n1) 的元素，这又是另一种情况。
一个有用的事实是，对于任何 ε > 0，我们知道
log n = O(nε).
我们也知道
log n = Ω(1)
让我们看看这是否能告诉我们任何信息。我们知道，对于任何 ε > 0：
，您的递归受此递归的限制
S(n) = 2S(n / 4) + nε
让我们在这里使用主定理。我们有 a = 2、b = 4 和 d = ε。我们需要推理 logb a = log4 2 = 1/2 以及它与 d = ε 的关系。让我们把 ε 变小——比如说，让我们选择 ε = 0.000001。然后我们有 logb a < d，所以主定理说运行时间是
O(nlogb a) = O(n1/2).
接下来，考虑这个递归关系：
R(n) = 2R(n / 4) + 1
此重复频率降低了您的重复频率。使用主定理也告诉我们 R(n) = Ω(n1/2)。
总的来说，我们看到你的复发是 O(n1/2) 和 Ω(n1/2) by upper - 并通过更大和更小的重复来降低你的重复。因此，即使主定理在这里不适用，您仍然可以使用主定理声称运行时间将为 Θ(n1/2).
希望对您有所帮助！
我目前正在尝试用主定理解决这个关系：
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，我不确定它的大 O 表示法。
我的意思是我可能会说它是 O(n1/2) 的元素，这将导致情况二，其中 a 和 b^d 相同，但它也是 O(n1) 的元素，这又是另一种情况。
一个有用的事实是，对于任何 ε > 0，我们知道
log n = O(nε).
我们也知道
log n = Ω(1)
让我们看看这是否能告诉我们任何信息。我们知道，对于任何 ε > 0：
，您的递归受此递归的限制S(n) = 2S(n / 4) + nε
让我们在这里使用主定理。我们有 a = 2、b = 4 和 d = ε。我们需要推理 logb a = log4 2 = 1/2 以及它与 d = ε 的关系。让我们把 ε 变小——比如说，让我们选择 ε = 0.000001。然后我们有 logb a < d，所以主定理说运行时间是
O(nlogb a) = O(n1/2).
接下来，考虑这个递归关系：
R(n) = 2R(n / 4) + 1
此重复频率降低了您的重复频率。使用主定理也告诉我们 R(n) = Ω(n1/2)。
总的来说，我们看到你的复发是 O(n1/2) 和 Ω(n1/2) by upper - 并通过更大和更小的重复来降低你的重复。因此，即使主定理在这里不适用，您仍然可以使用主定理声称运行时间将为 Θ(n1/2).
希望对您有所帮助！