\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2017年10月18日 星期三

[ Median-of-Medians Algorithm ] 中位數演算法

這是一個可以在保證線性時間(c++ std::nth_element是隨機演算法)找出一個序列中第k大元素的演算法,網路上已經有不少教學,但是很多人都認為常數太大因此缺乏實作。

教學文在此:http://tmt514-blog.logdown.com/posts/484313-divide-and-conquer-method-iii-find-the-median

其實我高中時就想要試著去時做看看,但是因為那時的程式能力太差的關係,做出來的東西一直有bug,後來去忙其他事情後就被我忘掉了。最近因為學長面試有被問到一樣的問題跑來問我,才慢慢想起來有一份沒寫完的code,於是今天抱著不管怎樣都要寫出來的精神把他寫完了:


沒有留言:

張貼留言