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