关于Splay的时间复杂度证明
  • 板块学术版
  • 楼主zhangjunyan2580
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/4/9 13:29
  • 上次更新2023/11/5 00:50:26
查看原帖
关于Splay的时间复杂度证明
103558
zhangjunyan2580楼主2021/4/9 13:29

文章链接

不太懂这篇文章中的一个地方,假如Splay只用单旋,为什么不能将第一步单旋的结论直接累加得到T(n)<Θ(1)+Θ(xroot)Θ(xbeginning)T(n)<\Theta(1)+\Theta(x_{root})-\Theta(x_{beginning}),得到T(n)=Θ(logn)T(n)=\Theta(\log n)呢?

恳请知道的大佬解答一下,谢谢!

2021/4/9 13:29
加载中...