algorithm - 展开递推关系并寻找闭式

Question

我有一段算法，必须找到最坏情况的递归并找到它的封闭形式。到目前为止，我有最坏情况的复发:

T(n)= 2T(n/4) + C for n > 1.

我尝试展开它，目前我有这个表格:

T(n) = 2^kT(n/4^k) + Ck

k = log₄(n) 或 k = (log₂(n))/2。

我有 T(1) = 1000。

我不知道下一步该做什么，或者如何准确地找到它的封闭形式。我仍然看不到算法中的模式或我对 T(n) 的扩展。任何见解都会很棒，谢谢。

Answer 1

当n = 4^k时，你可以得到一个封闭的公式:

T(4^k) = 2^k x 10^3 + C + 2C + ... + 2^(k-1)C
       = 2^k x 10^3 + (2^k - 1)C

其中最后一个等式来自几何级数公式。

对于所有其他 n，我认为你能做的最好的就是应用 master theorem

您的等式符合定理的情况 1(您有 a = 2、b = 4、c = 0)。因此:

log_b(a) = 1 / 2

和

T(n) = O(sqrt(n))

我不确定它是否接受唯一的封闭形式。