如何解决复发T（N）= T（N-1）+ ... T（1）1？ [英] How to solve the recurrence T(n)=T(n-1) + ... T(1) +1?

问题描述

我需要找到涉及复发的一个算法的复杂度：

I need to find the complexity of an algorithm that involves the recurrence:

T（N）= T（N-1）+ ... + T（1）+ 1

T（N）是需要解决规模的问题时 N 。

T(n) is the time it takes to solve a problem of size n.

主方法在这里并不适用，我不能做一个猜测使用替换法（我并不一定要使用替换法）。 我留下了递归树的方法。

The master method doesn't apply here and I can't make a guess to use the substitution method (I don't want to use the substitution method anyway). I'm left with recursion tree method.

由于每个节点的子节点的数目是不恒定的，我发现很难跟踪多少每个节点都贡献。潜在的模式是什么？

Since the number of children of each node isn't a constant, I'm finding it hard to keep track of how much each node contributes. What is the underlying pattern?

我明白，我必须找到一棵树，其中每个节点（ K ）有其子所有节点编号从1到<$ C的节点数$ C> K-1 。

I understand that I have to find the number of nodes in a tree in which each node (k) has for its children all nodes numbered from 1 to k-1.

时，也可​​能找到确切的时间 T（N）鉴于公式？

Is it also possible to find the exact time T(n) given that formula?

推荐答案

由于 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）

这篇关于如何解决复发T（N）= T（N-1）+ ... T（1）1？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！