数据结构和算法.pptx

《数据结构和算法.pptx》由会员分享，可在线阅读，更多相关《数据结构和算法.pptx（91页珍藏版）》请在课桌文档上搜索。

1、数据结构和算法,01,为什么要学习数据结构和算法,为什么要学习数据结构和算法,02,如何高效学习数据结构和算法,如何高效学习数据结构和算法,学习技巧：,04,20个常用、基础的数据结构和算法,05,书籍推荐,06,概念：广义上讲，数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法,01,学习基础：高中数学、基本编辑技巧,02,学习重点：复杂度分析,03,如何高效学习数据结构和算法,学习技巧：,01,02,03,04,1.边学边练，适度刷题,2.多问、多思考、多互动,3.打怪升级学习法,4.知识需要沉淀，不要想试图一下子掌握所有,如何高效学习数据结构和算法,20个常用、基础的数据结构和

2、算法,单击此处添加标题,9,300 Million,单击此处输入你的正文，文字是您思想的提炼，为了最终演示发布的良好效果，请尽量言简意赅的阐述观点；根据需要可酌情增减文字，以便观者可以准确理解您所传达的信息。,数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树,算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法,03,复杂度分析,复杂度分析,事后统计法的局限性,1.测试结果非常依赖测试环境,01,2.测试结果受数据规模的影响很大,02,复杂度分析,大 O 复杂度表示法,03,1.公式：T(n)=O(f(n),2.代码的执行

3、时间 T(n)与每行代码的执行次数 n 成正比,3.代码执行时间随数据规模增长的变化趋势，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。,02,01,时间复杂度分析,知识点 最好情况时间复杂度最坏情况时间复杂度平均情况时间复杂度(又称加权平均时间复杂度或者期望时间复杂度)均摊时间复杂度(一种特殊的平均时间复杂度),技巧 1.只关注循环执行次数最多的一段代码2.加法法则：总复杂度等于量级最大的那段代码的复杂度3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积,时间复杂度量级,多项式 1.常量O(1)2.对数阶O(logn)、O(nlogn)

4、3.两个数据规模 O(m+n)、O(m*n)非多项式 1.O(2n)2.O(n!),复杂度分析,空间复杂度,空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。,常见的空间复杂度就是 O(1)、O(n)、O(n2),04,数组,数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。,数组,定义,特点,1.线性表（Linear List）,2.连续的内存空间和相同类型的数据,3.时间复杂度,插入删除O(n)查找O(1),线性表：数组、链表、队列、栈非线性表：二叉树、堆、图,

5、05,链表,链表,LRU 缓存淘汰算法,单击此处添加标题,9,300 Million,先进先出策略 FIFO（First In，First Out）,最少使用策略 LFU（Least Frequently Used）,最近最少使用策略 LRU（Least Recently Used）,单击此处输入你的正文，文字是您思想的提炼，为了最终演示发布的良好效果，请尽量言简意赅的阐述观点；根据需要可酌情增减文字，以便观者可以准确理解您所传达的信息。,1.链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”2.每个结点除了存储数据之外，还需要记录链上的下一个结点的地址，记录下个结

6、点地址的指针叫作后继指针 next 3.第一个结点叫作头结点，头结点用来记录链表的基地址。4.最后一个结点叫作尾结点，尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。5.时间复杂度 插入删除O(1)查找O(n),单链表,链表,循环链表,1.循环链表是一种特殊的单链表,2.尾结点指针是指向链表的头结点,双向链表,1.每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点,链表,链表,双向环链表,链表,链表VS数组,1插入删除：数组O(n)链表O(1),2随机访问：数组O(1)链表O(n),链表,编写链

7、表代码技巧,01,技巧一：理解指针或引用的含义,02,技巧二：警惕指针丢失和内存泄漏,03,技巧三：利用哨兵简化实现难度,04,技巧四：重点留意边界条件处理,05,技巧五：举例画图，辅助思考,06,技巧六：多写多练，没有捷径,链表,常见的链表操作,01,单链表反转,链表中环的检测,02,03,04,05,两个有序的链表合并,删除链表倒数第 n 个结点,求链表的中间结点,06,栈,栈,栈在函数调用中的应用,栈在括号匹配中的应用,56%Option 2,47%Option 4,特性,栈在表达式求值中的应用,1.后进者先出，先进者后出，这就是典型的“栈”结构2.一种“操作受限”的线性表3.用数组实现

8、的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。,30%Option 3,23%Option 1,07,队列,队列,01,1.先进者先出，这就是典型的“队列”2.操作受限的线性表数据结构3.用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。,特性,02,循环队列,03,阻塞队列和并发队列,08,递归,递归,1,4,2,3,1.一个问题的解可以分解为几个子问题的解2.这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样3.存在递归终止条件,递归需要满足的三个条件,怎么将递归代码改写为非递归代码？,递归注意事项,如何编写递归代码？,写递归代码的关键就是找到如何将大问题分解

9、为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码,1.递归代码要警惕堆栈溢出2.递归代码要警惕重复计算,09,排序,如何分析一个“排序算法”,冒泡排序（Bubble Sort）,插入排序（Insertion Sort）,选择排序（Selection Sort）,归并排序（Merge Sort）,快速排序（Quick Sort）,排序,单击此处添加文本具体内容，简明扼要的阐述您的观点。根据需要可酌情增减文字，以便观者准确的理解您传达的思想。,单击此处添加标题,排序,线性排序排序优化,排序,如何分析一个“排序算法”,A,B,C,执行效率,内存消耗,稳定

10、性,执行效率,1.最好情况、最坏情况、平均情况时间复杂度2.时间复杂度的系数、常数、低阶3.比较次数和交换（或移动）次数,内存消耗,1.通过空间复杂度衡量内存的消耗2.原地排序算法，就是特指空间复杂度是 O(1)的排序算法,1.如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变,稳定性,冒泡排序（Bubble Sort）,冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。最好情况时间复杂度O(n)最坏情

11、况复杂度O(n)平均时间复杂度操作原子，比较和交换,排序,有序度：数组中具有有序关系的元素对的个数,逆序度：逆序度的定义正好跟有序度相反,满有序度：完全有序的数组的有序度,公式：逆序度=满有序度-有序度,公式：n*(n-1)/2,推理方式,平均时间复杂度,复杂度O(n),插入排序（Insertion Sort）,将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。最好情况时间复杂度O

12、(n)最坏情况复杂度O(n)平均时间复杂度O(n)操作原子，比较和移动,排序,排序,选择排序（Selection Sort）,01,选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。,02,最好情况时间复杂度O(n),03,最坏情况复杂度O(n),04,平均时间复杂度O(n),排序,归并排序（Merge Sort）,归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。,分治思想,性能分析,重

13、点,01,03,02,04,分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了,分治思想,性能分析,稳定的排序算法最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)空间复杂度是 O(n)，非原地排序,重点,理解递推公式和 merge()合并函数,排序,快速排序（Quick Sort）,1,快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。,2,性能分析,3,重点,原地、不稳定时间复杂度也是 O(nlogn),性能分析,重点,理解递推公式和

