时间开往递归算法恒定组合时间 [英] Time bound for recursive algorithm with constant combination time

问题描述

假设我有一个递归算法，简单地将输入到2个输入大小为n-1，解决了他们的递归。它结合的结果一定时间内例如c。

Suppose I have a recursive algorithm that splits input into 2 inputs of size n-1 and solves them recursively. It combines the results in a constant time say c.

所以，制定一个公式对于这一点，

So formulating an equation for this,

T（N）= 2T（N-1）+ C

T(n) = 2T(n-1) + c

为了找到这一个的复杂性，我用递归树方法。因为输入在每个步骤分为2，节点的数量将得到的平方在每一步，同时，因为只有一个元素是越来越消除，每级将失去只有一个元素从列表

In order to find the complexity of this one, I used the recursive tree method. Since input is divided into 2 at each step, the number of nodes will get squared at each step while since only one element is getting eliminated, every level will lose only one element from the list.

所以，我认为这个问题的复杂性应该是与西塔（N ² ）

So I think that the complexity of this problem should be Θ(n²)

我的权利在这个思考过程。如果不是这样，我是什么做错了吗？

Am I right in this thought process. If not, What am I doing wrong?

感谢你。

推荐答案

节点中的每一个步骤的数量不获取平方。相反，双打在各个层面。例如，节点的数量

The number of nodes at each step doesn't get squared. Instead, it doubles at every level. For example, the number of nodes at

• 问题的大小N：1
• 问题的大小N - 1：2
• 问题的大小N - 2：4
• 问题的大小N - 3：8
• 问题的大小N - 4：16
• ...
• 问题的大小N - I：2 ^我

• problem size n: 1
• problem size n - 1: 2
• problem size n - 2: 4
• problem size n - 3: 8
• problem size n - 4: 16
• ...
• problem size n - i: 2ⁱ

其结果是，在递归树节点的总数为1 + 2 + 4 + 8 + ... + 2 ^N = 2 ^{n + 1个} - 1。因此，所做的工作将是C2 ^{N + 1} - C，这是与西塔;（2 ^N ）。这是指数时间，而不是二次的时间。

As a result, the total number of nodes in your recursion tree will be 1 + 2 + 4 + 8 + ... + 2ⁿ = 2ⁿ⁺¹ - 1. Accordingly, the work done will be c2ⁿ⁺¹ - c, which is Θ(2ⁿ). This is exponential time, rather than quadratic time.

希望这有助于！

这篇关于时间开往递归算法恒定组合时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！