关于主定理
  • 板块灌水区
  • 楼主_ERO_
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/9/13 21:35
  • 上次更新2023/11/2 21:01:07
查看原帖
关于主定理
947565
_ERO_楼主2023/9/13 21:35

关于这道题

按照主定理,f(n)=O(nlogn)=O(nlogba+ϵ)=O(n1+ϵ)f(n) = O(nlogn) = O(n^{log_ba + \epsilon}) = O(n^{1 + \epsilon}) ,符合主定理的第三种形式,那应该 T(n)=f(n)=O(nlogn)T(n) = f(n) = O(nlogn) 。但是答案显然是 O(nlog2n)O(nlog^2n) 。

线上询问了老师,老师说这是因为这里 f(n) 不是关于 n 的多项式。但是我不是很理解(因为例如归并的f(n)=n也可以求解),所以想询问一下主定理能够在哪些条件下满足,以及一般该如何解决这道题。

2023/9/13 21:35
加载中...