Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add Splay 时间复杂度分析 #3694

Closed
Peanut-Tang opened this issue Dec 16, 2021 · 1 comment · Fixed by #3733
Closed

Add Splay 时间复杂度分析 #3694

Peanut-Tang opened this issue Dec 16, 2021 · 1 comment · Fixed by #3733
Labels
Content Request / 内容请求 New feature or request

Comments

@Peanut-Tang
Copy link
Contributor

页面英文名

splay-complexity

我希望能添加的内容是

添加 Splay 的时间复杂度分析,运用势能分析得出 Splay 的伸展操作的时间复杂度是均摊 $O(\log{n})$ 的,进而得出插入、删除等基于伸展的操作时间复杂度也是均摊 $O(\log{n})$ 的。

我了解到的相关参考资料有

https://www.luogu.com.cn/blog/Atalod/shi-jian-fu-za-du-shi-neng-fen-xi-qian-tan

https://www.cnblogs.com/reverymoon/p/10086216.html

@Peanut-Tang Peanut-Tang added the Content Request / 内容请求 New feature or request label Dec 16, 2021
@welcome
Copy link

welcome bot commented Dec 16, 2021

感谢你对 OI Wiki 的关注!记得在 Issue 中表达清楚自己的意思哦~

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Content Request / 内容请求 New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant