algorithm-and-datastruct-note

算法和数据结构保研笔记

介绍一下最短生成树算法

最短生成树算法常见的有Prim算法和Kruskal算法。

这里Prim算法是每次添加一个点到集合，然后把该点连接的边放入小顶堆中，每次取出堆顶，如果该边连接顶点不在集合中，则将该点和边放入生成树集合中，这种使用堆优化的复杂度为$O(mlogm)$,否则为$O(n^2)$。

Kruskal算法使用并查集作为基础，将图中所有的边进行排序从小到大依次加入生成树集合，如果边两边属于不同并查集则合并，直到所有点都在集合中，时间复杂度为$O(mlogm)$

什么是“图”，请描述图的基本术语和图的常见存储结构。

图是一种数据结构，用于表示一组对象（顶点）以及这些对象之间的关系（边）。

常用的存储方式有邻接矩阵和邻接表，邻接矩阵适合稠密图和频繁的边查询，而邻接表更适合稀疏图和边的插入/删除操作。

介绍一下最短路径算法

最短路径算法比较常见的有Floyd算法和Dijkstra算法。

Floyd算法是多源最短路径算法，它将1到n行分别作为中转节点更新一次邻接矩阵，时间复杂度$O(n^3)$

Dijkstra算法是单源最短路径，它将目标点到临近点的距离放在集合中，从离目标点最近的临近点开始查找，每次尝试松弛临近点连接的点，将松弛的点加入集合直至处理完所有的点

什么是稳定排序，哪些排序是稳定的

稳定排序就是排序后对于原来序列中相同大小的元素顺序不变

冒泡排序，插入排序，归并排序是稳定的

快速排序，堆排序，选择排序是不稳定的

数组和链表的优劣势

数组查找速度快，但插入和删除效率较低，浪费内存，且存储必须使用连续内存，不能动态拓展

链表不能随机查找，但插入和删除效率高，内存利用率高，拓展灵活

B树和B+树

B树就是多路平衡查找树，B+树和B树区别在于B+树将所有信息放在叶子结点，非叶结点仅仅起到索引作用，且叶节点之间用链表连接，提高了查找效率

二路归并算法

先将数组自上而下分成两组直到单一元素，一共$\log_2n$层然后开始合并，每层进行n次比较

介绍霍夫曼树

霍夫曼树目的是树的带权路径长度和最小，构造方式是将所有节点按权重构造小顶堆，每次取出堆顶两个元素合并再重新放回堆中，直到堆中只有一个节点

P和NP问题

能在多项式时间解决的是P问题，能在多项式时间验证的是NP问题

动态规划，贪心，分治的关系

三个方法都是将问题分解为子问题然后求解，都在追求最优子结构

分治算法要将所有子问题求解、对于重叠子问题，就会有较多的重复计算

动态规划算法通过记住了子问题的答案以避免重复计算，适用于重叠子问题

贪心算法，对每一个决策点做一个当时看起来是最优的选择，不一定总能产生最优解，当子问题会相互影响时则不一定能得到最优解。认为子问题是互不相交的

介绍一下动态规划

动态规划是一种解决复杂问题的方法，主要通过将问题分解为较小的子问题来优化计算。它适用于具有重叠子问题和最优子结构性质的问题。DP的核心思想是利用已经解决的子问题的结果来构建新问题的解，从而避免重复计算。