温岭 网站建设,广州网站建设怎么做,福州网站制作怎样,好看的网站页面设计一般ACM或者笔试题的时间限制是1秒或2秒。 在这种情况下#xff0c;C代码中的操作次数控制在 1 0 7 ∼ 1 0 8 10^7\sim10^8 107∼108为最佳。
下面给出在不同数据范围下#xff0c;代码的时间复杂度和算法该如何选择#xff1a; n ≤ 30 n\leq30 n≤30#xff0c;指数级别…一般ACM或者笔试题的时间限制是1秒或2秒。 在这种情况下C代码中的操作次数控制在 1 0 7 ∼ 1 0 8 10^7\sim10^8 107∼108为最佳。
下面给出在不同数据范围下代码的时间复杂度和算法该如何选择 n ≤ 30 n\leq30 n≤30指数级别 d f s dfs dfs剪枝状态压缩 d p dp dp n ≤ 100 ⇒ O ( n 3 ) n\leq100\rArr O(n^3) n≤100⇒O(n3) f l o y d floyd floyd d p dp dp高斯消元 n ≤ 1000 ⇒ O ( n 2 ) n\leq1000\rArr O(n^2) n≤1000⇒O(n2) O ( n 2 l o g n ) O(n^2logn) O(n2logn) d p dp dp二分朴素版 D i j k s t r a Dijkstra Dijkstra朴素版 P r i m Prim Prim B e l l m a n − F o r d Bellman-Ford Bellman−Ford n ≤ 10000 ⇒ O ( n ∗ x ) n\leq10000\rArr O(n*\sqrt{x}) n≤10000⇒O(n∗x )块状链表、分块、莫队 n ≤ 100000 ⇒ O ( n l o g n ) ⇒ n\leq100000\rArr O(nlogn)\rArr n≤100000⇒O(nlogn)⇒各种 s o r t sort sort线段树、树状数组、 s e t / m a p set/map set/map、 h e a p heap heap、拓扑排序、 d i j k s t r a h e a p dijkstraheap dijkstraheap、 p r i m h e a p primheap primheap、 K r u s k a l Kruskal Kruskal、 s p f a spfa spfa、求凸包、求半平面交、二分、 C D Q CDQ CDQ分治、整体二分、后缀数组、树链剖分、动态树 n ≤ 1000000 ⇒ O ( n ) n\leq1000000\rArr O(n) n≤1000000⇒O(n)以及常数较小的 O ( n l o g n ) O(nlogn) O(nlogn)算法 ⇒ \rArr ⇒ 单调队列、 h a s h hash hash、双指针扫描、 B F S BFS BFS、并查集、 k m p kmp kmp、 A C AC AC自动机常数比较小的 O ( n l o g n ) O(nlogn) O(nlogn)的做法 s o r t sort sort、树状数组、 h e a p heap heap、 d i j k s t r a dijkstra dijkstra、 s p f a spfa spfa n ≤ 10000000 ⇒ O ( n ) n\leq10000000\rArr O(n) n≤10000000⇒O(n)双指针扫描、 k m p kmp kmp、 A C AC AC自动机、线性筛素数 n ≤ 1 0 9 ⇒ O ( n ) n\leq10^9\rArr O(\sqrt{n}) n≤109⇒O(n )判断质数 n ≤ 1 0 18 ⇒ O ( l o g n ) n\leq10^{18}\rArr O(logn) n≤1018⇒O(logn)最大公约数快速幂数位DP n ≤ 1 0 1000 ⇒ O ( ( l o g n ) 2 ) n\leq10^{1000}\rArr O((logn)^2) n≤101000⇒O((logn)2)高精度加减乘除 n ≤ 1 0 100000 ⇒ O ( l o g k × l o g l o g k ) n\leq10^{100000}\rArr O(logk\times loglogk) n≤10100000⇒O(logk×loglogk) k k k表示位数高精度加减 F F T / N T T FFT/NTT FFT/NTT。
