数据结构、数据算法知识框架笔记总结
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
线性勘探法
左右平方找
二次勘探法
随机勘探法
分类
开放地址
多个散列函数一起用
再散列函数
冲突处理
求模取余法（最经典）
取关键字或关键字的某个线性函数值为散列地址。;即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数）
直接寻址法
分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，;这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，;如果用后面的数字来构成散列地址，则冲突的几率会明显降低;数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
数字分析法
取关键字平方后的中间几位作为散列地址
平方取中法
将关键字分割成位数相同的几部分，最后一部分位数可以不同，;然后取这几部分的叠加和（去除进位）作为散列地址。
折叠法
选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。
随机数法
除留余数法
构造方法
查找复杂度为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
公理
事件A、B，P(A)gt;0，则
条件概率
事件A、B满足P(AB)=P(A)P(B)，则称A与B相互独立
性质
独立
加法
减法
乘法
全概率
贝叶斯
公式
概率
随机事件与概率
定义
分布函数
r.v的可能取值是有限多个或可数无穷多个
函数分布
离散型r.v
密度函数
公式法
定义法
连续型r.v
随机变量X（random variable，记r.v）
r.v 分布律
数学期望（均值）
方差
0-1分布
二项分布
泊松分布
几何分布
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;
正态分布
指数分布E(λ)
常用分布
随机变量与概率分布
边缘分布
条件分布
分布
表格表示
概率分布（分布律）
二维 nbsp; nbsp;离散型r.v
fx(x)
fy(y)
边缘密度
条件密度
二维 nbsp; nbsp;连续型r.v
分布律
充要条件
独立性
二维 均匀分布
二维 正态分布
二维r.v
多维随机变量及其分布
离散型
连续型
数学期望
计算公式
协方差nbsp;
ρxy
不相关
相关系数
随机变量的数字特征
χ2分布（卡方分布）
t分布
F分布
数理统计
点估计
步骤
矩估计法
最大似然法
估计量的求法
参数估计
概率论与数理统计
行列式
矩阵
向量
线性方程组
特征值、特征向量
二次型
线性代数
单调增
单调减
单调性
奇函数
偶函数
奇X奇=偶
奇X偶=奇
偶X偶=偶
奇函数复合奇函数==gt;奇函数
偶函数复合偶函数==gt;偶函数
偶函数复合奇函数==gt;偶函数
对称原点的数集X上的函数f(x)可分解为一奇一偶函数之和
定理
奇偶性
周期性
充分条件
有界性
连续
左连续
连续函数经过四则运算后也连续
四则运算
两个连续函数复合后仍然连续
复合函数连续性
基本初等函数在其定义域内都是连续的
基本初等函数
初等函数在其定义域的区间内都是连续的
初等函数
初等函数连续性
有界性定理
最值定理
介值定理
零点定理
闭区间连续函数性质
可去间断点
跳跃间断点
第一类间断点
第二类间断点
间断
与可导的关系
左、右导数
可导必连续，连续不一定可导
可导与连续
函数的微分
高阶导数
切线斜率
几何意义
可导则可微
可导与可微的关系
运算法则
基本初等函数导数
变限积分求导
n阶导数运算法则
常见初等函数n阶导数
隐函数求导
幂指函数求导
反函数一阶二阶导数
可导点处极值的必要条件
第一充分条件
第二充分条件
极值
1
2
3
4
求法
最值
判定
凹凸性
二阶可导点处拐点的必要条件
拐点
驻点
水平渐近线
铅直渐近线
斜渐近线
渐近线
曲率
曲率圆
导数
微分
存在充要条件
数列极限
初等数学 恒等变换
极限存在但不为0的因式 可以提出因式另求
等价无穷小替换
洛必达法则
佩亚诺余项泰勒公式
夹逼定理
极限四则运算 重要极限等
求解方法
函数极限
唯一性
推论
保号性
比较
与极限的关系
无穷小
无穷大
1.
2.
无穷小和无穷大的关系
注：
单调有界定理
注：法则对于数列极限和函数极限都成立
判断极限存在法则
nbsp;
重要极限和等价无穷小
5
替换定理
等价无穷小替换等价无穷小的充要条件
法则1
法则2
lt;bgt;洛必达法则lt;/bgt;
常用函数x=0处展开公式
极限
函数
高等数学
数据结构、数据算法知识框架笔记总结
0 条评论
回复 删除
下一页
