六：时空复杂度分析

参考课堂笔记： https://www.acwing.com/file_system/file/content/whole/index/content/1120024/。

由数据范围反推算法复杂度： https://www.acwing.com/blog/content/32/。

常用int,long long等数据范围： https://www.acwing.com/blog/content/475/。

一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 10$^7$∼10$^8$最佳。

题目中的数据范围可以给我们很大的提示！！！

注：

O(logn)一般指$\log_2n$.
int范围约是2*10$^9$.
long long的范围约是10$^{18}$.
一般来说代码短的，常数会比较小.

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

n≤30, 指数级别, dfs+剪枝，状态压缩dp
n≤100 => O(n$^3$)，floyd，dp，高斯消元
n≤1000 => O(n$^2$)，O($n^2logn$)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
n≤10000 => O(n∗$\sqrt n$)，块状链表、分块、莫队
n≤100000 => O($nlogn$) => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分
n≤1000000 => O(n), 以及常数较小的 O($nlogn$) 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O($nlogn$)的做法：sort、树状数组、heap、dijkstra、spfa
n≤10000000 => O(n)，双指针扫描、kmp、AC自动机、线性筛素数
n≤10$^9$=> O($\sqrt n$)，判断质数
n≤10$^{18}$ => O($logn$)，最大公约数（欧几里得），快速幂（接近long long范围）
n≤10$^{1000}$=> O($(logn)^2$)，高精度加减乘除
n≤10$^{100000}$=> O($logk×loglogk$)，k表示位数，高精度加减、FFT/NTT

作者：yxc
链接：https://www.acwing.com/blog/content/32/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

hash表平均时间复杂度可以看成：O(1)，和快排分析类似。

注意：递归也是需要空间的，递归调用了系统栈，快速排序使用了递归，所以空间复杂度是O(logn)。

七：数学知识

数论基础： https://oi-wiki.org/math/number-theory/basic/。

数论参考系列文章： https://mp.weixin.qq.com/s/dFBbbTB8Fz2_n3YeMIj7nw。

蓝桥杯（三十）中介绍过数论的部分知识。

参考书籍：《算法竞赛进阶指南》。

7.1：质数

质数，也可以称为素数（过时的叫法）。

质数和合数是针对所有大于 1 的 “自然数” 来定义的（所有小于等于1的数都不是质数）。

质数的判定方法——试除法。

如何判定？
从质数定义出发，1.判断一个数是否大于1，2.判断它的因数是否只有1和它本身。

例题：866. 试除法判定质数（模板题）

给定 n 个正整数 ai，判定每个数是否是质数。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。

输出格式
共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。

数据范围
1≤n≤100,
1≤ai≤2^31 − 1
输入样例：
2
2
6
输出样例：
Yes
No

暴力做法：

对于一个数n，自然可以枚举从小到大的每个数看是否能整除n。

优化做法：

很容易发现这样一个事实：如果$x$ 是$n$ 的约数，那么$n/x$ 也是$n$ 的约数。

这个结论告诉我们，对于每一对 $(x,n/x)$，只需要检验其中的一个就好了。

为了方便起见，我们之考察每一对里面小的那个数。不难发现，所有这些较小数就是$[1,\sqrt n]$这个区间中的数。

所以可以开根号优化。

注意：不推荐使用$\sqrt n$的写法，也不推荐使用$i*i<=n$的写法。

第一种写法很慢，第二种写法存在溢出风险。

推荐写法：i <= n/i。

时间复杂度：$O(\sqrt n)$。

#include <iostream>
using namespace std;
int n;

// 判定质数
bool is_prime(int x){
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ ){
        if (x % i == 0) return false;
    }
    return true;
}

int main(){
    cin >> n;
    int a;
    while (n -- ){
        cin >> a;
        if (is_prime(a)) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

例题：867. 分解质因数（模板题）

给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。

输出格式
对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围
1≤n≤100,
1≤ai≤2×10^9
输入样例：
2
6
8
输出样例：
2 1
3 1

2 3

分解质因数还是利用上面的试除法。

求n的所有因数：n的因数可以被分成$[1,\sqrt n]$和$[\sqrt n + 1,n]$两个区间，根据试除法，每次遍历就能找到n的两个因数。

求n的所有质因数及其指数：

重要性质：n中最多只有一个大于$\sqrt n$的质因数。

证明：反证法，假设存在两个，那么它们相乘一定大于n，所以最多只有一个。

利用性质，我们可以先求出$[1,\sqrt n]$区间中的质因数及其指数，分解到最后，如果n != 1，那么剩下的数就是那个大于$\sqrt n$的质因数，否则不存在大于$\sqrt n$的质因数。

时间复杂度：$O(\sqrt n)$。（最坏情况下）

说明：分解质因数的实际时间复杂度要比判定质数要快。当$n = 2^k$时，它只有一个质因数2，最快时间复杂度是$O(log n)$。平均时间复杂度介于两者之间。

#include <iostream>
using namespace std;
int n;

void divide(int x){
    for (int i = 2;i <= x / i;i ++){
        if (x % i == 0){// i一定是质数
            int s = 0;// 将x中的所有i除尽，同时求i的指数s
            while (x % i == 0) x /= i,s ++;
            cout << i << ' ' << s << '\n';
        }
    }
    if (x > 1) cout << x << " 1\n";// 处理剩下的>sqrt(n)的质因数，最多只有一个
    cout << '\n';
}

int main(){
    cin >> n;
    int a;
    while (n -- ){
        cin >> a;
        divide(a);
    }
    return 0;
}

为什么循环中满足x % i == 0的i一定都是质数呢？（后面的筛法也有类似的东西）

因为经过while处理x，合数都会被除去。假设存在一个i是合数且x % i == 0，根据算术基本定理，它可以分解质因数：$i = p_1^{a_1}\star p_2^{a_2}*…\star p_k^{a_k}$，显然有$p_1 < i$，所以for循环会先遍历$p_1$，然后在while循环中将会除去x中的所有因子$p_1$，同理会去除x的其他质数因子，则x的因子中不包含[2,i-1]中的数，也就是说x和i不再有公共因子，那么如果x % i == 0，i就一定是一个质数，得证。

证明参考： https://oi-wiki.org/math/number-theory/pollard-rho/。

grant's Blog

算法基础课笔记（三三）

六：时空复杂度分析

七：数学知识

7.1：质数