数据结构、数据算法知识框架笔记总结
2022-10-28 17:45:28 0 举报AI智能生成
数据结构、数据算法知识框架笔记总结
作者其他创作
大纲/内容
查找
基本概念
静态查找
只做查找操作
动态查找
在查找过程中同时插入查找表中不存在的数据元素，;或是删除已经存在的某个数据
线性结构
顺序查找
思想与概念
顺序查找属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，;依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功
代码
代码1
优化
过程
分支主题
评价
查找成功时的平均查找长度为： ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
顺序查找的时间复杂度为O(n)。
顺序查找适合于存储结构为顺序存储或链接存储的线性表。
折半查找
概念与思想
二分查找即折半查找，属于有序查找算法。;用给定值value与中间结点mid的关键字比较，若相等则查找成功；;若不相等，再根据value与该中间结点关键字的比较结果确定下一步查找的子表;大于mid，low =mid+1；小于mid，high=mid-1
代码
非递归
递归
过程
分支主题
评价
元素必须是有序的，如果是无序的则要先进行排序操作。
时间复杂度:最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)
查找长度：与二叉排序树一样
nbsp;成功：ASL=(1*1+2*2+3*4+4*3)/10=29/10;;失败：ASL=(3*5+4*6)/11=39/11;（第3层下面有5个）
分块查找
概念
分块查找又称索引顺序查找，它是顺序查找的一种改进方法。吸取了顺序查找和折半查找的优点
思想
将n个数据元素quot;按块有序quot;划分为m块（m ≤ n）。每一块中的结点不必有序，;但块与块之间必须quot;按块有序quot;；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；;而第2块中任一元素又都必须小于第3块中的任一元素，……
过程
step1 先选取各块中的最大关键字构成一个索引表；;step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；;然后，在已确定的块中用顺序法进行查找。
评价
时间复杂度：O(log(m)+N/m)
查找长度:ASL:log2(b＋1)＋(s+1)/2，n长度的表分为b块，每块s条记录;外面折半，里面顺序
树形结构
二叉排序树（树与二叉树中详述）
二叉平衡树（树与二叉树中详述）
B树，B+树
B和B+树都能有效地支持随机查找
散列结构
散列表
概念
哈希也称为散列，哈希查找是一种按关键字编址的快速检索方法
不同之处
1.哈希查找是通过对记录的关键字值进行某种运算，直接求出记录的地址；; 2.快----关键字到地址的直接转换，无需反复的比较; 3.核心不在于如何“比较”，而在于如何“计算”; 4.最能体现计算机科学精髓的查找方法
思想
核心是设计哈希函数，并构造哈希表
查找过程
1.由给定的关键字值Key，根据哈希函数计算出对应的哈希地址H（Key）; 2.根据H（Key）直接找到该记录的存储位置
冲突处理
链地址法
链地址法：将哈希值相同的数据存在一个链表中；;查找哈希表时，当查找这个链表是，必须采用线性查找方法
开放地址
一旦发生冲突，就去寻找下一个空的散列地址，只要散列表只够大，总能找到位置存储
分类
线性勘探法
找不到就往后+i
映射次数：n(n-1)/2
查找：n(n+1)/2
二次勘探法
f(key) = (f(key)+di) MOD m;nbsp;(di = 1^2, -1^2, 2^2, -2^2,……, q^2, -q^2, q lt;= m/2);di取值可能为1,-1,4,-4,9,-9,16,-16,...k*k,-k*k(klt;=m/2);
左右平方找
随机勘探法
再散列函数
多个散列函数一起用
构造方法
求模取余法（最经典）
直接寻址法
取关键字或关键字的某个线性函数值为散列地址。;即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数）
数字分析法
分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，;这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，;如果用后面的数字来构成散列地址，则冲突的几率会明显降低;数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
平方取中法
取关键字平方后的中间几位作为散列地址
折叠法
将关键字分割成位数相同的几部分，最后一部分位数可以不同，;然后取这几部分的叠加和（去除进位）作为散列地址。
随机数法
选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。
除留余数法
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, plt;=m。;不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，;一般取素数或m，若p选的不好，容易产生同义词。
性能分析
查找复杂度为O(1)
查找长度影响因素
散列函数是否均匀
处理冲突方法
散列表的装填因子a=表中记录数n/散列表长度m
查找长度计算：
链地址
查找成功时： ASL=（4*1+3*2+1*3）/8=13/8（映射到的链长之和）;查找不成功时：ASL=(7×1+1×2+2×3+1×4 )/11=19/11（映射到的链尾端NULL的链长之和。）;
线性勘查
分支主题
失败时有空地址时
分支主题
分支主题
查找失败构思小结：遇到有空地址不放关键字的时候，会停止继续往下查找，如图中的地址2和地址4；
注意
设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择;小于等于m的最大素数;
效率指标
平均查找长度
查找成功
查找失败
概率论与数理统计
随机事件与概率
随机事件
包含
相等
交
并
差
互斥
对立
运算规律
交换律
结合律
分配律
对偶律
概率
公理
任意事件A，有P(A)≥0
必然事件Ω，有P(Ω)=1
两两互斥的可数无穷个事件A1,A2...An,... 有P(A1∪A2...∪An∪...=P(A1)+P(A2)+...+P(An)+...，称P(A)为事件A的概率
条件概率
事件A、B，P(A)gt;0，则
独立
事件A、B满足P(AB)=P(A)P(B)，则称A与B相互独立
性质
性质
公式
加法
减法
乘法
全概率
贝叶斯
随机变量与概率分布
随机变量X（random variable，记r.v）
分布函数
定义
性质
离散型r.v
定义
r.v的可能取值是有限多个或可数无穷多个
函数分布
连续型r.v
定义
分布函数
密度函数
函数分布
公式法
定义法
常用分布
0-1分布
r.v 分布律
数学期望（均值）
方差
二项分布
r.v 分布律
数学期望（均值）
方差
泊松分布
r.v 分布律
数学期望（均值）
方差
几何分布
r.v 分布律
数学期望（均值）
方差
均匀分布
lt;bgt;lt;ugt;连续型lt;/ugt;lt;/bgt;nbsp; nbsp;r.v 分布律
密度函数
分布函数
数学期望（均值）
方差
指数分布
lt;bgt;lt;ugt;连续型nbsp;lt;/ugt; nbsp;lt;/bgt;r.v 分布律
密度函数
分布函数
数学期望（均值）
方差
正态分布
r.vnbsp;
密度函数
分布函数
标准正态
密度函数
分布函数
一般正态转换标准正态
数学期望（均值）
方差
性质
均匀分布U(a,b)
指数分布E(λ)
正态分布N(μ,σ^2);
多维随机变量及其分布
二维r.v
定义
X=X(ω),Y=Y(ω)
分布
分布函数
F(x,y)=P{X≤x,Y≤y} , -∞lt;xlt;+∞,-∞lt;ylt;+∞
边缘分布
Fx(x)=P{X≤x} , Fy(y)=P{Y≤y}
条件分布
二维 nbsp; nbsp;离散型r.v
定义
r.v (X,Y)可能取值为有限个或可数无穷个(xi,yi)
概率分布（分布律）
表格表示
边缘分布
条件分布
二维 nbsp; nbsp;连续型r.v
分布函数
密度函数
边缘密度
fx(x)
fy(y)
条件密度
性质
分布律
分布函数 nbsp; nbsp;F(x,y)
密度函数 nbsp; nbsp;f(x,y)
独立性
充要条件
常用分布
二维 均匀分布
密度函数
性质
二维 正态分布
密度函数
性质
随机变量的数字特征
数学期望
定义
离散型
连续型
性质
方差
定义
计算公式
性质
协方差nbsp;
Cov(X,Y)
公式
性质
相关系数
ρxy
不相关
性质
数理统计
常用分布
χ2分布（卡方分布）
定义
性质
t分布
定义
性质
F分布
定义
性质
参数估计
点估计
估计量的求法
矩估计法
步骤
最大似然法
步骤
线性代数
行列式
矩阵
向量
线性方程组
特征值、特征向量
二次型
高等数学
函数
性质
单调性
单调增
单调减
奇偶性
奇函数
偶函数
定理
奇X奇=偶
奇X偶=奇
偶X偶=偶
奇函数复合奇函数==gt;奇函数
偶函数复合偶函数==gt;偶函数
偶函数复合奇函数==gt;偶函数
对称原点的数集X上的函数f(x)可分解为一奇一偶函数之和
周期性
有界性
充分条件
连续
定义
连续
左连续
在(a,b)内[a,b]连续
四则运算
连续函数经过四则运算后也连续
复合函数连续性
两个连续函数复合后仍然连续
初等函数连续性
基本初等函数
基本初等函数在其定义域内都是连续的
初等函数
初等函数在其定义域的区间内都是连续的
闭区间连续函数性质
有界性定理
最值定理
介值定理
零点定理
间断
第一类间断点
可去间断点
跳跃间断点
第二类间断点
导数
定义
左、右导数
定义
与可导的关系
可导与连续
可导必连续，连续不一定可导
函数的微分
高阶导数
几何意义
切线斜率
可导与可微的关系
可导则可微
公式
运算法则
基本初等函数导数
变限积分求导
n阶导数运算法则
常见初等函数n阶导数
隐函数求导
幂指函数求导
反函数一阶二阶导数
极值
定义
可导点处极值的必要条件
第一充分条件
第二充分条件
最值
定义
求法
1
2
3
4
凹凸性
定义
判定
拐点
定义
二阶可导点处拐点的必要条件
充分条件
驻点
渐近线
水平渐近线
铅直渐近线
斜渐近线
曲率
曲率
曲率圆
微分
极限
数列极限
定义
存在充要条件
函数极限
定义
存在充要条件
求解方法
初等数学 恒等变换
极限存在但不为0的因式 可以提出因式另求
等价无穷小替换
洛必达法则
佩亚诺余项泰勒公式
夹逼定理
极限四则运算 重要极限等
导数
性质
唯一性
保号性
性质
推论
无穷小
定义
比较
与极限的关系
无穷大
无穷小和无穷大的关系
1.
2.
判断极限存在法则
夹逼定理
1.
2.
注：
单调有界定理
注：法则对于数列极限和函数极限都成立
重要极限和等价无穷小
1
2
3
4
nbsp;
分支主题
nbsp;
nbsp;
nbsp;
运算法则
四则运算
1
2
3
4
5
注：
等价无穷小替换等价无穷小的充要条件
替换定理
充要条件
lt;bgt;洛必达法则lt;/bgt;
法则1
1
2
3
法则2
1
2
3
佩亚诺余项泰勒公式
常用函数x=0处展开公式
1
2
3
4
5
0 条评论
下一页
