解决递归：T（n）= 3T（n / 2）+ n [英] Solving a recurrence: T(n)=3T(n/2)+n

问题描述

我需要找到n的递归解，如果n> 1的 T（n）= 3T（n / 2）+ n ，则为2的幂

I need to Find the solution of the recurrence for n, a power of two if T(n)=3T(n/2)+n for n>1 and T(n)=1 otherwise.

使用 n = 2 ^ m，S（m）= T（2 ^（m -1））我可以得出以下结论：

using substitution of n=2^m,S(m)=T(2^(m-1)) I can get down to:

S（m）= 2 ^ m + 3 * 2 ^（m-1）+ 3 ^ 2 * 2 ^（m-2）+⋯+ 3 ^（m-1）2 ^ 1 + 3 ^ m

但是我不知道如何简单地做到这一点。

But I have no idea how to simply that.

推荐答案

这些重复类型最容易解决由Master Theem由算法分析得出，解释如下：

These types of recurrences are most easily solved by Master Theorem for analysis of algorithms which is explained as follows:

让 a 为大于或等于1的整数， b 是大于1的实数，而 c 是正实数。给定形式为-

Let a be an integer greater than or equal to 1, b be a real number greater than 1, and c be a positive real number. Given a recurrence of the form -

T（n）= a * T（n / b）+ n ^c ，其中n> 1那么对于 n 的 b 幂，如果

T (n) = a * T(n/b) + n^c where n > 1, then for n a power of b, if

1. Log _b a< c，T（n）=Θ（n ^c ）;


2. Log _b a = c，T（n）=Θ （n ^c * Log n）;


3. Log _b a> c，T（n）=Θ（n ^{log _b a} ）。

1. Log_ba < c, T (n) = Θ(n^c);
2. Log_ba = c, T (n) = Θ(n^c * Log n);
3. Log_ba > c, T (n) = Θ(n^log_ba).

---

复发的英语翻译

在主定理中最重要的要理解的是常数 a，b和c 在重复中提到。让我们以您自己的递归为例-T（n）= 3T（n / 2）+ n-。

The most critical thing to understand in Master Theorem is the constants a, b, and c mentioned in the recurrence. Let's take your own recurrence - T(n) = 3T(n/2) + n - for example.

实际上，这种递归表示它所代表的算法是这样，

This recurrence is actually saying that the algorithm represented by it is such that,

（解决尺寸为 n 的时间）=（解决尺寸为 3 大小为 n / 2 ）+ n

(Time to solve a problem of size n) = (Time taken to solve 3 problems of size n/2) + n

最后的 n 是合并那些 3 n / 2 大小的问题的结果的成本。

The n at the end is the cost of merging the results of those 3 n/2 sized problems.

现在，直观上您可以理解：

Now, intuitively you can understand that:

• 如果解决大小为 n / 2 的 3 个问题的权重大于 n 的权重，则第一项将确定总体复杂性；


• 如果成本 n 的权重大于解决大小为 n / 2 <的 3 个问题 / em>，那么第二项将确定总体复杂度；并且，


• 如果两个部分的权重相同，则解决子问题并将其结果合并将具有总体复合权重。

• if the cost of "solving 3 problems of size n/2" has more weight than "n" then the first item will determine the overall complexity;
• if the cost "n" has more weight than "solving 3 problems of size n/2" then the second item will determine the overall complexity; and,
• if both parts are of same weight then solving the sub-problems and merging their results will have an overall compounded weight.

根据以上三个直观的理解，仅出现了三个主定理情况。

From the above three intuitive understanding, only the three cases of Master Theorem arise.

在您的示例中，a = 3，b = 2，c =1。因此，在情况3中，Log _b a = Log ₂ 3更大大于1（c的值）。

In your example, a = 3, b = 2 and c = 1. So it falls in case-3 as Log_ba = Log₂3 which is greater than 1 (the value of c).

因此复杂度很简单-Θ（n ^{log _b a} ）= Θ（n ^{log ₂ 3} ）。

The complexity therefore is straightforward - Θ(n^log_ba) = Θ(n^log₂3).

这篇关于解决递归：T（n）= 3T（n / 2）+ n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！