在NOIP競賽中如何通過數據範圍估計演算法複雜度，選取適合的演算法？

在NOIP競賽中如何通過數據範圍估計演算法複雜度，選取適合的演算法？

---

首先得記住基本演算法的時間複雜度，包括一些語言自帶庫的時間複雜度。

其次記住OI老爺機大概是1e8ops/s。

接著把n代入常用時間複雜度O(1)，O(logn)，O(√n)，O(n)，O(nlogn)，O(n^2)，O(n^2logn)，看看1e8大概落在哪個區域內。

最後和演算法再對應，看看哪個演算法複雜度符合要求又靠譜，搞一搞就AC了（滑稽

---

根據我的經驗

5k以下，可能是n2的演算法。根據情況考慮也可能是dp。

10^5可能是nlogn的演算法。線段樹，樹狀數組之類的二叉數據結構。其實也有可能是on的演算法。根據題目來看吧。

10^9可能是logn，可以考慮二分

想到再補充

---

不基本上記住一些常用演算法的時間複雜度，然後到時候就看著數據猜，但其實基本上都是log的，所以我覺得幫助不大

---

推薦閱讀：