程序递归关系的求解

Question

我有一个小测验，要求我解决一个程序的递推关系：

算法所用的时间 T(n) 通常是大小的函数， n，输入数据。假设您编写了一个显示以下时间递归的程序：

T(n) = T(n/2) + a , if n > 1

T(n) = b, if n= 1

这是我尝试过的：

T(n/2) = T(n/4) + a T(n/4) = T(n/8) + a

所以：

T(n) = T(n/4) + 2*a = T(n/8) + 3*a = T(n/K) + 3*a

到这里为止，我想使程序应该终止的 T(n) = 1，所以我使

n/K = 1 -> K = n

我得到：

T(n/n) + 3*a = b + 3a

但是答案显示该程序具有对数复杂度，解决方案应为 T(n) = a ∗ log2(n) + b

我不明白如何得到上述解决方案，谁能帮助我？谢谢！

Answer 1

这样想。在每次迭代中，您将问题大小 n 减半：从 n 到 n/2 到 n/4 等等。你可以想象一个 "tree"，通常你有一个像 T(n) = a * T(n/b) + f(n) 这样的公式然后在你的树中每个节点都有度 a 和问题大小在每个节点除以 b。在您的情况下，树在每个级别都有一半的问题大小，但树节点的程度保持为一。

n/2: a
     \
n/4:  a
      \
n/8:   a
       \
        ...
        \
n/n:     b + a

我假设您知道这棵树有多深，以及如何达到您描述为解决方案的给定复杂性。

另一种看待它的方式，更接近于您的具体练习：在每次迭代中添加一个 a 对吗？您多久添加一次这样的 a？

程序递归关系的求解

solution of recurrence relations of a program

recurrence

time-complexity