画出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 Coze智能助手搭建过程中的问题请教
- ¥15 12864只亮屏 不显示汉字
- ¥20 三极管1000倍放大电路
- ¥15 vscode报错如何解决
- ¥15 前端vue CryptoJS Aes CBC加密后端java解密
- ¥15 python随机森林对两个excel表格读取,shap报错
- ¥15 基于STM32心率血氧监测(OLED显示)相关代码运行成功后烧录成功OLED显示屏不显示的原因是什么
- ¥100 X轴为分离变量(因子变量),如何控制X轴每个分类变量的长度。
- ¥30 求给定范围的全体素数p的(p-2)/p的连乘积值
- ¥15 VFP如何使用阿里TTS实现文字转语音?