奥丁9
奥丁9
后端
数据库
redis
mysql
mongoDB
达梦
php
laravel
laravel-admin
dcat
表单
表格
java
spring
python
go
c
c++
前端
vue
nodejs
sass/less
html/css
前端框架
javascript
微信生态
公众号
小程序
uniapp
typescript
其他
AI
数据结构
安全
linux
seo
git
健身
算法
正则表达式
docker
待分类
其他
/
算法
《算法图解》读书笔记
1年前
aoding9
90
算法
数据结构
读书笔记
python
## 目标 了解数据结构和一些常见算法 ## 进度 第一遍 P68 ## 1.算法简介 ### 1.1引言 ------------ ### 1.2二分查找 ------------ ### 1.3大O表示法 ------------ ## 2.选择排序 ## 3.递归 看前面的时候博客还没搭，后面第二遍再补 ## 4.快速排序 了解分而治之（divide and conquer,D&C），一种著名的递归式解决问题的方法 ### 4.1分而治之 #### 4.1.1步骤： 1.找出基线条件，条件必须尽可能简单 2.不断将问题分解（缩小规模），直到符合基线条件 #### 4.1.2例子 给定数字数组[2,4,6]，求所有元素之和 这个问题用循环当然可以解决，但是也可以用D&C的递归思想来解决。 1.找基线条件：怎样的数组求和是最简单的，只有1个或0个元素的数组求和最简单，无需相加，返回结果 2.缩小规模： ``` sum(2+4+6)=>2+sum(4+6) 2+10=12 sum(4+6)=>4+sum(6) 4+6=10 sum(6) = 6 达到基线条线，函数向上回归 ``` `一般涉及数组的递归函数，基线条件通常是数组为空或只有1个元素` ### 4.2快速排序 一种常用的排序算法，顾名思义就是速度快，使用了D&C。 1.基线条件：怎样的数组排序最简单，只有1个或0个元素的数组，不需要排序，原样返回即可 2.缩小规模：首先选一个元素为基准值，小于基准值的放左边，大于基准值的放右边，接着对左右两边的子数组递归调用这个步骤 >**归纳证明** 在基线条件中，证明了算法对空数组或一个元素的数组有效，归纳条件中，证明了如果算法对包含一个元素的数组有效，那么它对包含两个元素的数组也有效，如果它对两个元素的数组有效，那么它对三个元素的数组也有效，以此类推，推理出这个算法对所有长度的数组都有效。 ### 4.3 再谈大O表示法 #### 4.3.1 比较合并排序和快速排序 已知这两种算法时间复杂度都是O(nlogn)，为什么优先用快速排序？ 算法执行一步所需的固定实际量c，被称为常量，如果两个算法复杂度不一样，可以忽略这个常量，但是如果复杂度一样，那么c就可以用于判断哪个算法更快了。 #### 4.3.2 平均情况和最坏情况 快速排序高度依赖于选择的基准值，假设你对一个有序数组[1,2,3,4,5]排序，将第一个元素作为基准值，小于基准值的数组每次都为空，调用栈高度为5，而每层调用栈都涉及处理n个元素（取基准值，把每个元素划分到两个数组中），所以最坏情况是O(n^2) 如果总是将中间元素作为基准值，那么每次递归，数组长度都是(n-1)/2，因此调用栈高度为logn(底数为2，已省略)，复杂度为O(n)*O(logn)=O(nlogn)，这是最好的情况。 而数组越长，选到中间元素的概率就越高，因此快速排序的平均情况很接近最好情况 ## 5.散列表 假设你去商店销售人员，客人来报出商品名称询问价格，虽然二分查找速度很快，但是商品很多的话也要一些时间，如何能够报出名称马上就得到价格呢？ ### 5.1 散列函数 散列函数特点： - 将相同的输入映射到相同的数字 - 将不同的输入映射到不同的数字 - 知道数组最大长度，只返回有效的数组索引对应的数字 例如，我输入apple，映射到3，那么把价格存到arr[3]，然后我输入milk映射到0,则牛奶价格存到arr[0]，重复过程直到数组填满。查找时把名称输入散列函数，得到数组下标的数字，直接去数组取出即可，因此速度非常快，是O(1)级别 散列表别名：散列映射，映射，字典，关联数组。 ### 5.2 应用案例 #### 5.2.1 散列表用于查找 手机电话簿姓名不重复，每个姓名对应一个电话号，输入姓名得到电话号，用散列表实现，则需要提供2个功能 1.创建映射 =》添加联系人和电话 2.查找 =》输入联系人姓名得到电话 书中给了域名到ip转换的dns解析，说这是散列表提供的查找，但是多个不同域名可以对应一个ip，因此我认为不是散列表 #### 5.2.2 防止重复 假设你在管理投票站，一个人只能投一次票，为了避免重复，每次投票时，询问他的姓名，与已投票的名单对比，如果名字在名单中，说明重复投票，否则可以投票。现在假设有1万个人来投了票，如果一个个找会非常慢，而且随着名单增加，效率会越来越低。 如果使用散列表呢？投票时询问姓名输入散列函数，得到散列表arr的索引n，然后取出arr[n]，如果为空，说明没有投过票，将true存到arr[n]，那么下次再查，arr[n]就为true了，说明已投过票。 #### 5.2.3 散列表用作缓存 缓存：第一次查找后就记住，下次再遇到就直接从记忆中取出，速度快 比如妹妹问我月球到地球多远，我起初不知道，所以借口上厕所去查百度，得到答案x公里，再回来告诉妹妹，妹妹说，你好逊哦，我都打完一盘文明了。 第二天，表弟也问我相同的问题，由于我昨天刚查过还记得，因此马上回答出了，表弟露出了崇拜的表情说，你好6啊。这就是缓存的好处。 但如果过了1年再问，因为我忘了，所以还要再去查百度（缓存过期） 对于网页来说，可以将缓存的数据存储在散列表中，例如可以将url映射页面数据，缓存首页、联系我们、关于我们等不实时更新的页面，提高用户打开速度，节省服务器资源开销。有的公司后台修改手机号码后，联系我们页面的手机号还是旧号码，是因为有缓存，需要先清除缓存再打开才有效果（假设修改不触发自动清除缓存）。 ### 5.3 冲突 ## 6.广度优先搜索 关键词：图，找最短路径 先创建一个队列，将起点的邻居加入队列，然后判断邻居是否为终点，如果不是，则将邻居的邻居加入队列，直到找到终点。 ## 7.狄克斯特拉算法 关键词：加权无环图，找最短路径（最小开销），不能有负权边 假设有这个图：a->b 花费5 a->c花费1 c->b花费2，找a->b开销最少的路径 1. 创建1个散列表graph保存加权图，再创建2个散列表，costs保存节点与消费的关系，并且假设a->b的开销是无限大，parents保存节点与父节点的关系，创建一个数组processed存放已处理过的节点，防止重复处理。 2. 遍历起点a到邻近节点的开销，即a->b和a->c的开销，更新到消费表，然后从costs中找出开销最少的节点 3. 遍历该节点的每个邻居，计算开销，如`new_cost=costs[c]+graph[c][b]`，然后看new_cost是否比costs[b]开销更少，如果更少则更新costs[b]=new_cost，循环完所有邻居后，将节点push入processed数组。 例如：`a->c+c->b=1+2=3`，小于a->c的6，因此将costs[b]更新为3,parents[b]更新为c。 4. 从costs取出下一个最小消费节点，重复步骤2和3，直到计算完所有未处理节点的开销。 **如何找到costs中开销最小的节点** 默认lowest_cost_node=None，lowest_cost=float（"inf")无限大，循环costs表，当节点不在processed中，并且开销小于lowest_cost时，更新这2个变量，直到处理完所有节点。 **如何得到最短路径** 当处理完之后，根据parents表，终点b的父节点为c，判断c是否为起点，若不是起点，则再次找到c的父节点为a，由于a为起点，得到最短路径a->c->b。
本作品采用
《CC 协议》
，转载必须注明作者和本文链接