画出递归树求递归表达式的解

Question

画出T（n）＝6T（n/5）×3n^2的递归树 并求解
写出下列函数的渐进表达式 4n^3+7n^2+8
8×2^n+2n^2
5×（1/n）+8n
4log n^4

Answer 1

该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：

1. 画出递归树并求解递归表达式的解：

递归表达式：T(n) = 6T(n/5) + 3n^2

递归树：

        n
        |
   ---n/5---
   |   |   |
 n/25 n/25 n/25
   ... ... ...

递归树的深度为 log5(n)，每层的工作量为 3n^2，因此总的工作量为：

T(n) = 3n^2 * (6^log5(n))
     = 3n^2 * (n^log5(6))
     = 3n^(log5(6) + 2)

因此，递归表达式的解为 T(n) = 3n^(log5(6) + 2)。

2. 写出下列函数的渐进表达式：

a) 4n^3 + 7n^2 + 8

该函数的最高次幂为 n^3，因此渐进表达式为 O(n^3)。

b) 8×2^n + 2n^2

该函数的最高次幂为 2^n，因此渐进表达式为 O(2^n)。

c) 5×(1/n) + 8n

该函数的最高次幂为 n，因此渐进表达式为 O(n)。

d) 4log n^4

该函数可以简化为 4 * 4log n，因此渐进表达式为 O(log n)。

---

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