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

画出递归树求递归表达式的解
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- Leodong. 2023-04-11 16:50关注
该回答通过自己思路及引用到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)。
如果以上回答对您有所帮助,点击一下采纳该答案~谢谢
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 求局部放电案例库,用于预测局部放电类型
- ¥100 QT Open62541
- ¥15 stata合并季度数据和日度数据
- ¥15 谁能提供rabbitmq,erlang,socat压缩包,记住版本要对应
- ¥15 Vue3 中使用 `vue-router` 只能跳转到主页面?
- ¥15 用QT,进行QGIS二次开发,如何在添加栅格图层时,将黑白的矢量图渲染成彩色
- ¥50 监控摄像头 乐橙和家亲版 保存sd卡的文件怎么打开?视频怎么播放?
- ¥15 Python的Py-QT扩展库开发GUI
- ¥60 提问一下周期性信信号的问题
- ¥15 jtag连接不上fpga怎么办