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

七、图和图算法

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）