Gea-Suan LinJul 29, 2024

線性找中位數的演算法：Quickselect + Median of Medians

上禮拜看到「My Favorite Algorithm: Linear Time Median Finding (2018) (rcoh.me)」這篇，原文是 2018 的文章「My Favorite Algorithm: Linear Time Median Finding」。

找中位數最直覺的想法是排序後直接拉出來，這樣的

https://blog.gslin.org/archives/2024/07/29/11913/%e7%b7%9a%e6%80%a7%e6%89%be%e4%b8%ad%e4%bd%8d%e6%95%b8%e7%9a%84%e6%bc%94%e7%ae%97%e6%b3%95%ef%bc%9aquickselect-median-of-medians/

#Computer #Murmuring #Programming #algorithm #median #medians #quickselect

線性找中位數的演算法：Quickselect + Median of Medians

上禮拜看到「My Favorite Algorithm: Linear Time Median Finding (2018) (rcoh.me)」這篇，原文是 2018 的文章「My Favorite Algorithm: Linear Time Median Finding」。 找中位數最直覺的想法是排序後直接拉出來，這樣的演算法在最差情況下可以做到 。 不過這個問題有 Quickselect + Median of medians 的組合技，可以達到最差情況下仍然有線性時間解 。 記得是演算法的經典教科...

Gea-Suan Lin's BLOG