求助主定理
  • 板块学术版
  • 楼主FBW2010
  • 当前回复33
  • 已保存回复33
  • 发布时间2024/9/20 09:43
  • 上次更新2024/9/20 14:40:23
查看原帖
求助主定理
906072
FBW2010楼主2024/9/20 09:43

关于我无意间刷到一道初赛题,题意大概是求递归形式为 T(n)=2T(n2)+O(nlogn)T(n)=2T(\frac{n}{2})+O(n\log n) 的复杂度,于是直接套用主定理的情况3,算出 O(nlogn)O(n\log n)。结果一看答案,竟是 O(nlog2n)O(nlog^2n)。去复习了一下主定理,又拷问了半天 chatgpt,只知道好像主定理不适用于某些问题,要考虑递归复杂度影响,搞得本蒟蒻更懵逼了。问:

  1. 为什么用主定理无法准确得出这题答案?

  2. 主定理不适用于哪些情况?

  3. 对于主定理不适用的又该如何求解?

2024/9/20 09:43
加载中...