4 ms·
> One point the author hints at is that the median is more computationally intensive to compute than the mean. Computing the median requires you to store all yo
by cyphar 11y ago
> One point the author hints at is that the median is more computationally intensive to compute than the mean. Computing the median requires you to store all your samples in memory, and then sort them.
Actually, you can find the median in O(n)[1]. It still requires storing them all in memory though. It's based on quick select.
[1]: https://en.m.wikipedia.org/wiki/Median_of_medians https://en.m.wikipedia.org/wiki/Median_of_medians
- myrryr 11y agoNope, Median of Medians is an approximation.
- tamana 11y agoThe median-finding algorithm os exact. Reread the Wikipedia page more closely. MoM uses an approximate heuristic to guide the search for the exact median. The key is that the approximate has bounded error, and can be refined to exact in linear time.
- myrryr 11y agoHuh, I didn't get that from the Wiki article (it is a bit hard going), but... I found some other easier articles to follow on this. I stand corrected. Median of medians is freaking awesome :)
- justratsinacoat 11y ago>I found some other easier articles to follow on this Post them?
- Gibbon1 11y agoAlso the mean can be computed easily by a lady with an adding machine. And when all you have are adding machines you can trivially parallelize calculating the mean. Not sure how you'd do that with the median.