算法之数学

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 总结

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

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 219,701评论 6赞 508
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,649评论 3赞 396
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 166,037评论 0赞 356
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,994评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,018评论 6赞 395
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,796评论 1赞 308
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,481评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,370评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,868评论 1赞 319
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,014评论 3赞 338
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,153评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,832评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,494评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,039评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,156评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,437评论 3赞 373
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,131评论 2赞 356