Stella981· 1423 阅读 ·2021-10-12 # 前端# log# 复杂度# splaySplay和LCT的复杂度分析 $Splay$的复杂度分析不论插入,删除还是访问,我们可以发现它们的复杂度都和$splay$操作的复杂度同阶,只是一点常数的区别我们不妨假设有$n$个点的$splay$,进行了$m$次$splay$操作采用势能分析我们记$w(x)\\left\\lceil\\log\_2(size(x))