14、partition()分区函数,C,基数排序（Radix sort）,B,计数排序（Counting sort）,D,线性时间复杂度可以达到 O(n),A,桶排序（Bucket sort）,排序,线性排序,桶排序（Bucket sort）,桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。,计数排序（Counting sort）,计数排序其实是

15、桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。,基数排序（Radix sort）,基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数

16、据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n)了,排序,排序优化,如何选择合适的排序算法？,如何优化快速排序？,qsort()函数分析,如何选择合适的排序算法？,1.一般都会首选时间复杂度是 O(nlogn)的排序算法来实现排序函数,1.三数取中法2.随机法,原因：O(n2)时间复杂度出现的主要原因还是因为我们分区点选的不够合理。,区分算法,最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。,如何优化快速排序？,10,二分查找（Binary Search）,二分查找（Binary Search）,二分查找针对的是一个有序的数据集合，查找思

17、想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。,时间复杂度O(logn),实现,应用场景的局限性,四种二分查找的变形问题,二分查找（Binary Search）,实现,非递归,递归,容易出错的3个地方,1.循环退出条件2.mid 的取值3.low 和 high 的更新,递归,实现,非递归,二分查找（Binary Search）,应用场景的局限性,1.二分查找依赖的是顺序表结构，简单点说就是数组。,01,2.二分查找针对的是有序数据。,02,3.数据量太大也不适合二分查找。,03,应用场景的局限性,1.二分查找依赖

