算法的时间复杂度和空间复杂度是评价算法优劣的两个重要指标。
本文将介绍如何分析算法的时间复杂度和空间复杂度，并给出几个例子供参考学习。
重点在于“时间复杂度”，一般空间复杂度不容易超出。本文讨论的复杂度均为最坏复杂度，即以$O$标识的。
🎈 作者：Eriktse
🎈 简介：19岁，211计算机在读，CCPC全国赛金牌，ICPC区域赛银牌退役选手🏆力争以通俗易懂的方式讲解编程和算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
🎈欢迎加群一起玩耍~QQ群：600240150
空间复杂度
我们先来介绍空间复杂度，这个一般比较容易分析，就是看开了多大的数组，一般来说题目可能给256MB左右，也有给1024MB的，实际都差不多，一点点常数的差别。
我们的int类型是由4个byte组成的，占据了4B的空间，所以大小为1e6的int数组，占据空间为4MB。
以这个为基准，我们估算一下，一般题目允许开的空间约为3e7大小的int数组。
有些数据类型比较省空间，比如黑科技bitset，要给空间复杂度除以一个机器字长（位数）。
一般来说，我们开的数组，不会超过1e7，如果要开1e7的数组，也基本是卡到1e7，不会更多了，常见于欧拉筛法。
时间复杂度
时间复杂度是一个老生常谈的问题，也是新手需要突破的一个鸿沟。
我们通过一些示例来帮助大家快速计算复杂度。
循环嵌套类
一般循环，时间复杂度$O(n)$。
for(int i = 1;i <= n; ++ i)
do something with O(1).
双重循环，时间复杂度$O(nm)$。
for(int i = 1;i <= n; ++ i)
for(int j = 1;j <= m; ++ j)
do something with O(1).
调和级数循环，时间复杂度$O(n \ln{n})$。
for(int i = 1;i <= n; ++ i)
for(int j = i;j <= n; j += i)
do something with O(1).
函数嵌套循环，时间复杂度$O(n * g(n)), f(n) = O(g(n))$
for(int i = 1;i <= n; ++ i)
f(i);
递归类
解空间为子集树，时间复杂度为$O(2^n)$。
子集树可以理解为一个二进制数，表示某个位置的东西选或不选。
解空间为；排列树，时间复杂度$O(n!)$。
一般就是这两种，通过一些限界函数，可以让搜索跑的更快，但是复杂度应该是不变的。
特别的，如果搜索过程中，采取了记忆化的方法（也有叫带备忘录的搜索），那么复杂度就是状态的个数，只需要看开了多大数组就好。
常见的一些数据结构和算法
树状数组|线段树：区间修改、区间查询均为$O(logn)$。
并查集：查询、合并均为$O(1)$，这里提一嘴，这个查询的复杂度其实是$O(logn)$，但是十分接近$O(1)$，具体的可以自己去查一查。
分解质因数：一般为$O(\sqrt{n})$，如果提前打出了lowp表，可优化到$O(logn)$。如果没有，还有一种方法是$Pollard-Rho$算法，自行百度。
快速幂：对于$a^b$，时间复杂度为$O(logb)$。
二分法：$O(logn)$
快速排序、归并排序、堆排序：$O(nlogn)$
set,priority_queue的增删查改，均为$O(logn)$（各种容器的$size()$函数均为$O(1)$）。
分析复杂度
对于下面这段代码，分析其时间复杂度：
1.
for(int i = 1;i <= n; ++ i)
for(int j = 1;j * j <= i; ++ j)
do something with O(1).
复杂度为$O(n ^ {\frac{3}{2}})$。
2.
void f(int n)
{
int res = 0;
for(int i = 1;i <= n; ++ i)res += i;
return f(n / 2) + res;
]
我们可以知道一共会产生约$logn$层递归，每一层执行一个$O(\frac{n}{2^i})$，根据主定理分析（这个不需要掌握，大家了解个大概就好了）时间复杂度为$O(n)$。
当然你不用主定理，也可以通过迭代法、递归树法、级数求和分析出来时间复杂度为$O(n)$。
这个递归方程的递归树是一条链，这条链一共是$logn$层。
Comments NOTHING