如何将递归定义的输入大小函数转换为问题输入大小的直接函数？

Question

假设我有一个算法,它对大小为n的输入进行操作,我知道n所需的时间是n-1所需时间的两倍.我可以在这个简单的情况下观察(假设n = 0需要1 秒),算法需要2 ⁿ秒.

是否有一种将递归定义的定义转换为更熟悉的直接表达式的通用方法？

Answer 1

硕士定理

特别是:

T(n)= aT(n/b)+ n ^c

如果log _b a <c,那么T(n)= O(n ^c)

如果log _b a = c,那么T(n)= O(n ^c log [n])

如果log _b a> c,那么T(n)= O(n ^{log _b a})

这是一个有用的定理,但不能完全回答你的问题.

你要找的是递归关系的生成函数.通常,这些仅在非常简单的情况下是可解的,即当f(n)= Af(n-1)+ Bf(n-1)和f(0)= f(1)= 1(或f(1)时= A).其他复发关系很难解决.

有关详细信息,请参阅线性递归关系.