算法之数学

作者: 暴走竹竿 | 来源:发表于2019-08-08 16:57 被阅读0次

0x01 开坑：简介

现今对数据处理的都是大量，大集合，所以简介一些离散数学

例如：

问题一

设一组N哥数而要确定其中第K个最大者，我们称之为选择问题，只要学过编程的所以这种解决的“直观方法”很多

方法一：比如冒泡，递减顺序，然后返回位置K上的元素。

方法二：把K个元素读入数组并递减排序，然后将剩下的元素再逐个读入，当新元素被读到时，如果他小于数组的第K个元素则忽略，否则将他放在数组中的正确位置，同时将原数组中的最后一个元素挤出数组。当算法终止时，位于第K个位置上的元素作为答案返回

这两种都算法都非常简单，算法那个更好，或者是两个算法够好吗？例如使用3000万个元素的随机文件和k=15000000进行模拟指出，两个算法在合理的时间内均不能结束计算；每种算法都需要计算机若干天才能算完(不过最终结果还是能够算出来的).

问题二

解决字谜(word puzzle)游戏。输入由一些字母构成的二维数组和一个单词表组成。目标是找出字谜中的所有单词。如下表格

NULL	1	2	3	4
1	t	h	i	s
2	w	a	t	s
3	o	a	h	g
4	f	g	d	t

可以组成的单词可以是 this,two,fat和that

现在有两种算法可以满足这个问题。

方法一：对单词表中的每个单词，我们检查每个有序三元组(行，列，方向)，验证是否有单词的存在。这需要大量嵌套的for循环，但他基本上是直观的算法

方法二：对于每一个尚未越出迷板边缘的有序四元组(行，列，方向，字符数)，我们可以检测是否所指的单词再单词表中。这也导致使用大量嵌套的for循环。如果任意单词中的最大字符数已知，那么该算法有可能节省一些时间。

上述的两种方法，解决上面哪一种题还好解，如果要解决行列都有16个字符，上面就两种算法就要花费相当可观的时间了，但还是有方法能快速解决。

上述两个问题都是都能简单的体现在大量或大集合的运行时间问题，如果我们能够估算程序的运行时间，尤其是在，如何在尚未编码的情况下比较两个程序的运行时间。我们还将显著的节约成本，以及集中精力的优化代码段。

0x02 指数

$\frac{X^A}{X^b}=X^{A-B}$

$X^AX^B=X^{A+B}$

$(x^A)^B=X^{AB}$

$X^N+X^N=2X^N \neq X^{2N}$

$2^N+2^N=2^{N+1}$

0x03 对数

在计算机科学中，除非有特别的声明，所有的对数都是以2为底的。

定义1

$X^A=B {当且仅当} log_xB=A$

定理1

$log_AB=\frac{log_CB}{logCA}; A,B,C>0 A \neq 1$

证明：

设
$X=log_CB， Y=log_CA，Z=log_AB$
此时由对数定义
$C^X=B,C^Y=A,A^Z=B$
联合上面三个则得到
$B=C^X=(C^Y)^Z \\ \Rightarrow X=YZ \\ \Rightarrow Z=X/Y$

定理2

$logAB=logA+logB; A,B>0$

证明：

方法同上
$X=logA， Y=logB，Z=logAB$
由定义得
$2^X=A,2^Y=B,2^Z=AB \\ \Rightarrow 2^X2^Y=2^{XY}$
下面的的公式都可以推导
$logA/B=logA-logB \\ log(A^b)=BlogA \\ logX<X 对所有的X>0成立 \\ log1=0,log2=1,log1024=10,log1048576=20$

0x04 级数

级数又分几何级数和算数级数

几何级数:从第二项起,每一项是前一项的多少次方

算术级数：从第二项起，每一项均由前一项加一个常数所构成的序列。

几何级数

常用的两个公式为
$\sum_{i = 0} ^n 2^i=2^{N+1}-1 \quad (1) \\ \sum_{i = 0} ^n A^i=\frac{A^{N+1}-1}{A-1} \quad (2)$
其中公式2如果0<A<1则
$\sum_{i = 0} ^n A^i\leq\frac{1}{1-A}$
公式推导
$\sum_{i=0} ^\infty A^i(0<A<1)$
设S为总和
$S=1+A+A^2+A^3+A^4...... \\ 两边乘以A则 \\ AS=A+A^2+A^3+A^4+A^5...... \\ S-AS=1 \\ \Rightarrow S=\frac{1}{1-A}$
同样的方法可以计算
$\sum_{i=1}^\infty i/2^i$

$S=\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\frac{4}{2^4}...... \\ 两边同时乘以2 \\ 2S=1+\frac{2}{2}+\frac{3}{2^2}+\frac{4}{2^3}+\frac{5}{2^4}...... \\ 两个相减 \\ 结果S=1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}$

算数级数

$\sum_{i=1}^ni=\frac{N(N+1)}{2}\thickapprox \frac{N^2}{2}$

例如：
$2+5+8+...+(3k-1)$
转换成一
$3(1+2+3+...+k)-(1+1+1+1+...+1) \\ \Rightarrow \frac{3k(k+1)}{2-k}$
转换成二
$第一项与最后一项的和都是3k+1 \\ 它有k/2的项，每一项和为 \\ S=\frac{k(3k+1)}{2}$

