tionallynessed 2022-03-05 19:23 采纳率: 33.3%
浏览 46
已结题

看《数据结构与算法分析》有不懂的地方

《数据结构与算法分析》马克艾伦维斯 C语言描述第二版 第24页
前提:若N=2的k次,则T(N)=N*(k+1)。那为什么T(N)=NlogN+N=O(NlogN)?

  • 写回答

3条回答 默认 最新

  • 关注
    
    T(n)=2T(n/2)+n
        =2(2T(n/2*2)+n)+n
        =2(2(2T(n/2*2*2)+n)+n)+n
        =2^3T(n/2^3)+3n
        =...
        =2^kT(n/2^k)+kn            现在设 n=2^k
        =nT(1)+kn
        =n(T(1)+k)            T(1)是常数,可以忽略
        =kn
        =nlogn
    

    img

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

报告相同问题?

问题事件

  • 系统已结题 3月14日
  • 已采纳回答 3月6日
  • 创建了问题 3月5日

悬赏问题

  • ¥15 java map类型数据格式,如何快速通过前缀匹配元素
  • ¥15 stc12c5a60s2、QMC5883L、LCD1602组合测量磁场所需程序
  • ¥15 vba参数转c++ SAFEARRAY
  • ¥20 Win11测试yolov4,“找不到nvcuda.dll”怎么办?
  • ¥15 simulink绘制bode图
  • ¥15 php_network_getaddresses: getaddrinfo failed: Name or service not known
  • ¥15 用msg发消息出现的问题
  • ¥15 unity3d机械臂
  • ¥20 判断两个表是否完全相同
  • ¥20 工控机出现散热器转一下停一下这种情况,是什么原因造成的