时间复杂度

算法的时间复杂度往往只是定性描述，即不需要算出来具体数值。仅需要有大体的估算结果（有点像高数中的极限，仅考虑n趋近于正无穷时的情况）。下面给出几种常见时间复杂度的代码。

  1. #include<iostream>
  2. using namespace std;
  3. int n,ans;
  4. int main(){
  5.     cin>>n;
  6.     //O(1)和数据输入规模无关
  7.     for(int i=0;i<9;++i)
  8.         ans+=n;
  10.     //O(logn)一般默认底数是2（就算不是也可以用指数换底公式换成2）
  11.     for(int i=n;i;i/=2)
  12.         ans+=n;
  14.     //O(√n)
  15.     for(int i=1;i*i<n;++i)
  16.         ans+=n;
  18.     //O(n)线性时间复杂度
  19.     for(int i=0;i<n;++i)
  20.         ans+=n;
  22.     //O(n^2)
  23.     for(int i=1;i<n;++i)
  24.         for(int j=i+1;j<n;++j)
  25.             ans+=n;
  27.     return 0; 
  28. }
此外，还有O(n!)（阶乘级）、O(C^n)（指数级）等时间复杂度。很显然，在大规模数据下这种复杂度的算法是不可行的，因此应注意规避此类算法。<br />由以上，计算出的时间复杂度为**10^8**级别以下，则在可接受范围之内。

常见算法的时间复杂度

1、纯循环：几重循环就是几次方
2、递归 主定理
常有的分析方法: 先看每一层的时间复杂度，再看有多少层

基础算法:

快速排序：快排平均下来有log(n)层，归并排序一定有log(n)层，每一层都是线性的复杂度， 因此时间复杂度为O(n*log(n)) 。因为归并排序利用的是完全二叉树的原理，所以一定有log层，而快速排序是二叉树，不一定是完全二叉树，所以不一定总是log(n)层。从代码上看归并排序每次是取中间坐标（二分），那么最终肯定会分成log(n)层，而快速排序是记录中间元素，而不是坐标，所以不一定能够分log(n)层

二分:因为每一次都会把区间对半分，所有最多对半分log(n)次，而每次的操作数（常数）很少，所以算法时间复杂度为O(log(n))

高精度算法：因为最多只有一个循环，所以是O(n)

双指针算法:看着是两层循环，但是内循环的j只加不减，所以至多执行不超过n次，因此算法复杂度是O(n)

数据结构:

链表:插入删除一个数的时间复杂度都是O(1),很快，但是遍历的时间复杂度为O(n)

栈队列:每次操作都是O(1)

单调栈 :对于栈，每个元素最多只进栈一次，最多只出栈一次，所以时间是O(n)的

单调队列:每个元素因为最多只进队一次，所以做多只出队一次，所以算法复杂度是O(n)

KMP :因为每循环一次，内层的j最多+1，所以时间复杂度为O(n), 内层总共执行次数 小于 n

Tiral 字符串统计: 每个操作只有一个循环，因此效率就和数组长度呈线性关系

并查集:
两个优化：
1、路径压缩
2、按秩合并
两个优化都加上，复杂度就是O(loglogn)

堆:
1、取得最小值O(1),
2、插入一个数删除堆顶元素，因为堆是完全二叉树，所以最多要down up log(n)次
所以效率为O(logn);

哈希表:
和快排类似，快排在每次划分的时候最坏的情况(局部有序或者有序或数字完全相同)下会有一边为空的情况，
深度为n-1，而每一层是O(n)的，所以效率是O(n^2),解决方案就是随机取或者取中间(不取两端)。哈希发生最坏
情况的概率极小，所以一般用平均来衡量为O(1)的

图论

搜索分析一般化成一棵树的形状最后一层n!个点，(n-1)! …. 总共效率
(n! + (n - 1)! + ….) n因为除了n！之外和前者相比都非常小，所以可以去掉，因此最终就是n! n

图的遍历:因为有st{N]保证每个点只被遍历一次，所以遍历点需要n次，同时还要遍历所有的边m所以总共
O(n + m);

拓扑排序是基于宽度优先遍历，所以也是O(n + m);

dijkstra 朴素版: 两重循环所以是O(n^2);
堆优化版:因为只经过每一个点一次，并且经过点的所有边，所以该循环体执行m次，每次循环内有堆的操作，所以是mlog(m),而m<=n^2，所以可以看成mlog(n);

bellman-ford：两重循环o(nm);

spfa:最坏的情况是O(nm),属于图例里理论时间复杂度很高，实际时间复杂度非常好，匈牙利算法与最大流也一样

spfa判负环比求最短路长很多，O(nm),求最短路的范围可以设到1e5

floyd:三重循环,所以是O(n^3)

prim:两重循环n^2

kruskal: 因为有个排序，并查集，所以是O(mlogm) + O(mlog1+m/n(n)) = O(mlogm);

染色法是图的深度优先遍历宽度优先遍历，所以效率是O(n + m);

匈牙利算法:外层是n，内层是遍历所有点和边所以是O(nm) m <= n^2 所以最坏是O(n^3),但是实际效率很高。

常见技巧:log2(10^k) ≈3*k 因为log2(8) =3,所以log2(10) > 3 log2(10^18) = log2(2^64) = 64;

数学

1、试除法:因为是从2~sqrt(x) 所以效率是sqrt(x)
2、分解质因数:sqrt(x);
3、筛法
线性筛法:最小质因子筛素数，每个数只被筛一次，O(n)
普通筛法:nlog(n) 不管是质数还是合数都用来筛后面的倍数
埃氏筛法:n(loglogn) 只用质数筛倍数
第一次循环n/1 第二次n/2，第三次n/3… 1 + 1/n + 2/n +…. = ln(n) + c(0.577..);
所以是nln(n)
如果是自然数1/2 + 1/3 + 1/5 + .. + 1/质数 = loglog(n);
4、最大公约数gcd : 欧几里得算法：log(n)，而且常数小
5、快速幂:k有多少个二进制位，就循环几次，所以是log(k)

动态规划

动态规划的问题的加算量= 状态数量 * 状态转移计算量(计算转移状态所要的时间)