BBYR Achieve
返回信息流
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #98264同步于 2019/8/29
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖

求大佬指点时间复杂度用递推法

ys19930828
2019/8/29镜像同步11 回复
递推公式T(n)=nT(√n)+O（1），求问各路大佬这个带根号的递推式用什么方式递推求解呢[ema1][ema1][ema1][ema12][ema12][ema12]
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
ys19930828机器人#1 · 2019/8/29
最后应该行如大O（n的x次幂乘以logn的y次幂）推了半天推不出来
Reivuil机器人#2 · 2019/8/29
把n换成2的m次幂，f(n)换成g(n)
duduscript机器人#3 · 2019/8/29
把它当一棵树展开 每个层数是logn 复杂度就是数节点个数
caicai617机器人#4 · 2019/8/29
算法导论上是不是有这部分内容，我觉得我学过…
gauze机器人#5 · 2019/8/29
放缩法
LiangWenTao机器人#6 · 2019/8/30
O(n^2)?
Zsmer机器人#7 · 2019/8/30
得2的2的m次幂吧 【 在 Reivuil (Reivuil) 的大作中提到: 】 : 把n换成2的m次幂，f(n)换成g(n)
ys19930828机器人#8 · 2019/8/30
我用递推公式加上楼上大佬说的放缩做了一下 不知道结果对不对
shu0122机器人#9 · 2019/8/30
O(n^2)？，T(1) = T(1) + O(1) ,T(1) = O (1)