求助算递归复杂度
  • 板块学术版
  • 楼主yukimianyan
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/9/20 13:39
  • 上次更新2023/11/2 19:00:29
查看原帖
求助算递归复杂度
509229
yukimianyan楼主2023/9/20 13:39

T(n)=2T(n2)+O(nlog⁡n)T(n)=2T(\frac n 2)+O(n\log n)

它的时间复杂度是 T(n)=O(nlog⁡n)T(n)=O(n\log n) 还是 T(n)=O(nlog⁡2n)T(n)=O(n\log^2n)?

  1. 主定理:因为 O(nlog⁡n)O(n\log n) 较大,给出 T(n)=O(nlog⁡n)T(n)=O(n\log n),但是
  2. 这个东西不符合主定理第三条的 af(n/b)≤cf(n)af(n/b)\leq cf(n)(算出来是 log⁡n−1≤clog⁡n\log n-1\leq c\log n 不成立)
  3. 打表,T(200000) 是 3e7,T(2000000) 是 4e8
  4. 暴力展开 T(n)T(n) 得到是 O(nlog⁡2n)O(n\log^2n)

所以应该怎么算呢?

2023/9/20 13:39
加载中...