我 N 通过递归解决2子问题上的主定理刷新了一下，我试图找出一种算法，解决了大小的问题的运行时间尺寸 N-1 并在固定时间内结合的解决方案。照片 因此，计算公式为： T（N）= 2T（N - 1）+ O（1） 但我不知道我该怎么制定主定理的条件。 我的意思是，我们没有 T（N / B）所以 B 在这种情况下，主定理公式 B = N /（N-1）？ 如果是的话，因为很明显 A＆GT; b ^氏/ code>，因为 K = 0 是 O（N ^ Z），其中 Z = LOG2 与（N / N-1）如何有意义出来呢？假设我是对的那么远？

I am refreshing on Master Theorem a bit and I am trying to figure out the running time of an algorithm that solves a problem of size n by recursively solving 2 subproblems of size n-1 and combine solutions in constant time. So the formula is: T(N) = 2T(N - 1) + O(1) But I am not sure how can I formulate the condition of master theorem. I mean we don't have T(N/b) so is b of the Master Theorem formula in this case b=N/(N-1)? If yes since obviously a > b^k since k=0 and is O(N^z) where z=log2 with base of (N/N-1) how can I make sense out of this? Assuming I am right so far?

推荐答案

啊，足够的提示。解决的办法其实很简单。 Z变换两侧，集团的条款，然后逆Z变换得到解决。

ah, enough with the hints. the solution is actually quite simple. z-transform both sides, group the terms, and then inverse z transform to get the solution.

首先，看问题，

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

适用Z变换双方（有一些技术性相对于中华民国，但让我们忽略现在）

apply z transform to both sides (there are some technicalities with respect to the ROC, but let's ignore that for now)

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

解X（z）取得

solve for X(z) to get

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

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

now observe that this formula can be re-written as:

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

其中r = C /（1-a）和S = - 一个C /（1-a）的

where r = c/(1-a) and s = - a c / (1-a)

此外，观察到

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

其中，P（z）的= RZ /（Z-1）= R /（1 - （1 / Z）），和Q（z）的= SZ /（ZA）= S /（1 - 一个（1 / Z））

where P(z) = r z / (z-1) = r / (1 - (1/z)), and 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]是单元（希维赛德）阶跃函数（即U [η] = 1对于n> = 0和u [η] = 0对于n℃下）。

where log denotes the natural log and u[n] is the unit (Heaviside) step function (i.e. u[n]=1 for n>=0 and u[n]=0 for n<0).

最后，通过线性Z变换：

Finally, by linearity of z-transform:

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

其中r和s如上所定义

where r and s are as defined above.

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

so relabeling back to your original problem,

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

然后

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

其中，EXP（X）= E ^ X，日志（x）是x的自然对数，和u [n]是单位阶跃函数。

where exp(x) = e^x, log(x) is the natural log of x, and u[n] is the unit step function.

这是什么告诉你吗？

除非我犯了一个错误，T指数与正增长。这是有效的合理假设，即一个> 1的指数是由一个（更具体地，自然对数）管辖下的指数递增函数。

Unless I made a mistake, T grows exponentially with n. This is effectively an exponentially increasing function under the reasonable assumption that a > 1. The exponent is govern by a (more specifically, the natural log of a).

一更简化，注意，实验值（日志（a）将正）= EXP（日志（一））^ N = A ^ n为

One more simplification, note that exp(log(a) n) = exp(log(a))^n = a^n:

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

所以O（一^ N）的大O符号。

so O(a^n) in big O notation.

喏，这就是最简单的方式：

把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
    ....

请注意，这将创建一个模式。具体做法是：

note that this creates a pattern. specifically:

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

把C = 1给出了

put c = 1 gives

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

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

this is geometric series, which evaluates to:

    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。

for n>=0.

请注意，这个公式是与上述相同的C = 1给出使用z变换方法。此外，O（一^ N）。

Note that this formula is the same as given above for c=1 using the z-transform method. Again, O(a^n).