程式競賽常用的演算法

一開始是在 Hacker News Daily 上看到「Algorithms for Modern Hardware (algorithmica.org)」這篇,原文在「Algorithms for Modern Hardware」,本來是在他們要在 2022 夏天出一本書講現代硬體架構下的演算法,但在裡面看到了「Algorithms for Competitive Programming」這個網站,列出了程式競賽常用的演算法。

裡面的演算法常常是解問題的基礎 (小積木),拿來打 Leetcode 也很好用,不過要注意裡面都未必是最佳解,像是 Kth order statistic in O(N) 這邊只提到了 Quickselect 這個時間複雜度平均是 \theta(n) 的演算法 (最壞是 \theta(n^2)),但實際上配合 Median of medians 可以確保最壞的情況下是 \theta(n)

Leave a Reply

Your email address will not be published.