答案相同哟

但，现在下面说的两个公式就不常见了
$\sum_{i=1}^Ni^2=\frac{N(N+1)(2N+1)}{6}\thickapprox \frac{N^3}{3} \\ \sum_{i=1}^Ni^k \thickapprox \frac{N^k+1}{|k+1|},k\neq-1$
当K=-1时，公式2不成立。此时我们需要下面的公式，这个公式在计算机科学中使用要远比在数学其他科学中用的频繁。
$H_N又称调和数$
调和数的和又叫做调和和

下面近似中误差趋向于
$\gamma \thickapprox0.57721566$
称为欧拉常数
$H_N=\sum_{i=1}^N\frac{1}{i} \thickapprox log_eN$
一下两个公式一般的代数运算：
$\sum_{i=1}^Nf(N)=Nf(N) \\ \sum_{i=n_0}^Nf(i)=\sum_{i=1}^Nf(i)-\sum_{i=1}^{n_0-1}f(i)$

0x05 模运算

如果N整除A-B，那么我们就说A与B模N同余，记为
$A\equiv B(mod N)$
无论A还是B被N除去，所有余数都是相同的。类似
$81 \equiv 61 \equiv 1 (mod 10)$
如同等式的情形
$A \equiv B(mod N) \\ \Rightarrow A+C \equiv B+C(mod N) \\ 以及 AD \equiv BD(mod N)$
N常常为素数，对此，我们有3个重要的定理：

定理一：

如果N是素数，那么
$ab \equiv 0 (modN) \\ \Rightarrow a\equiv 0 (mod N)\quad or \quad b \equiv0(modN)$

定理二：

如果N是素数
$ab \equiv 0 (modN) \\ \Rightarrow ax \equiv 1(mod N)对于所有的0<a<N \\ 有一个唯一的解（modN) \\ 这个解就是乘法逆元(multiplicative inverse) 其中满x满足:0<x<N$
定理三：

如果N是素数
$X^2 \equiv a (modN) 对于所有的 0<a<N \\ \Rightarrow 有两个解或者没有解$

0x06 证明方法

证明数据结构分析结论的最常用的方法是归纳法和反证法(偶尔不得已也是用胁迫式证明（proof by intimidation)。证明一个定理不成立的最好方法是举出一个反例

归纳法证明

归纳法进行证明有两个标准的部分

证明基准情形（base case）
- 就是确定定理对于某个(某些)小的(通常是退化的)值的正确性
归纳假设(inductive hypothesis)
- 它指的是假设定理对直到某个有限数K的所有情况都是成立的。然后使用这个假设证明定理对下一个值(通常是k+1)也是成立的至此定理得证(k是在有限的情况下)

举例证明：斐波那契数列
$F_0=1,F_1=1,F_2=2,F_3=3,F_4=5,F_5=8........,F_i=F_{i-1}+F_{i-2} \\ 满足对i\geq1 有F_i(5/3)^i。(有些规定F_0=0，这只不过将级数做一次平移)为了证明这个不等式 \\ 一:基准情形 F_1=1 <5/3 ,F_2=2<25/9 得证 \\ 二:归纳假设定理对于i=1,2,3.....,k 成立，证明定理正确就是归纳 \\ 为了证明定理,我们需要证明F_{K+1}=(5/3)^{K+1} \\ F_{k+1}=F_k+F_{k-1} 等号右边 \\ \Rightarrow F_{k+1}<(5/3)^k+(5/3)^{k-1} \\ \quad \quad<(3/5)(5/3)^{k+1}+(3/5)^2(5/3)^{k+1} \\ \quad \quad<(3/5)(5/3)^{k+1}+(9/25)(5/3)^{k+1} \\ 化简: F_{k+1}<(3/5+9/25)(5/3)^{k+1} \\ \quad \quad =(24/25)(5/3)^{k+1}<(5/3)^{k+1} \\ 得证$

定理：

$N \geq 1，则 \sum_{i=1}^Ni^2=\frac{N(N+1)(2N+1)}{6} \\ 证明：基准情形 N=1时满足,设\quad定理1\le k \le N成立 \\ \Rightarrow \sum_{i=1}^{N+1}i^2=\sum_{i=1}^{N}i^2+(N+1)^2 \\同理 \\右边=（N+1）[\frac{N(2N+1)}{6}+(N+1)] \\ \Rightarrow（N+1）\frac{2N^2+7N+6}{6} \\ \Rightarrow \frac{(N+1)(N+2)(2N+3)}{6} \\ 得证 \sum_{i=1}^{N+1}i^2=\frac{(N+1)[(N+1)+1][2(N+1)+1]}{6}$

0x07 总结

已经很久没有复习数学了，这一次复习已经把很多数学知识捡起来了，心累。

算法之数学

0x01 开坑：简介

问题一

问题二

0x02 指数

0x03 对数

定义1

定理1

定理2

0x04 级数

几何级数

算数级数

0x05 模运算

0x06 证明方法

归纳法证明

定理：

0x07 总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读