简介
在开始正式的算法学习之前，先学一点数学的基础知识，有助于后面的学习。当然你已经具备这些知识，可以跳过这节内容。本人建议：即使一下内容你都学过，也温故一下。该数学基础知识一共包括四个部分，分别是：
级数（用于时间和空间复杂度的计算）
离散数学相关知识
概率论相关知识
线性代数相关知识
第一部分 级数
这部分内容在高等数学里的函数极限那章介绍的比较详细，我就挑我们常用的几种进行介绍。需要进一步学习的可以去找同济版高等数学参考学习。
1. 求和公式及其性质
线性性质
∑k=1n(cak+bk)=c∑k=1nak+∑k=1nbk
线性性质可以用来对项中包含渐进记号的和式求和。
∑k=1nΘ(f(k))=Θ(∑k=1nf(k))
等式中，左边的Θ
符号作用于变量κ
，而右边的Θ
则作用于n。
等差级数
∑k=1nk=1+2+⋯+n=12n(n+1)=Θ(n2)
平方和与立方和
∑k=0nk2=n(n+1)(2n+1)6
∑k=0nk3=n2(n+1)24
几何级数 (指数级数)
∑k=0nxk=xn+1−1x−1
当n趋于无穷大且|x|<1时，上述公式可修改为
∑k=0∞xk=11−x
调和级数
Hn=1+12+13+⋯+1n=∑k=1n1k=lnn+O(1)
级数积分与微分
通过对上面的公式进行积分或微分，可以得到其他新的公式。例如对公式六两边同时微分并乘以x，可以得到
∑k=0∞kxk=x(1−x)2
其中，|x|<1
。
裂项级数
∑k=0n−1ak−ak+1=an−a0
乘积
lg(∏k=1nak)=∑k=1nlgak
第二部分 离散数学
1. 集合
集合的几个相关概念
集合：有不同对象聚集而成的一个整体，称其中的对象为成员或元素。
∅：表示空集合，即集合中不包含任何元素。
Z：表示整数集合。
R：表示实数集合。
N：表示自然数集合。
子集：若集合B包含集合A的所有元素，则称集合A是集合B的一个子集。
真子集：若集合A是集合B的一个子集，但集合A不等于集合B，则称集合A是集合B的一个真子集。
集合的基数、有限性、可数性：集合中元素的个数称为集合的基数；若一个集合的基数时自然数，则称这个集合是有限的，否则是无限的；若一个无限集合可以与自然数集合N构成一一对应，则该集合是可数无限的，否者是不可数的。
n集合与k子集：一个包含n个元素的集合称为n集合。称1集合为单元集。如果一个集合的子集包含k个元素，则称其为k子集。
集合的几个常见公式
空集律：
A∩∅=∅
幂等律：
A∪∅=A
交换律：
A∩A=AA∪A=A
结合律：
A∩(B∩C)=(A∩B)∩CA∪(B∪C)=(A∪B)∪C
分配律：
A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)
吸收律：
A∩(A∪B)=AA∪(A∩B)=A
德摩根律：
A−(B∩C)=(A−B)∪(A−C)A−(B∪C)=(A−B)∩(A−C)A∩B¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=A¯¯¯¯∪B¯¯¯¯A∪B¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=A¯¯¯¯∩B¯¯¯¯A1∩A2∩⋯∩An¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=A1¯¯¯¯¯¯∪A2¯¯¯¯¯¯∪⋯∪An¯¯¯¯¯¯A1∪A2∪⋯∪An¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=A1¯¯¯¯¯¯∩A2¯¯¯¯¯¯∩⋯∩An¯¯¯¯¯¯
2. 关系
相关概念
二元关系： 集合A与B上的二元关系R是笛卡尔积A×
B的子集。(a,b)∈R
有时写成aRb
。
自反： ∀a∈A,aRa,
则二元关系R⊆A×A
是自反的。
反自反： ∀a∈A,(a,a)∉R,
则二元关系R⊆A×A
是反自反的。
对称： ∀(a,b)∈A,aRb→bRa,
则二元关系R⊆A×A
是对称的。
反对称： ∀(a,b)∈A,(aRb)∩(bRa)→a=b,
则二元关系R⊆A×A
是反对称的。
传递 ： ∀(a,b),(b,c)∈A,(aRb)∩(bRc)→(aRc),
则二元关系R⊆A×A
是传递的。
等价关系与等价类： 同时具有自反、对称、传递性质的二元关系是等价关系。所有等价关系中，所有等价于a的元素的集合称为a的等价类，用[a]={b∈A:aRb}
。
偏序： 满足自反、反对称和传递性质的二元关系是一个偏序。
全关系、全序与全预序： 满足∀a,b∈A,(aRb)||(bRa)
，那么R称为全关系。若一个偏序关系也是一个全关系，则称为全序或线性序。如果一个全关系具有传递性，则称为全预序。
注：下面用关系矩阵来解释一下上面的几个概念。
⎡⎣⎢⎢⎢⎢⎢1x⋮xx1⋮x⋯⋯⋱⋯xx⋮1⎤⎦⎥⎥⎥⎥⎥
，对角线上全1，该关系是自反的。
⎡⎣⎢⎢⎢⎢⎢0x⋮xx0⋮x⋯⋯⋱⋯xx⋮0⎤⎦⎥⎥⎥⎥⎥
，对角线上全0，该关系是反自反的。
⎡⎣⎢⎢⎢⎢⎢xa⋮bax⋮c⋯⋯⋱⋯bc⋮x⎤⎦⎥⎥⎥⎥⎥
，关于主对角线对称，该关系是对称的（主对角线上元素为任意元素）。
⎡⎣⎢⎢⎢⎢⎢x1⋮00x⋮0⋯⋯⋱⋯01⋮x⎤⎦⎥⎥⎥⎥⎥
，若除主对角线之外存在1，则该元素关于主对角线对称的另一个元素必为0，则该关系是反对称的（主对角线上元素为任意元素）。所以空集具有反自反、对称、反对称性质。
3. 函数
相关概念
定义域与陪域： 给定两个集合A和B，称函数f
是A和B上的二元关系，需满足∀a∈A
有且仅有一个b∈A
使(a,b)∈f
。A称为定义域，B称为陪域。（B可以不对应A中的元素）
像和值域： b=f(a)
，则称b
是f
下a
的像。定义域的像称为值域。
单射： a≠b→f(a)≠f(b)
满射： 值域等于陪域，则该函数为满射。（B中元素一定对应A中元素）
双射： 即是单射又是满射，称为双射。
4. 图
相关概念
有向图： 有向图G是一个二元组（V，E），其中V是有限集，二E是V上的二元关系。
无向图： 无向图G=（V，E），边集E由无序的顶点对组成，而不是有序对。无向图中不允许存在自环。
度： 在无向图顶点的度是指关联该顶点的边的数目。在有向图中，顶点的入度是指进入该顶点的边的数目，顶点的出度是指离开该顶点的边的数目，有向图顶点的度是该顶点的出度、入度之和。
路径： 从顶点u
到顶点u′
的一条长度为k的路径是一个顶点序列<v0,v1,⋯,vk>
，其中u=v0，u′=vk
。 如果从顶点u
到顶点u′
存在一条路径p
，则称是从经过p
可达的。
连通性：如果一个无向图中每个顶点从所有其他顶点都可达的，则称该图是连通的。无向图的连通分量是顶点在“从……可达”关系下的等价类。如果一个有向图中任意两个顶点互相可达，则该有向图是强连通的。有向图的强连通分量是“相互可达”关系下顶点的等价类。
同构： 两个图G=(V,E)
和G′(V′,E′)
是同构的，如果存在一个双射f:V→V′
，使得(u,v)∈E
当且仅当(f(u),f(v))∈E′
。其本质就是边不变化，给顶点重新标记。（换顶点序号）
子图： 如果V′⊆V
且E′⊆E
，则称图G′=(V′,E′)
是G=(V,E)
的子图。
完全图与二分图： 图中每对顶点都邻接的无向图。二分图是一个无向图G=(V,E)
，其顶点集V可以划分为两个集合V1,V2
，且(u,v)→(u∈V1∩v∈V2)||V1,V2
，且(u,v)→(u∈V2∩v∈V1)
。
寄语：想系统的学习算法，基础一定要打好，以上介绍的是最基本的内容。要深入学习算法，例如贝叶斯，拉普拉斯，傅里叶等要深入了解。不光是数学，如果你要研究NLP，那编译原理就必须学的很好，其中语法制导、语义分析非常重要。总之计算机的跨学科性很强，时刻学习，才能避免被淘汰。
注：其他部分明天接着写，争取这几天把算法所需要的基本数学知识介绍完。
5. 树
1. 自由树
占位符
2. 有根树和有序树
3. 二叉树和位置树
第三部分 概率论
1. 排列组合
2. 概率
3. 离散随机变量
4. 几何分布与二项分布
5. 二项分布的尾部
第四部分 线性代数
1. 矩阵与矩阵运算
2. 矩阵的基本性质
---------------------
作者：心理咨询木木
来源：CSDN
原文：https://blog.csdn.net/juejing2271/article/details/75112220
版权声明：本文为博主原创文章，转载请附上博文链接！