算法
常用算法
搜索算法
- 线性搜索或顺序搜索
- 二分搜索：用于搜索排序后的集合
排序
- 冒泡排序
- 插入排序
贪心算法
每一步都选择最好的选项，而不考虑可能导致最优解的所有步骤序列
函数的增长
$\mathrm O$记号用于描述$g(x)$的上限，$\Omega$用于描述$g(x)$的下限，$\Theta$用于描述$g(x)$的上下限。
- 令$f$和$g$为从整数集合或实数集合到实数集合的函数，如果存在正常数$C$和$k$，使得只要$x>k$，就有
$$
\mid f(x)\mid \le C\mid g(x)\mid
$$我们就说$f(x)$是$\mathrm O(g(x))$ - 令$f$和$g$为从整数集合或实数集合到实数集合的函数，如果有常数$C$和$k$，使得只要$x>k$，就有
$$
\mid f(x)\mid\ge C\mid g(x)\mid
$$ - 令$f$和$g$为从整数集合或实数集合到实数集合的函数，如果$f(x)$是$\mathrm O(g(x))$及$f(x)$是$\Omega (g(x))$，就说$f(x)$是$\Theta (g(x))$。
函数的组合增长
- 假定$f_1(x)$是$\mathrm O(g_1(x))$，$f_2(x)$是$\mathrm O(g_2(x))$，那么$(f_1+f_2)(x)$是
$$
\mathrm O(max(\mid g_1(x)\mid , \mid g_2(x)\mid))
$$ - 假定$f_1(x)$是$\mathrm O(g_1(x))$，$f_2(x)$是$\mathrm O(g_2(x))$，那么$(f_1 f_2)(x)$是$\mathrm O(g_1(x)g_2(x))$
算法复杂度
| 复杂度 | 术语 | 复杂度 | 术语 |
|---|---|---|---|
| $\Theta (1)$ | 常数复杂度 | $\Theta (n^b)$ | 多项式复杂度 |
| $\Theta (logn)$ | 对数复杂度 | $\Theta (b^n),b>1$ | 指数复杂度 |
| $\Theta (n)$ | 线性复杂度 | $\Theta (n!)$ | 阶乘复杂度 |
| $\Theta (nlogn)$ | $nlogn$复杂度 |
- 一般来讲，能用多项式复杂度的算法解决的问题都是易解的，反之是难解的。
- 能用多项式时间验证解的问题属于NP类，易解的问题属于P类。
- NP完全问题，这类问题的性质是，只要其中任何一个问题能用一个多项式时间最坏情形算法来解答，那么所有这些问题都能用多项式时间最坏情形算法解答。
整数
- 如果$a$和$b$是整数，$a\neq 0$，若有整数$c$使$b=ac$，就说$a$整除$b$。在$a$整除$b$时，$a$是$b$的一个因子，$b$是$a$的倍数，符号$a\mid b$表示$a$整除$b$。当$a$不能整除$b$时写成$a∤b$
- $a\mid b$也可以表示成$\exists c(ac=b)$，论域是整个整数集合。
- 令$a$，$b$，$c$为整数。则
- 若$a\mid b$和$a\mid c$，则$a\mid (b+c)$；
- 若$a\mid b$和$a\mid c$，则$a\mid mb+nc$，其中$m$和$n$为整数；
- 若$a\mid b$，那么对所有整数$c$都有$a\mid bc$；
- 若$a\mid b$，$b\mid c$，则$a\mid c$；
同余
- 带余除法：令$a$为整数，$d$为正整数，有唯一的整数$q$和$r$，并且$0\le rlt d$，满足$a=dq+r$。
- 若$a$和$b$为整数而$m$为正整数，如果$m$整除$a-b$，就说$a$模m同余$b$。用$a\equiv b\pmod m$。也就是说$a\equiv b\pmod m$当且仅当$a \mod m=b\mod m$
- 令$m$为正整数，整数$a$和$b$模$m$同余的充分必要条件是存在整数$k$，使$a=b+km$
- 整数$a$模$m$所有整数同余的集合称为$a$模$m$的同余类
- 令$m$为正整数。若$a\equiv b\pmod m$，$c\equiv d\pmod m$，那么
$$
a+c\equiv b+d\pmod m\
ac\equiv bd\pmod m
$$ - 令$m$是正整数，$a$和$b$是整数，则有
$$
(a+b)\mod m = ((a\mod m)+(b\mod m))\mod m\
ab\mod m = ((a\mod m)(b\mod m))mod m
$$ - 根据$\mod m$和关于模$m$同余的定义，可得$a\equiv (a\mod m)(\mod m)$，并且$b\equiv (b\mod m)(\mod m)$，因此
$$
a+b\equiv (a\mod m)+(b\mod m)(\mod m)\
ab\equiv (a\mod m)(b\mod m)(\mod m)
$$
同余应用
- 散列函数
- 伪随机数
最常用的产生伪随机数的过程称为线性同余。选择4个数：模数$m$，乘数$a$，增量$c$和种子$x_0$，使得$2\le a\lt m$，$0\le c\lt m$，$0\le x_0 m$。生成伪随机序列${x_n}$，使得对所有$n$，$0\le x_n \lt m$。生成的办法是逐次同余：
$$
x_{n+1} = (ax_n +c)\mod m
$$
- 密码学
凯撒密码：
$$
f(p)=(p+k)\mod 26\
f(p)=(ap+b)\mod 26
$$
素数和最大公约数
- 每个大于1的正整数都可以唯一写为素数的乘积。对大整数进行素因子分解所需的时限在密码学中起着重要的作用。
- 如果$n$是个合数，那么$n$必有小于或等于$\sqrt n$的一个素因子。
- 梅森素数，是形如$2^p-1$这样的整数。目前已知最大的素数都是这种形式，可用卢卡斯－莱莫尔(Lucas-Lehmer)检验的方法判断$2^p-1$是否为素数。
- 素数定理：当$x$无限增长时，不超过$x$的素数个数与$x/Inx$之比趋于1。
- 令$a$和$b$是不全为$0$的两个整数。能使$d\mid a$和$d\mid b$的最大整数$d$称为$a$和$b$的最大公约数。$a$和$b$的_最大公约数_用$gcd(a, b)$表示。
- 如果整数$a$和$b$的最大公约数是$1$，就说它们是互素的。
- 整数$a_1,a_2,\cdots,a_n$是两两互素的，如果只要$1\le i\lt j\le n$，就有$gcd(a_i, b_j)=1$
- 正整数$a$和$b$的_最小公倍数_是能被$a$和$b$整除的最小正整数。$a$和$b$的最小公倍数用$lcm(a, b)$表示。
- 令$a$和$b$为正整数，则$ab = gcd(a, b)\cdot lcm(a, b)$
求最大公约数算法
- 假定两个不全为$0$的整数$a$和$b$的素因子分解为：
$$
a=p_1^{a_1}p_2^{a_2}\dots p_n^{a_n} \
b=p_1^{b_1}p_2^{b_2}\dots p_n^{b_n}
$$
每个整数都是非负整数，而且出现在$a$和$b$分解中的所有素数都包含在两个分解之中，必要时以0为指数出现。于是$gcd(a, b)$由下面的公式给出
$$
gcd(a, b) = p_1^{min(a_1,b_1)}p_2^{min(a_2, b_2)}\dots p_n^{min(a_n,b_n)}
$$
例如，求$120$和$500$的最大公约数：
$$
120 = 2^3\cdot 3\cdot 5 , 500 = 2^2\cdot 5^3\
gcd(120, 500) = 2^{min(3,2)}\cdot 3^{min(1,0)}\cdot 5^{min(1,3)}\
= 2^3\cdot 3^0\cdot 5^1 = 20
$$ - 另一个求最大公约数的算法就是欧几里得算法。
- 令$a=bq+r$，其中$a,b,c,q$均为整数，则$gcd(a, b)＝gcd(b,r)$。
求最小公倍数算法
同最大公约数算法类似，最小公倍数的由以下公式给出：
$$
lcm(a, b) = p_1^{max(a_1,b_1)}p_2^{max(a_2, b_2)}\dots p_n^{max(a_n,b_n)}
$$
整数和进制
令$b$为不等于$1$的正整数，那么如果$n$是个正整数，就可以唯一地表示为下面的形式：
$$
n = a_kb^k+a_{k-1}b^{k-1}+\cdots +a_1b+a_0
$$
其中$k$是非负整数，$a_0,a_1,\cdots,a_k$是小于$b$的非负整数，$a_k\neq 0$。该形式被称为$n$的$b$进制展开。
数论应用
*$a$和$b$为正整数，则存在整数$s$和$t$，使得为$gcd(a,b)=sa+tb$。
- 如果$a,b,c$为正整数，使得$gcd(a, b)=1$且$a\mid bc$，那么$a\mid c$。
- 如果$p$是素数，且$p\mid a_1a_2\cdots a_n$，其中$a_j$为整数，则对某个$i$，$p\mid a_i$
- 令$m$为正整数，$a,b,c$为整数，如果$ac\equiv bc\pmod m$且$gcd(c, m)=1$，那么$a\equiv b\pmod m$