我需要找到涉及递归的算法的复杂性:
T(n) = T(n-1) + ... + T(1) + 1
T(n)
是解决尺寸问题所需要的时间n
。
主方法不适用于此处,我无法猜测使用替代方法(无论如何我都不想使用替代方法)。我剩下的是递归树方法。
由于每个节点的子节点数量不是一个常数,因此我很难跟踪每个节点的贡献量。潜在的模式是什么?
我知道我必须找到树中的节点数,其中每个节点(k
)的子节点都有从1到编号的所有节点k-1
。
T(n)
给定该公式也可以找到确切的时间吗?
自从 T(n-1) = T(n-2) + ... + T(1) + 1
T(n) = T(n-1) + T(n-2) + ... + T(1) + 1
= T(n-1) + T(n-1)
= 2*T(n-1)
和T(1) = 1
=>T(n) = 2^(n-1)
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句