一般ACM或者筆試題的時間限制是1秒或2秒。
在這種情況下,C++代碼中的操作次數控制在 10^7為最佳。
下面給出在不同數據范國下,代碼的時間復雜度和算法該如何選擇:
1.n≤ 30,指數級別,dis+剪枝,狀態壓縮dp
2.n < 100 => 0 (n^2), floyd, dp
3.n ≤1000=>0(n^3), 0(nlogn), dp,二分
4. n ≤ 10000 => O(n * √n), 塊狀鏈表
5.n ≤100000=>0(nlogn)=>各種sort,線段樹、樹狀數組、set/map、 heap、dijkstra、 spta、求凸包、求半平面交、二分
6.n ≤1000000~>0(9),以及常數較小的O(nlogm)算法>hash、雙指針掃描、kemp、 AC自動機,常數比較小的o(nlogr)的做法:sort、樹狀數組、heap、 dijkstra、spfa
7.n ≤10000000 =>0(m),雙指針掃描、kmp、AC自動機、線性篩索數
8.n ≤10^9=>O(√n),判斷質數
9.n ≤ 10^18 => O(logn), 最大公約數