4

我对 Master Theorem 有点耳目一新，我试图找出一种算法的运行时间，该算法n通过递归解决 2 个大小子问题n-1并在恒定时间内组合解决方案来解决大小问题。
所以公式是：
T(N) = 2T(N - 1) + O(1)
但我不确定如何制定主定理的条件。我的意思是在这种情况下
我们没有主定理公式吗？ 如果是的话，因为很明显，因为我在哪里可以理解这一点？假设我到目前为止是对的？T(N/b)bb=N/(N-1)
a > b^kk=0O(N^z)z=log2(N/N-1)

4

4 回答 4

3

啊，足够的提示。解决方案其实很简单。z 变换两边，对项进行分组，然后进行 z 逆变换得到解。

首先，将问题视为

    x[n] = a x[n-1] + c

对两边应用 z 变换（关于 ROC 有一些技术性问题，但我们暂时忽略它）

    X(z) = (a X(z) / z) + (c z / (z-1))

求解 X(z) 得到

    X(z) = c z^2 / [(z - 1) * (z-a)]

现在观察到这个公式可以重写为：

    X(z) = r z / (z-1) + s z / (z-a)

其中 r = c/(1-a) 和 s = - ac / (1-a)

此外，观察到

    X(z) = P(z) + Q(z)

其中 P(z) = rz / (z-1) = r / (1 - (1/z))，Q(z) = sz / (za) = s / (1 - a (1/z))

应用逆 z 变换得到：

    p[n] = r u[n]

和

    q[n] = s exp(log(a)n) u[n]

其中 log 表示自然对数，u[n] 是单位（Heaviside）阶跃函数（即，对于 n>=0，u[n]=1，对于 n<0，u[n]=0）。

最后，通过 z 变换的线性：

    x[n] = (r + s exp(log(a) n))u[n]

其中 r 和 s 如上定义。

所以重新标记回到你原来的问题，

    T(n) = a T(n-1) + c

然后

    T(n) = (c/(a-1))(-1+a exp(log(a) n))u[n]

其中exp(x) = e^x，log(x)是x的自然对数，u[n]是单位阶跃函数。

这告诉你什么？

除非我犯了错误，否则 T 会随着 n 呈指数增长。在 a > 1 的合理假设下，这实际上是一个指数增长的函数。指数由 a（更具体地说，a 的自然对数）控制。

另一种简化，注意 exp(log(a) n) = exp(log(a))^n = a^n：

    T(n) = (c/(a-1))(-1+a^(n+1))u[n]

所以 O(a^n) 在大 O 表示法中。

现在这是简单的方法：

把 T(0) = 1

    T(n) = a T(n-1) + c

    T(1) = a * T(0) + c = a + c
    T(2) = a * T(1) + c = a*a + a * c + c
    T(3) = a * T(2) + c = a*a*a + a * a * c + a * c + c
    ....

请注意，这会创建一个模式。具体来说：

    T(n) = sum(a^j c^(n-j), j=0,...,n)

把 c = 1 给

    T(n) = sum(a^j, j=0,...,n)

这是几何级数，其计算结果为：

    T(n) = (1-a^(n+1))/(1-a)
         = (1/(1-a)) - (1/(1-a)) a^n
         = (1/(a-1))(-1 + a^(n+1))

对于 n>=0。

请注意，此公式与上面给出的 c=1 使用 z 变换方法相同。再次，O(a^n)。

于 2013-01-20T12:18:56.270 回答
1

甚至不要考虑大师定理。只有当从一般形式 T(n) = aT(n/b) + f(n) 中得到 b > 1 时的 master 定理时，才能使用 Masther 定理。

相反，这样想。您有一个递归调用，它在每次递归调用时将输入的大小 n 减 1。并且在每次递归调用中，成本都是常数 O(1)。输入大小将递减，直到达到 1。然后将用于进行递归调用的所有成本相加。他们有几个人？n. 所以这需要 O(2^n)。

于 2013-01-20T12:01:30.100 回答
0

看起来你不能用主定理来表述这个问题。

一个好的开始是绘制递归树来理解模式，然后用替换方法证明它。您还可以将公式扩展几次，然后查看它的结果。

另请参阅解决 2 个子问题的问题，而不是a： Time bound for recursive algorithm with constant combination time

于 2013-01-20T11:44:31.313 回答
0

也许你可以这样想

什么时候

n = 1, T(1) = 1
n = 2, T(2) = 2
n = 3, T(3) = 4
n = 4, T(4) = 8
n = 5, T(5) = 16

不难看出这是一个几何级数1 + 2+ 4+ 8 + 16...，其和就是第一项(ratio^n - 1)/(ratio - 1)。对于这个系列是

1 * (2^n - 1)/(2 - 1) = 2^n - 1.

这里的主导词是2^n，因此函数属于Theta(2^n)。你可以通过做一个来验证它lim(n->inf) [2^n / (2^n - 1)] = +ve constant.

因此函数属于Big Theta (2^n)

于 2013-01-27T01:14:33.730 回答