我知道它可以用主方法解决，但如何解决？请帮忙 ？
问问题
860 次
2 回答
0
Ralf 告诉您不能应用 masters theorem是不正确的。
这里唯一的限制是a >=1and b >= 1, a, b 可以是无理数，而 f(n) 可以是任何东西。
Log2(sqrt(2)) is 1/2，这使您处于第一种情况，您的解决方案是O(n^0.5)。
于 2016-01-31T07:06:58.223 回答
0
我不确定这是否正确：
a = sqrt(2)
b = 2
f(n) = log n
log(b) a = log (2) sqrt(2) = 1/2
log n in O[n^(1/2)]
所以找到一个数 n 的对数的运行时间是 O{n^(1/2)} （但是这里不能应用主定理）
解决方案在以下线程中：用 log n 求解主定理：T(n) = 2T(n/4) + log n
总体而言，我们看到您的复发是 O(n1/2) 和 Ω(n1/2)，通过更大和更小的复发来确定您的复发的上限和下限。因此，即使主定理在这里不适用，您仍然可以使用主定理声称运行时间将为 Θ(n1/2)。
通常，f(n) 必须是多项式才能应用主定理 - 它不适用于所有函数。然而，主定理有一个有限的“第四种情况”，它允许它应用于多对数函数。
于 2016-01-22T18:40:49.693 回答