顶尖的设计网站,外贸仿牌网站建设,网站开发的技术指标,上海网络推广方法目录 1 基础知识2 模板3 工程化 1 基础知识
#xff08;一#xff09; 由数据范围反推算法。
C中题目给出的要求时间是1秒或2秒计算出结果#xff0c;而1秒内C可以执行 1 0 7 ∼ 1 0 8 10^7 \sim 10^8 107∼108次操作。故需要把时间复杂度控制在 1 0 8 10^8 108以内。
给… 目录 1 基础知识2 模板3 工程化 1 基础知识
一 由数据范围反推算法。
C中题目给出的要求时间是1秒或2秒计算出结果而1秒内C可以执行 1 0 7 ∼ 1 0 8 10^7 \sim 10^8 107∼108次操作。故需要把时间复杂度控制在 1 0 8 10^8 108以内。
给定数目范围 n n n有如下情况
当 n ≤ 30 n\leq 30 n≤30时指数级别可以考虑的算法有dfs剪枝状态压缩dp。当 n ≤ 1 0 2 n \leq 10^2 n≤102时可以接受的最大的时间复杂度为 O ( n 3 ) O(n^3) O(n3)那么可以考虑的算法有floyddp。当 n ≤ 1 0 3 n\leq 10^3 n≤103时可以接受的最大的时间复杂度为 O ( n 2 l o g n ) O(n^2logn) O(n2logn)那么可以考虑的算法有dp二分。当 n ≤ 1 0 4 n \leq 10^4 n≤104时可以接受的最大的时间复杂度为 O ( n n ) O(n\sqrt{n}) O(nn )那么可以考虑的算法有块状链表。当 n ≤ 1 0 5 n\leq 10^5 n≤105时可以接受的最大的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)那么可以考虑的算法有排序算法快速排序、归并排序、堆排序线段树树状数组set/mapheapdijkstra heapspfa求凸包求半平面交二分。当 n ≤ 1 0 6 n \leq 10^6 n≤106时可以接受的最大的时间复杂度为常数较小的 O ( n l o g n ) O(nlogn) O(nlogn)那么可以考虑的算法有hash双指针扫描kmpAC自动机排序算法快速排序、归并排序、堆排序树状数组heapdijkstraspfa。当 n ≤ 1 0 7 n\leq 10^7 n≤107时可以接受的最大的时间复杂度为 O ( n ) O(n) O(n)那么可以考虑的算法有双指针扫描kmpAC自动机线性筛素数。当 n ≤ 1 0 9 n\leq 10^9 n≤109时可以接受的最大的时间复杂度为 O ( n ) O(\sqrt{n}) O(n )那么可以考虑的算法有判断质数。当 n ≤ 1 0 18 n\leq 10^{18} n≤1018时可以接受的最大的时间复杂为 O ( l o g n ) O(logn) O(logn)那么可以考虑的算法有最大公约数。
二 计算时间复杂度的小技巧有
看循环有几重循环就是n的几次方的时间复杂度。并查集的时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)。动态规划问题的计算量 状态的数量 * 状态转移的计算量。
2 模板
暂无。。。
3 工程化
暂无。。。