18、的是顺序表结构，简单点说就是数组。2.二分查找针对的是有序数据。3.数据量太大也不适合二分查找。,二分查找（Binary Search）,四种二分查找的变形问题,变体一：查找第一个值等于给定值的元素,变体三：查找第一个大于等于给定值的元素,变体二：查找最后一个值等于给定值的元素,变体四：查找最后一个小于等于给定值的元素,四种二分查找的变形问题,变体一：查找第一个值等于给定值的元素变体二：查找最后一个值等于给定值的元素变体三：查找第一个大于等于给定值的元素变体四：查找最后一个小于等于给定值的元素,11,跳表（Skip list）,跳表（Skip list）,链表加多级索引的结构，就是跳表时间复杂

19、度O(logn),12,散列表（Hash Table）,散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。,散列表（Hash Table）,顾名思义，它是一个函数。我们可以把它定义成 hash(key)，其中 key 表示元素的键值，hash(key)的值表示经过散列函数计算得到的散列值。散列函数设计的基本要求 1.散列函数计算得到的散列值是一个非负整数；2.如果 key1=key2，那 hash(key1)=hash(key2)；3.如果 key1 key2，那 hash(key1)hash(key2)。著名

20、的哈希算法 MD5、SHA、CRC,散列函数,散列冲突解决方法,开放寻址法（open addressing）线性探测（Linear Probing）二次探测（Quadratic probing）双重散列（Double hashing）链表法（chaining）,散列表（Hash Table）,装载因子：散列表的装载因子=填入表中的元素个数/散列表的长度,散列表（Hash Table）,如何设计散列函数？,1.散列函数的设计不能太复杂。,01,2.散列函数生成的值要尽可能随机并且均匀分布,02,影响：装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。不仅插入数据的过程要多

21、次寻址或者拉很长的链，查找的过程也会因此变得很慢。动态散列表 动态扩容：当装载因子过大时，重新申请一个更大的散列表，将数据搬移到这个新散列表中。动态缩容：随着数据的删除，散列表中的数据会越来越少，空闲空间会越来越多，装载因子小于某个值之后，启动缩容,装载因子过大了怎么办？,散列表（Hash Table）,1.当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。,2.当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过程。,如何避免低效地扩容？,成功,散列表（Hash Table）,1.

22、开放寻址法（当数据量比较小、装载因子小的时候，适合采用开放寻址法。）,2.链表法（基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。）,如何选择冲突解决方法？,成功,散列表（Hash Table）,工业级的散列表应该具有哪些特性？,1.支持快速的查询、插入、删除操作；,3.性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。,2.内存占用合理，不能浪费过多的内存空间；,散列表（Hash Table）,如何实现这样一个工业级散列表呢？,1.设计一个合适的散列函数；,01,2.定义装载因子阈值，并且

23、设计动态扩容策略；,02,3.选择合适的散列冲突解决方法。,03,13,哈希算法,哈希算法,任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法设计优秀哈希算法要求应用范围,从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）,散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；,对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同,哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。,成功,哈希算法,设计优秀哈希算法要求,哈希算法,应用范围,应用一：安全加密,A,应用二：唯一标识,B,应用三：数据校验

24、,C,应用四：散列函数,D,应用五：负载均衡,E,应用六：数据分片,F,哈希算法,应用范围,01,02,应用七：分布式存储,其他:网络协议中的 CRC 校验、Git commit id 等等,应用五：负载均衡,我们可以通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。,1.如何统计“搜索关键词”出现的次数？,难点 第一个是搜索日志很大，没办法放到一台机器的内存中。第二个难点是，如果只用一台机器来处理这么巨大的数据，处理时间会很长。解决思路 可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。,应用六：数据分片,2.如何快速判断图片是否在图库中？,应用七：分布式存储,一致性哈希算法,14,二叉树,二叉树,感谢聆听,