【学习】python数据结构和算法
https://www.bilibili.com/video/BV1VC4y1x7uv?p=85
二、算法分析
2.2 什么是算法分析
-
大O表示法
image.png
2.3 python数据结构的性能
-
列表
image.png
-
字典
image.png
说一下list[index]的o(1)原理，dict是散列表形式，访问函数是o(1)很容易理解。但实际上list的访问函数我认为也是一种“散列表”，或者直接是额外空间的赋值存在。即在原始的线性结构（链表）外，为了能够快速访问（毕竟索引是最必须和高频的函数）而采用了额外空间来加速访问。一种简单的形式就是，比如list[1]用node_1来赋值，list[n]用node_n来赋值，需要访问时，直接去找node_index就可以了，这是最简单的方式。（书上的实现形式并不是python真正的实现形式）
三、基本数据结构类型
3.2 线性结构
包括栈、队列、双端队列和列表。
栈：先进后出
队列：先进先出
双端队列：允许先进先出\先进后出，典型场景是回文词判定
列表：这里考虑无序列表需要的方法：
- class node: node.getData, node.getNext, node.setData, node.setNext
- class unorderdlist: unorderdlist.add, 其他就是常规函数，isempty, search等。。
四、递归Recursion
4.2 什么是递归
递归三大定律
- 必须有基本结束条件
- 必须改变自己的状态并向基本结束条件演进
- 必须递归地调用自身
典型问题1：谢尔宾斯基三角
- 结束条件：剩余迭代次数>=1
- 演进和递归调用：
1、把中间的三角形剔除；2、把左边三角形进行迭代；3、把上边三角形进行迭代；4、把右边三角形迭代
典型问题2：河内塔问题
- 结束条件：小塔层数为1（只有一个圆盘）
- 演进和递归调用：
1、把底盘上面的小塔从起点移到中间点，小塔进行迭代；2、把底盘从起点移到终点；
3、把底盘上面的小塔从中间点移到终点，小塔进行迭代
4.5 动态规划
典型问题：硬币找零
先说一下贪心算法：先找面值最大的硬币，剩下的零散的余额再用剩下的面值最大的硬币来找零。。显然在此场景下不是最优解
动态规划本质上是一个递归问题：
def recDC(coinValueList,change,knownResults):
minCoins = knownResults[change] #在此场景下，最大的次数就是余额本身，所以这里相当于是赋的初值为最大值
if change in coinValueList:
knownResults[change] = 1
return 1
if minCoins < change:
return minCoins
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recDC(coinValueList, change-i, knownResults)
if numCoins < minCoins:
minCoins = numCoins
knownResults[change] = minCoins
return minCoins
knownResults = list(range(64))
print(recDC([1,5,10,25],63,knownResults))
- 设定一个初始列表，来保存每一个值条件下的最优解，初值设为最差解
- 依次对列表中的值进行迭代，求解当前值的最优解：
1、如果有一个明确的最优解，那就是本身（此场景下就是对应找零余额存在合适的硬币）；
2、 没有最优解，则求解依次减去之前的值，再用新值去求最优解，并用最后的复合答案最优解，依次迭代；
3、完全迭代后，用最优解中的最优解作为当前值的最优解。。。
五、排序和搜索
5.2 搜索
- 顺序搜索
无序表直接进行顺序搜索，o(n) - 二分搜索
无序表可以先进行排序（额外消耗），再进行有序列表的搜索，o(logn)，在要进行大量搜索的时候综合效率最高。如果本身只执行单次搜索，效果可能不如顺序搜索
5.2.3 散列
- 槽
散列表的每一个位置是槽 - 负载因子
数据项个数/散列表大小 - 冲突
- 完美散列函数
实际上并不需要完美散列函数，而是用解决冲突的办法来合理利用槽 - 冲突解决方法
线性探测：寻找开放地址，但容易产生集中趋势，造成周边一系列槽都被线性探测填充；
二次探测法：不进行线性探测，而是采用一个再散列函数来寻找新的槽
链
5.3 排序
- 冒泡排序
对列表相邻两项进行比较，并交换顺序确保后一项大于前一项，每一轮遍历完成则有一个最大值排到最后的位置。o(n2) - 选择排序
每遍历一次只交换一次数据，即将最大项放到最后的位置。o(n2) - 插入排序
依次将列表前方进行排序，然后将后一项插入到前方已排序好的列表中正确位置。o(n2) - 希尔排序
间隔插入排序，以插入排序为基础。大致介于O(n)和O(n2)之间。 - 归并排序
分而治之，持续地将一个列表分成两半。如果列表是空的或者
只有一个元素，那么根据定义，它就被排序好了（最基本的情况）。如果列表里的元素超过一个，我们就把列表拆分，然后分别对两个部分调用递归排序。一旦这两个部分被排序好了，那么就是归并好了。O(nlogn)，效率是最高的，但是需要额外的空间来进行两个归并数组的比较。 - 快速排序
同样是分而治之，选择一个中值，并确定好中值在列表中正确的位置；将中值的左列表和右列表进行中值迭代排序。O(nlogn)~O(n2)之间，但不需要额外的存储空间。
六、树和树算法
6.2 术语
- 节点：又可细分为根节点、子节点、叶节点（没有子节点的节点）、父节点、兄弟节点
- 子树
- 层数（根节点层数为0），高度（所有层数的最大值）
- 路径、边
6.4 嵌套列表来实现树
myTree = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]
image.png
所以对树的class可以基于列表实现
6.7 树的遍历
- 前序遍历：先根后左再右
- 中序遍历：先左后根再右
- 后序遍历：先左后右再根
image.png
遍历的方式决定了读树的方式，比如上面这一棵解析树，只有中序遍历是对的，(7+3)*（5-2）
6.8 二叉堆/二叉树（优先队列）
除了先进先出、先进后出、双端队列之外，二叉堆可以实现特定的优先队列先出。二叉树的关键是保持根节点是最小值，但是对其他节点不进行排序。
完全二叉树，是指左子树和右子树相对平衡，最多只相差一层的二叉树。
生成完全二叉树的复杂度是o（n），理论上对列表进行排序的复杂度是o（n2），但是二叉树只是保持最小值在根节点，有点类似于在无序列表中寻找最小值的复杂度是o（n）。
6.9 二叉搜索树/BTS搜索树
定义:始终保持左节点<父节点<右节点
bts搜索树在极端情况下就一棵树到底，因此更广泛采用平衡二叉树
6.10 平衡二叉树/AVL树
AVL树在生成树的时候会引入平衡因子+旋转的操作来使得整体始终保持平衡
image.png
仿佛这里有问题，排好序的列表put和del的复杂度应该也是log2(n)才对，按照二分法来定位
七、图和图算法
7.2 概念
- 顶点
- 边
- 权重
- 路径
- 圈
7.3 实现形式
- 邻接矩阵（稀疏度通常特别大）
- 邻接表（更常用）
7.7 广度优先搜索（BFS）
词梯问题：寻找由fool到sage最短的路径
）
7.8 深度优先搜索（DFS）
骑士周游问题（下图并不代表实际问题）：
image.png
每个节点记录两个值：发现时间和结束时间，典型特性是返回时间更晚的（父节点）优先级总是要高于返回时间更早的（子节点），所以要实现深度搜索（所有节点都必须覆盖），就得先通过父节点，再通过子节点。。适用于各种需要优先级排序的场景，比如制作一个煎饼
image.png
7.11 dijkstra（BFS）
对于需要考虑权重的广度搜索问题，dijkstra算法：每一个节点记录源节点到当前节点的最短路径
7.12 prim（DFS）
对于需要走遍所有节点，但是为了保证路径代价最小的问题，prim算法：每一个节点记录源节点到当前已发现树（包含多个已发现节点）的最短路径。。。走到最后一个节点的时候，记录的就是源节点要走遍所有节点所需要的代价。。（书中的图不对，每个节点记录的值仍然是dijkstra）
