用Master定理计算算法的渐近时间复杂度
Using Master theorem to calculate asymptotic time complexity of algorithm
问题：您有一个算法将 n 大小问题划分为 六个子问题，大小为 四分之一的原文。划分算法使 100 步 并合并 75n。算法的时间渐近复杂度是多少？
所以大师定理的公式
而对于这个问题a = 6和b = 4，但我不知道在哪里适合划分和合并信息。
可接受的结果是：
O(n1.2924), omega(n1.2) 和 O(1.001n)
每解决一个子问题，就必须将当前实例分成更多的子问题（成本=100步）。然后，您必须合并子问题的结果（成本 = 75n 步）。
意思是f(n) = 75n + 100，因为f(n)表示解决单个子问题的代价（不包括递归的代价）。
f(n) = 75n + 100 是 O(n).
因此，您正在查看：T(n) = 6 * T(n/4) + O(n)
我们知道：
a = 6
b = 4
f(n) = 75n + 100
接下来，我们计算log_b(a) = log_4(6) = log(6)/log(4) = 1.2924...
让我们考虑主定理的情形 I：
如果 f(n) = O(n^c) 其中 c < log_b(a)，则 T(n) = Ө(n^(log_b(a))。
我们知道f(n) = O(n^1)，所以让我们试试c = 1。
是c < log_b(a)吗？嗯，1 < 1.2924...，是的。
因此，T(n) = Ө(n^(log_b(a)) => T(n) = Ө(n^1.2924...).
问题：您有一个算法将 n 大小问题划分为 六个子问题，大小为 四分之一的原文。划分算法使 100 步 并合并 75n。算法的时间渐近复杂度是多少？
所以大师定理的公式
而对于这个问题a = 6和b = 4，但我不知道在哪里适合划分和合并信息。
可接受的结果是： O(n1.2924), omega(n1.2) 和 O(1.001n)
每解决一个子问题，就必须将当前实例分成更多的子问题（成本=100步）。然后，您必须合并子问题的结果（成本 = 75n 步）。
意思是f(n) = 75n + 100，因为f(n)表示解决单个子问题的代价（不包括递归的代价）。
f(n) = 75n + 100 是 O(n).
因此，您正在查看：T(n) = 6 * T(n/4) + O(n)
我们知道：
a = 6
b = 4
f(n) = 75n + 100
接下来，我们计算log_b(a) = log_4(6) = log(6)/log(4) = 1.2924...
让我们考虑主定理的情形 I：
如果 f(n) = O(n^c) 其中 c < log_b(a)，则 T(n) = Ө(n^(log_b(a))。
我们知道f(n) = O(n^1)，所以让我们试试c = 1。
是c < log_b(a)吗？嗯，1 < 1.2924...，是的。
因此，T(n) = Ө(n^(log_b(a)) => T(n) = Ө(n^1.2924...).