关于块状链表
  • 板块学术版
  • 楼主zhangbo1000
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/12 12:45
  • 上次更新2024/9/12 13:32:52
查看原帖
关于块状链表
760291
zhangbo1000楼主2024/9/12 12:45

rt,OI wiki 上说块状链表所有操作是 O(n)O(\sqrt{n}) 的,但是我之前写的时候注意到:

设块长为 bb,总操作次数为 nn,分裂的阈值是 Θ(b)\Theta(b) 的话,显然总共最多只会分裂 Θ(nb)\Theta(\frac{n}{b}) 次,单次分裂显然也是 Θ(b)\Theta(b) 的,因此分裂的总复杂度为 Θ(n)\Theta(n) 的,最终得出因分裂产生的运算量应该是均摊 Θ(1)\Theta(1) 的吧?(硬说单次操作复杂度不考虑总计的话 Splay 好像还是 O(n2)O(n^2) 呢)

2024/9/12 12:45
加载中...