递归树法

发布于 2024-10-15 15:15:53 字数 502 浏览 2 评论 0原文

给定方程：T(n) = T(n/4) + T(n/2) + n^2

树模型：

              T(n)                 -- Level 1
             /    \
       T(n/4)       T(n/2)         -- Level 2
        /   \       /    \
 T(n/16)  *T(n/8) T(n/4)  *T(n/8)  -- Level 3

来自 MIT 算法课程讲座：http://www.youtube.com/watch?v=whjt_N9uYFI

分钟：38:53

问题：如何、什么以及为什么第三级变成n/8？创建递归树的显式方程是什么？

顺便说一下，这不是家庭作业问题。

原文

Given Equation: T(n) = T(n/4) + T(n/2) + n^2

Model of Tree:

              T(n)                 -- Level 1
             /    \
       T(n/4)       T(n/2)         -- Level 2
        /   \       /    \
 T(n/16)  *T(n/8) T(n/4)  *T(n/8)  -- Level 3

From Lecture of MIT Algorithm Class: http://www.youtube.com/watch?v=whjt_N9uYFI

Minute: 38:53

Question: How, What and Why 3rd level becomes n/8 ? What is the explicit equation to create recursion tree?

This isn't the homework question by the way.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

夜吻♂芭芘 2024-10-22 15:15:53

原始树是这样的：

  T(n)    =   n^2  ->  T(n/4)
                   ->  T(n/2)

当您展开第一个分支时，您进行替换n = n/4，因此您得到：

  T(n/4)  =   (n/4)^2  ->  T((n/4)/4)
                       ->  T((n/4)/2)

          =   (n/4)^2  ->  T(n/16)
                       ->  T(n/8)

对于第二个分支，类似地，n = n/2 code>

  T(n/2)  =   (n/2)^2  ->  T(n/8)
                       ->  T(n/4)

因此将这些扩展代回 T(n) 你得到

  T(n)    =   (n^2)    ->  (n/4)^2   ->  T(n/16)
                                     ->  T(n/8)
                       ->  (n/2)^2   ->  T(n/8)
                                     ->  T(n/4)

The original tree is this:

  T(n)    =   n^2  ->  T(n/4)
                   ->  T(n/2)

When you expand the first branch, you make a substitution n = n/4 so you get:

  T(n/4)  =   (n/4)^2  ->  T((n/4)/4)
                       ->  T((n/4)/2)

          =   (n/4)^2  ->  T(n/16)
                       ->  T(n/8)

and similarly for the second branch, n = n/2

  T(n/2)  =   (n/2)^2  ->  T(n/8)
                       ->  T(n/4)

so substituting these expansions back into T(n) you get

  T(n)    =   (n^2)    ->  (n/4)^2   ->  T(n/16)
                                     ->  T(n/8)
                       ->  (n/2)^2   ->  T(n/8)
                                     ->  T(n/4)

回复收藏 0 原文

~没有更多了~