algorithm - 无法弄清楚这种重复的复杂性

Question

我稍微更新了 Master Theorem，我试图通过递归解决 2 个大小为 n 的子问题来计算解决大小为 n 的问题的算法的运行时间- 1 并在常数时间内组合解决方案。
所以公式是:
T(N) = 2T(N - 1) + O(1)
但是我不确定如何制定主定理的条件。
我的意思是我们没有 T(N/b) 因此在这种情况下主定理公式的 b b=N/(N-1) ?
如果是，显然 a > b^k 因为 k=0 并且是 O(N^z) 其中 z=log2 的基数为 (N/N-1) 我怎么理解这个？假设到目前为止我是对的？

Answer 1

啊，提示够多了。解决方案其实很简单。对两边进行 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 = - a c/(1-a)

此外，观察

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

其中 P(z) = r z/(z-1) = r/(1 - (1/z)), Q(z) = s z/(z-a) = s/(1 - a (1/z))

应用反向 z 变换得到:

    p[n] = r u[n] 

和

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

其中 log 表示自然对数，u[n] 是单位(Heaviside)阶跃函数(即 u[n]=1 表示 n>=0，u[n]=0 表示 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。

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