算法数据结构
2019-07-23 10:46:05 0 举报AI智能生成
数据结构以及算法原理
作者其他创作
大纲/内容
基础篇二
为什么redis一定要用跳表来实现有序集合?
跳表：链表加多级索引的结构就是跳表，一种动态数据结构，支持快速插入，删除，查找操作
利用二分法实现链表的高效查询，时间复杂度Ologn
通过时间换空间的方式，获取更高的效率，可以通过减少索引节点密度来减少空间复杂度，对于存储对象而言，索引内存开销可以不计
高效动态插入和删除
插入需要查询Ologn,插入时间O1，删除需要查询Ologn,删除节点，并删除索引
跳表索引动态更新
极端情况跳表可能退化成单链表的情况
插入数据时，通过随机函数生成k值，把节点添加到k级索引中维护“平衡性”
为什么选用跳表，不选用红黑树
跳表按区间查找数据比红黑树效率高
跳变更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗
散列表：文档单词拼写功能如何实现？
散列冲突
开放寻址法
根据hash函数计算存放位置，如果已存在，依次寻找空
查找同样，根据映射，没找到就依次寻找
删除元素：通过标记为deleted,当查询时候遇到标记就跳过
缺点：数据大，冲突多，检测时间久，极端情况On
上述为线性探测方法，还有二次探测（冲突探测下标增量为平方，1,4,9等），双重散列
衡量冲突的量：装载因子 =装入元素个数/散列表长度
链表法
再hash
构造多个hash算法，冲突再计算
建立公共溢出区
将hash表分为基本表，溢出出表，和基本表发生冲突，填入溢出表
怎么设计高效的散列函数
散列函数不能太复杂、生成的值要尽可能随机并均匀分布
解决方法：分析数据的特点，选取随机的数据部分作为key
直接寻址、平方取中、折叠法、随机数法、ASCLL码
装载因子不能过大、进行扩容，数据少时进行缩容
数据量大时、并不能一次性搬移数据
数据超过阈值、进行空间申请
插入数据时插入到新的散列表中，同时从旧的散列表取一个值添加到新的散列表中
选择冲突解决办法
开放寻址适用场景
数据量小，装载因子小的时候，ThreadLocalMap 使用的开放寻址解决散列冲突
链表法
比较适合存储对象，大数据量的散列表，更加灵活、支持更多优化策略，比如红黑树替代链表
设计要求
支持快速查询、插入、删除操作
内存占用不合理
性能稳定、极端情况下，散列表性能不能退化到无法接受的情况
解决方法
设计一个合适的散列函数
定义装载因子阈值，设计动态扩容
选择合适的散列冲突解决方法
散列表和链表一起使用
LinkedHashMap
由散列表+单链表+双链表实现
如何查找、如何删除、如何添加
添加操作与LRU算法一致
散列表动态数据，高效的数据插入、删除、查找，但是无法支持快速的顺序遍历
hash算法
hash算法需要满足
不能逆向推导数据
对输入的数据敏感，改变一位，hash值不同
散列冲突小
执行效率要高效
应用途径
安全加密、数据校验、散列函数、负载均衡、数据分片、分布式存储
hash在分布式系统中有哪些应用
负载均衡的处理方法：通过hash算法对客户端ip地址或者会话ID计算hash值，然后取模计算服务器列表大小，使得通过IP地址路由到服务器不变
数据分片：统计1T日志文件中“搜索关键字”出现的次数、寻找1一张图片书否存在库中
分布式存储-一次性哈希算法
二叉树
定义
节点的高度、节点的深度、节点的层数、树的高度、完全二叉树、满二叉树
存储
链式存储、顺序存储
数组可用来存储一颗完全二叉树，最节约空间
二叉树递归遍历
二叉查找树的查找、删除、增加
删除操作涉及三种可能：删除节点为叶子节点、删除节点有两个节点、删除节点有一个子节点
二叉树怎么解决键相同情况
通过链表或者支持动态扩容的数组，存放相同的值到一个节点上
直接把它当成大于节点的数，存放到右边叶子
为什么要用二叉树、不用散列表替代二叉树？
1、散列表数据无序存储，在二叉查找树中只需要中序遍历就可以实现数据的有序
2、散列扩容耗时多，遇到散列冲突性能不稳定，在工程中用平衡二叉树解决性能不稳定情况，使得时间复杂度稳定在Ologn
3、散列表设计复杂，考虑情况多，因装载因子浪费空间
红黑树
定义
广义理论：二叉树任意一个节点左右树的高度相差不能大于1
狭义理论要求：红黑树中不保证树的高度相差为1，只要树的高度为Ologn
根节点的颜色是黑色
每个叶子都是黑色的空节点、叶子节点不存数据
从节点到叶子节点不能有连续两个红色节点
每个节点，从该节点到其可达的叶子节点的所有路径，都包含相同的黑色节点
平衡：让树左右看起来对称，比较平衡，保证整棵树高度相对低，执行插入、删除、查找的效率高
递归树
解决递归时间复杂度分析
堆排序
定义：堆是一种完全二叉树
特性:节点的值大于等于其子节点的值
堆排序两步骤：建堆、排序
插入元素：从下往上堆化
删除元素：从上往下堆化
复杂度：建堆时间复杂度为On,排序为Onlogn,整体复杂度为：Onlogn
堆得应用
优先级队列
根据优先级大小先后出队列，可以利用堆实现优先级队列
赫夫曼编码、图的最短路径、最小生成树
定时器
利用堆存储定时任务，计算堆顶与下一次定时任务时间间隔，不需要定时轮询
获取top 100
利用堆维护100元素的小顶堆
静态数据：直接把元素与堆顶比较，如果小于堆顶不处理，大于堆顶就删除堆顶，然后堆化
动态数据：如果有两个操作：添加数据、访问当前前100数据，可维护堆
获取中位数、统计程序接口99%的响应时间
图的表示
和二叉树一样，是一种非线性结构
顶点、边、度、入度、出度、带权图、邻接矩阵、邻接表
邻接矩阵与邻接表的优劣势
邻接矩阵：在存储方面比较浪费空间，查询效率高，方便矩阵运算
邻接表：存储每个顶点对应一个链表，节约空间，不便查找，查询效率没邻接矩阵高，但是可以通过平衡二叉树，跳表、散列表进行优化。
深度和广度优先搜索（六度空间理论）
广度优先
时间复杂度OE(边数)
空间复杂度OV（顶点数）
深度优先
同上
广度优先利用队列实现，深度优先利用栈实现
字符串匹配
BF(Brute Force 暴力匹配)
主串与模式串，模式串与主串一位一位对应匹配
时间复杂度（On*m）
RK（Rabin-Karp）
利用hash算法计算出字符串所有子串的hash值，与模式串hash值比较
时间复杂度On，需要On处理hash值，On比较
BM（Boyer-Moore）
比较复杂的字符串匹配，但是匹配效率高、在文本编辑器中应用较多
核心思想是在模式串与主串不匹配时候，模式串往后多滑动几位，减少不必要字符匹配
主要有两种构建规则：坏字符规则、好后缀规则
KMP
和BM算法很相似，遇到坏字符，把模式串多移动几位
时间复杂度O(n+m)
AC自动机
基于Trie 树的改进算法、存在失败指针
构建步骤
构建AC自动机
构建Trie树
构建失败指针
AC自动机中匹配主串
Trie树
也名字典树：树形结构、专门处理字符串匹配的数据结构，快速查找某个字符串
Trie 树中查找字符串的时间复杂度：0(n)
Trie树是一种时间换空间的思路，非常耗空间
解决思路：使用散列表、红黑树
Trie对处理的字符串要求多
字符串包含字符既不能太大
要求字符串前缀重合较多
自己实现Trie逻辑
指针对数据块不连续，性能会受到影响
应用
自动输入补全、输入法自动补全、IDE编译器自动补全
贪心算法
哈夫曼压缩编码、最小生成树、单源最短路径、背包问题
难点：把问题抽象成贪心算法模型
思想：贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解
适用范围
整体最优解可以通过局部最优解求出
.一个整体能够被分为多个局部，并且这些局部都能够求出最优解
步骤
从问题的某个初始解出发
采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模
将所有部分解综合起来，得到问题的最终解
实战篇
入门
算法作用
写出性能更优代码
算法，扩展自己的思维方式
可以训练大脑的思考能力
有利于框架阅读与设计思想
算法学习困难
项目中涉及少
容易忘记
无法灵活运用
算法与数据结构之间的关系
数据结构是为算法服务的，算法作用在特定的数据结构上
怎么学
多思考、多动手，边学边练、重复写、多问、多互动
首先掌握算法复杂度分析，大力气肯，平衡时间与空间资源
需要能沉下心学习，知识需要不断沉淀
打怪升级法，不断培养自己的兴趣与经验
每篇文章写学习笔记，每周实现一次该周代码
学习算法的由来、特性、适用场景、他能解决的问题
学习目的
建立时间复杂度、孔家复杂度意识，写出高质量代码
能够设计基础架构，提升编程技能，训练逻辑思维
提升看待问题的深度，开拓解决问题的角度
推荐书目
《算法第四版 java》
《剑指offer》
《编程珠玑》
《编程之美》
《数据结构和算法分析》
《算法导论》
基础篇一
复杂度分析
如何分析、统计算法执行效率和资源消耗
什么是复杂度分析
数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”
因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度
复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。
复杂度分析必要性
和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点
掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本
如何进行复杂度分析
大O 表示法
算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。
以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽略这些项。
常用复杂度级别
多项式阶
O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶）
非多项式阶
O(2^n)（指数阶）、O(n!)（阶乘阶）
对数阶推导公式
log3n 就等于 log32 * log2n 通过换底公式推导
2x=n :当 循环x 次 >=n 时跳出循环
时间复杂度分析
最好、最坏、平均、均摊时间复杂度
平均时间复杂度
代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。
均摊时间复杂度
代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；
低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。
数组为什么从0开始编号
如何实现随机访问
线性表
连续的内存空间和相同类型的数据
数组越界问题
java中根据编译器的区别，gcc中默认开启-fno-stack-protector（栈保护功能），i 无论定义在前还是后，都会在array后压入栈
插入与删除优化
数组无序要求插入时,可替换当前元素，并把当前元素添加在后边
数据删除时避免频繁移动数据，可以把已删除的元素进行标记，当空间不足时再删除数据，根据垃圾回收机制
数组优势
集合框架无法储存基本数据类型
如果知道数据大小，数据操作简单可以使用数组
计算机为什么使用0
减少指令的计算
a[k]_address = base_address + K*type_size，从1开始的话 k-1
如何实现LRU（Least Recently Used） 缓存淘汰算法
链表中删除节点两种情况，单链表与多链表执行效率不一样
删除值等于某值节点
删除给定指针指向的节点
程序设计优化思想
以空间换时间的方式进行优化
数组简单易用，对于cpu缓存很友好，因为链表不是连续存储，cpu缓存的是数据块
实现LRU
数据存在缓存中需要把数据删除、添加到队首
没有存在缓存中
缓存未满，插入到头部
缓存满了，删除尾节点，新的节点插入头部
单链表实现回文串思路
练习LetCode 206 、141、21、19、876
更好的写出链表算法
理解指针或引用的含义
警惕指针丢失与内存泄漏
利用哨兵简化实现难度
留意边界条件的处理
链表为空
链表只有一个节点
链表有两个节点
代码逻辑在处理头节点和尾节点
画图辅助思考
多练习，多动手
链表常见操作
单链表反转
快慢指针、前或后部分反转
链表环检测
判断单链表中的环
遍历判断节点是否重复、快慢指针
判断环的出口
从链表head开始到入口点的距离a,与从slow与fast的相遇点到入口点的距离相等
求环上节点数
从相遇点开始，遍历一遍，回到起点
两个有序链表合并
两个指针比较，排序
删除链表倒数n个节点
两个指针等距右移、遍历两遍length-k+1、链表反转
求链表的中间节点
快慢指针
利用栈实现浏览器回退功能
栈：操作受限的线性表，只允许一端插入和删除数据
实现方式：顺序栈、链式栈
复杂度
时间复杂度，最好情况1 最坏情况n
均摊时间复杂度1
临时变量存储，操作系统分配独立的内存空间，使用栈存储方法中的局部变量
在四则计算中的运用
使用两个栈实现，一个存放操作数，一个存储符号，符号入栈时比较栈内符号，优先级低于栈内符号，则出栈运算
利用栈匹配括号的运用
内存空间
代码区
存储方法体的二进制代码，高级（作业）调度、中级（内存调度）、低级（进程调度），控制代码区执行代码的切换
静态数据区
存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。
动态数据区
栈区、堆区
栈：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收
堆：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据
Letcode 编程练习
20,155,232,844,224,682,496
队列在线程池等有限资源池的运用
队列：操作受限的线性表，只允许一端插入和另一端删除数据
也有两种实现方式
数组实现的顺序队列，链表实现的链式队列
基于数组队列容量满了后需要扩容，如果head 前边还有空闲，tail ==n 无法添加元素，就需要扩容
可以复制数据，时间复杂度n
直接移动数据，数组顺序移动，时间复杂度只有1
利用循环链表解决这个问题
空、满判断
数组实现
空 head==tail 满 tial==n
链表实现
空 tail==head 满 (tail+1)%n=head
阻塞队列
应用在生产者消费者模型中
并发队列
关于线程安全，使用并发队列，可以直接给enqueue() 、dequeue()加锁 .但是锁粒度大、并发度比较低。
可以使用基于数组的循环队列，利用CAS原子操作，实现高效并发。
任务请求线程资源、数据库连接池
基于链表的无界队列
任务太多，等待时间太长，不符合
基于数组有界队列
请求超过队列大小，请求被拒绝
主要是能找到最合理的队列大小
递归：如何用三行代码找到“最终推荐人”？
递归需要满足三个条件
一个问题能分解为多个问题
分解成多个问题后，除了规模不同，求解思路相同
存在递归终止条件
防止堆栈溢出
解决方式：1、转换成非递归 2、使用static 替换nostatic 3、增大堆栈大小值
警惕重复计算
可以使用散列表，把每次递归的结果存储起来
递归缺点
需要的时间复杂度、空间复杂度大、堆栈溢出、重复计算
改写递归代码，将递归代码改成非递归代码
递归调试方法
打印日志发现递归值、结合条件断点进行调试
为什么插入排序比冒泡排序更受欢迎
排序种类繁多
最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。
比如猴子排序、睡眠排序、面条排序等。
如何分析一个排序算法
算法的执行效率
最好、最坏、平均情况时间复杂度
时间复杂度的系数、常数、低阶
比较次数和交换次数
排序算法的内存消耗
排序算法的稳定性
稳定排序算法，可以保持金额相同的两个对象，在排序之后前后顺序不变（应用在按照订单金额排序，金额相同按照下单时间排序）
冒泡排序
原地排序算法、相邻相等元素不交换、复杂度 最好 0n 最坏 0n2
概率论方法分析时间复杂度分析
通过“有序度、逆序度”概念分析
有序度：数组中有序对的个数，逆序度=满有序度-有序度
最坏情况：有序度为0，要进行n*(n-1)/2次交换，平均为n*(n-1)/4次交换，平均时间复杂度0n2
插入排序
原地排序、是稳排序算法、时间复杂度最好On,最坏On2,平均复杂度为On2
选择排序
原地排序、是一种不稳定排序、时间复杂度最好On2,最坏On2,平均复杂度为On2
正是因为排序不稳定，所以相对于插入排序，冒泡排序效率低一点
插入排序与冒泡排序比较
冒泡排序因为交换数据需要赋值3次，而插入排序数据移动只需要赋值一次
快排与归并排序
归并排序，选取中间点
归并是否稳定取决于合并时相同元素位置是否变化决定
时间复杂度是：Onlogn、空间复杂度On
快排，随机选择点，然后大小放两边
快排是不稳定排序，空间复杂度O1,时间复杂度Onlogn,极端情况会出现On2，所以一般使用快排
都采用分治思想，都通过递归实现，快排理解递推公式、merge合并函数，理解快排理解递推公式与partition分区函数
快速排序、递归排序、寻找第k大的数
桶排序（ On）、计数排序(On+k)、基数排序 （Odn）
桶排序
适用场景：适合在外部排序中使用，比如需要读取10G数据，内存只有300M的情况
计数排序
适合用于粒度比桶排序小的，范围小的，并且是正整数的情况
基数排序
适用于范围大，而且存在梯度层次情况，比如比较电话号码情况
如何实现一个通用、高性能排序函数
线性排序时间复杂度比较低，但是适用场景比较特殊，需要写通用排序不能选线性排序
快速排序为什么经常使用？
由于时间复杂度低，空间复杂度On，只是最坏情况On
优化方式：三数去中、随机法
递归排序的时间复杂度低，但是空间复杂度On
应用级排序：通过混合使用排序方式实现
c 语言的qsort实现
先使用归并，用空间换时间的方式，当数据量太大采用快排
快排实现使用三数取中法
在快速排序中，排序区间小于4采用插入排序
小规模排序，On2 不一定比Onlogn 执行时间长，数据量小可以选择插入排序，也可以采用哨兵来简化代码，优化性能
二分查找
如何使用最省内存的方式实现快速查找功能？
二分查找效率高，时间复杂度Ologn
要求有序的数组数据结构，适合规模比较大，经常查询，没有频繁的数据插入、删除操作的情况
注意 循环条件的退出、mid 取值、low和high的更新
可使用循环与递归实现二分查找
散列表、二叉树能解决快速查找动态数据结构，但是需要比较大额外的内存空间
leetcode 33
二分查找的变式,针对重复情况
查询第一次出现的值
查询最后一次出现的值
查询第一次比特定值大的数
查询最后一个比特定值小的数
高级篇
0 条评论
下一页
