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.

Sign up for GitHub

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

Jump to bottom

Add Median of medians #4455

Closed
StudyingFather opened this issue Nov 18, 2022 · 0 comments · Fixed by #4457
Closed

Add Median of medians #4455

StudyingFather opened this issue Nov 18, 2022 · 0 comments · Fixed by #4457
Assignees
@StudyingFather
Labels
Content Request / 内容请求 New feature or request

Comments

@StudyingFather
Copy link
Member

页面英文名

No response

我希望能添加的内容是

快速排序 页面中介绍的线性时间找第 k 大元素算法，其时间复杂度依赖于哨兵元素的选择。如果哨兵元素选择不当，该算法时间复杂度很容易退化到 O(n^2)。

为解决这一问题，该页面目前提供了一种随机选择的方法来确保线性时间复杂度。而 Median of medians 则是一个确定性算法，最坏时间复杂度仍可以做到 O(n)。

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

Median of medians - Wikipedia
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@StudyingFather StudyingFather

Labels
Content Request / 内容请求 New feature or request
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

feat(quick-sort): add median of medians algorithm OI-wiki/OI-wiki
1 participant
@StudyingFather