algorithm - 使用Master定理计算算法的渐近时间复杂度

Question

问题：你有一个算法，把n个大小的问题分成6个子问题，大小是原来问题的四分之一。该算法分为100步和合并算法，算法的时间渐近复杂度是多少？
所以主定理的公式
对于这个问题，a=6和b=4，但我不知道在哪里适合划分和合并信息。
可接受的结果是：
O（n1.2924）、欧米茄（n1.2）和O（1.001N）

Answer 1

每次解决子问题时，都必须将当前实例划分为更多的子问题（cost=100步骤）。然后，必须合并子问题的结果（cost=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...
让我们考虑主定理的情形一：
如果 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...)。