递归关系问题
Recurrence relation problems
我在一次测试中有以下递归关系，但我弄错了，我不知道为什么。
1. T(n) = 2T(n/4) + O(n^0.5)
使用机器翻译：a = 2, b = 4, f(n) = n^0.5
将 n^(log_4(2)) 与 n^0.5 进行比较 => n^0.5 == n^0.5
因此，情况 3：Θ(n log n)
显然是错误的，不知道为什么。
2. T(n) = 3T(n/4) + O(n^0.75)
使用机器翻译：a = 3, b = 4, f(n) = n^0.75
比较 n^(log_4(3)) 和 n^0.75
因此，情况 1： Θ(n^log_4(3))
3. T(n) = T(n/2) + T(n/3) + O(n log n)
这不是一种可以用 MT 解决的形式，我无法在没有帮助的情况下轻易找到 p 值。因此，我在黑暗中刺了一刀，结果错了。不知道从哪里开始。
4. T(n) = 2T(n/2) + n log n
使用 MT：a = 2，b = 2，f(n) = n log n
比较 n^log_2(2) 到 n log n => n^1 到 n log n
情况 2：Θ(n log n)
您可能误读或遗漏了大师定理的一些细节。会参考Wikipedia article.
1)
第二种情况说明：
由于c_crit = 0.5和k = 0，最终的复杂度为：
您只是漏掉了前面 n 的指数。
2)
This is correct.
4)
您在这里遗漏了另一个细节：k = 1，需要有一个额外的因素 log n:
3)
这有点棘手。使用 Akra-Bazzi method:
要求解指数 p，只需在计算器上使用 Newton-Raphson - 得出 p = 0.787885...。分部进行积分：
代入：
我在一次测试中有以下递归关系，但我弄错了，我不知道为什么。
1. T(n) = 2T(n/4) + O(n^0.5)
使用机器翻译：a = 2, b = 4, f(n) = n^0.5
将 n^(log_4(2)) 与 n^0.5 进行比较 => n^0.5 == n^0.5
因此，情况 3：Θ(n log n)
显然是错误的，不知道为什么。
2. T(n) = 3T(n/4) + O(n^0.75)
使用机器翻译：a = 3, b = 4, f(n) = n^0.75
比较 n^(log_4(3)) 和 n^0.75
因此，情况 1： Θ(n^log_4(3))
3. T(n) = T(n/2) + T(n/3) + O(n log n)
这不是一种可以用 MT 解决的形式，我无法在没有帮助的情况下轻易找到 p 值。因此，我在黑暗中刺了一刀，结果错了。不知道从哪里开始。
4. T(n) = 2T(n/2) + n log n
使用 MT：a = 2，b = 2，f(n) = n log n
比较 n^log_2(2) 到 n log n => n^1 到 n log n
情况 2：Θ(n log n)
您可能误读或遗漏了大师定理的一些细节。会参考Wikipedia article.
1)
第二种情况说明：
由于c_crit = 0.5和k = 0，最终的复杂度为：
您只是漏掉了前面 n 的指数。
2)
This is correct.
4)
您在这里遗漏了另一个细节：k = 1，需要有一个额外的因素 log n:
3)
这有点棘手。使用 Akra-Bazzi method:
要求解指数 p，只需在计算器上使用 Newton-Raphson - 得出 p = 0.787885...。分部进行积分：
代入：