问题:您有一个算法,将n 个大小的问题划分为六个子问题,大小为原始问题的四分之一。对于划分算法进行100 步和合并75n。算法的时间渐近复杂度是多少?
所以主定理的公式
对于这个问题a = 6和b = 4,但我不知道在哪里适合划分和合并信息。
可接受的结果是: O ( n 1.2924 )、omega ( n 1.2 ) 和O (1.001 n )
问题:您有一个算法,将n 个大小的问题划分为六个子问题,大小为原始问题的四分之一。对于划分算法进行100 步和合并75n。算法的时间渐近复杂度是多少?
所以主定理的公式
对于这个问题a = 6和b = 4,但我不知道在哪里适合划分和合并信息。
可接受的结果是: O ( n 1.2924 )、omega ( n 1.2 ) 和O (1.001 n )
每次解决一个子问题时,都必须将当前实例划分为更多的子问题(成本 =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...)
。