赤耀半夏i 2023-04-11 16:36 采纳率: 80%
浏览 38
已结题

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

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

  • 写回答

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)。
    

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 4月11日
  • 已采纳回答 4月11日
  • 创建了问题 4月11日

悬赏问题

  • ¥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实现文字转语音?