算法之数学

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

算法之数学
学习笔记二：数据挖掘最佳路径--摘自陈旸课程
数学之美
机器学习4：局部加权回归
算法
算法和数据结构 - 开篇
stl 算法自带总汇
哈希里的数学
我在MIT人工智能研究实验室工作一年学到的 5 件事
究竟哪些《见识》，能让我们走得更远1

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 开坑：简介现今对数据处理的都是大量，大集合，所以简介一些离散数学例如：问题一设一组N哥数而要确定...
学习笔记二：数据挖掘最佳路径--摘自陈旸课程
一、数据挖掘的基本流程、十大算法、数学原理 A、分类算法：1、c4.5这个算法是得票最高的算法，可以说是十大算法之...
数学之美
数学之美，人民邮电出版社--吴军著一直数学没有学好，现在要开始补算法课，顺便把数学之美书也买了，近来把书看...
机器学习4：局部加权回归
参数学习算法，非参数学习算法参数学习算法，用固定的明确的参数进行数据的拟合。比如线性回归。非参数学习算法，使用的...
算法
说起算法，相信大家普遍都听过数学算法，例如：口算，心算等，这些都属于数学算法。不过，今天给大家介绍的算法不是数学算...
算法和数据结构 - 开篇
材料《数据结构与算法之美》 - 极客时间《程序员的数学基础课》- 极客时间《算法导论》方式多遍实现，达到...
stl 算法自带总汇
算法，问题之解法也。以有限的解决逻辑或数学上的问题，这一专门科目我们称为算法。大学信息相关教育里面，与编程最有直接...
哈希里的数学
哈希里的数学【本文由赞我(zaneds.com)独家冠名】哈希算法，是由数学算法的构成的，这毋容置疑。什么算法...
我在MIT人工智能研究实验室工作一年学到的 5 件事
原文来自于：算法与数学之美原文链接：https://mp.weixin.qq.com/s/vQ8S1EThOVd...
究竟哪些《见识》，能让我们走得更远1
作者：吴军，原腾讯副总裁，当前Google中日韩文搜索算法的主要设计者，著有《数学之美》、《浪潮之巅》和《文明之光...