> For the complete documentation index, see [llms.txt](https://1951995428.gitbook.io/ghostcn-z/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://1951995428.gitbook.io/ghostcn-z/suan-fa.md). # 算法 ## 评判算法的优劣标准 ### 时间复杂度 #### 概念 ​ 时间复杂度是用来估计算法运行时间的一个式子（单位）。 ​ 一般来说，时间复杂度高的算法比复杂度低的算法慢。 #### 常见的时间复杂度（按效率排序） ​ 常数阶O(1)<对数阶O(logn)<线性阶O(n)<线性对数阶O(nlogn)<平方阶O(n^2)<立方阶O(n^3)<.......<指数阶O(2^n)。 #### 简单快速判断算法复杂度（适用于绝大多数简单情况） * 确定问题规模n（循环次数或者列表长度等） * 循环减半过程->logn（判断是否有循环减半的过程） * k层关于n的循环->n^k **复杂情况：**根据算法实际情况看。 ### 空间复杂度 ​ 空间复杂度是用来评估算法内存占用大小的式子 #### 空间复杂度的表示方式与时间复杂度完全一样 * 算法使用了几个变量：O(1) * 算法使用了长度为n的一维列表：O(n) * 算法使用了m行n列的二维列表：O(mn) #### 空间换时间 ​ 现阶段内存价格不是很贵，成本较低，所以现阶段一般牺牲空间，来换取时间复杂度的优势。 ## 算法 ### 递归 **两个特点**： * ​ 调用自身 * ​ 结束条件 #### 递归实例（汉诺塔问题） [此处有图](https://img2018.cnblogs.com/blog/1614606/201909/1614606-20190923110638633-1629261151.png) ```python ''' 这里的A,B,C是槽位，3为盘子个数。 ''' def hanoi(n, a, b, c): if n > 0: hanoi(n - 1, a, c, b) print(f'从{a}移动到{c}') hanoi(n - 1, b, a, c) hanoi(3, 'A', 'B', 'C') ``` ### 查找 #### 概念 ​ 在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程。 #### 列表查找（线性表查找）：从列表中查找指定元素 * 输入：列表、待查找元素 * 输出：元素下标（未找到元素时一般返回None或-1） 内置列表查找函数：index() **查找方法** **顺序查找（也叫线性查找）** ​ 从列表第一个元素开始，顺序进行搜索，直到查找到元素或搜索到列表最后一个元素为止。 时间复杂度：O(n) **二分查找（也叫折半查找）** > 必须是有序列表，如果是无序列表，则需先排序，且查询次数多时才用二分查找。 ​ 从**有序列表**的初始候选区li\[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。 时间复杂度：O(logn) ### 列表排序 * 输入：列表 * 输出：有序列表 方式：升序与降序 内置排序函数：sort() #### 常见排序算法 > 初阶：O(n^2) > > ​ 冒泡排序 > > ​ 选择排序 > > ​ 插入排序 > > 中阶：O(nlogn) > > ​ 快速排序 > > ​ 堆排序 > > ​ 归并排序 > > **一般情况下，就运行时间而言：**快速排序<归并排序<堆排序 > > **三种排序算法的缺点：** > > ​ 快速排序：极端情况下排序效率低。 > > ​ 归并排序：需要额外的内存开销。 > > ​ 堆排序：在快的排序算法中相对较慢。 > > [此处有图](https://img2018.cnblogs.com/blog/1614606/201909/1614606-20190924140042478-1797093936.png) > > 高阶： > > ​ 希尔排序 > > ​ 计数排序 > > ​ 基数排序 #### 冒泡排序 ​ 列表每两个相邻的数，如果前面的比后面大，则交换这两个数。 ​ 一趟排序完成后，则无序区减少一个数，有序区增加一个数。 ​ **代码关键点：趟、无序区范围。** ​ **如果冒泡排序中的一趟排序没有发生交换，则说明列表已经有序，可以直接结束算法。** 时间复杂度：O(n^2) #### 选择排序 * ​ 一趟排序记录最小的数，放到第一个位置。 * ​ 再一趟排序记录记录列表无序区最小的数，放到第二个位置。 * ​ ...... * 算法关键点：有序区和无序区、无序区最小数的位置。 时间复杂度：O(n^2) #### 插入排序 ​ 初始时有序区有一张牌。 ​ 每次从无序区摸一张牌，插入到手里已有牌的正确位置。 时间复杂度：O(n^2) #### 快速排序 **特点：**速度快。 **快速排序思路：** [此处有图](https://img2018.cnblogs.com/blog/1614606/201909/1614606-20190923143326743-773678936.png) * 取一个元素P(第一个元素)，使元素P归位； * 列表被P分成两部分，左边都比P小，右边都比P大； * 递归完成排序。 快速排序的时间复杂度：O(nlogn) **快速排序的问题：** ​ 最坏情况 ​ 递归 #### 堆排序 一种特殊的完全二叉树结构（二叉树介绍在文后） [此处有图](https://img2018.cnblogs.com/blog/1614606/201909/1614606-20190923174652089-498486798.png) 大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大。 小根堆：一棵完全二叉树，满足任一个节点都比其孩子节点小。 **堆的向下调整性质:** * 假设根节点的左右子树都是堆，但根节点不满足堆的性质。 * 可以通过一次向下的调整来将其变成一个堆。 **堆排序的过程：** 1. 建立堆。 2. 得到堆顶元素，为最大元素。 3. 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序。 4. 堆顶元素为第二大元素。 5. 重复步骤3，直到堆变空。 **堆排序的时间复杂度：**O(nlogn) **堆排序的内置模块：** ​ Python内置模块——**heapq** ​ 常用函数： ​ heapify(x) ​ heappush(heap,item) ​ heappop(heap) **topk问题：** ​ 现在有n个数，设计算法得到前k大的数。（k\ 对列表进行排序，已知列表中的数范围都在0到100之间。设计时间复杂度为O(n)的算法。 #### 桶排序 > 在计数排序中，如果元素的范围比较大（比如在1到1亿之间），如何改造算法？ ​ 首先将元素分在不同的桶中，再对每个桶中的元素排序。 桶排序的表现取决于数据的分布。也就是需要对不同数据排序时采取不同的分桶策略。 平均情况时间复杂度：O(n+k) 最坏情况时间复杂度：O(n^2k) 空间复杂度：O(nk) #### 基数排序 > 例子：[此处有图](https://img2018.cnblogs.com/blog/1614606/201909/1614606-20190924151846432-390699781.png) ## 数据结构 ​ 数据结构就是设计数据以何种方式组织并存储在计算机中。 ​ **程序=数据结构+算法** ### 数据结构的分类 > 按照逻辑结构可分为：线性结构、树结构、图结构。 ​ 线性结构：数据结构中的元素存在一对一的相互关系。 ​ 树结构：数据结构中的元素存在一对多的相互关系。 ​ 图结构：数据结构中的元素存在多对多的相互关系。 ### 线性结构 #### 列表（数组） ​ 列表（其他语言称数组）是一种基本数据类型。 #### 栈 ​ 栈是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表。由栈顶、栈底构成。 **栈的特点：** ​ 后进先出 **栈的基本操作：** ​ 进栈（压栈）：push/append ​ 出栈：pop ​ 取栈顶：gettop/l\[-1] **栈的应用：** ​ 括号匹配 #### 队列 ​ 队列是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。 ​ 进行插入的一端称为队尾（rear），插入动作称为进队或入队。 ​ 进行删除的一端称为队头（front），删除动作称为出队。 **队列的特点：** ​ 先进先出（First-in，First-out） **队列的实现方式：** ​ 环形队列（保证可删除可插入不浪费空间）。 ​ [此处有图](https://img2018.cnblogs.com/blog/1614606/201909/1614606-20190925102149595-577981766.png) ​ 双向队列（两端都可进可出）。 **队列的内置模块：** ```python #使用方法： from collections import deque #创建队列： queue=deque() #进队： append() #出队： popleft() #双向队列队首进队： appendleft() #双向队列队尾出队： pop() ``` #### 栈和队列的应用（迷宫问题） [此处有图](https://img2018.cnblogs.com/blog/1614606/201909/1614606-20190926173821426-1065782115.png) #### 链表 链表是由一系列节点组成的元素集合。每个节点包含两个属性，数据域item和指向下一个位置的next指针。 **链表的创建** 头插法：从头部插入 尾插法：从尾部插入（需要知道头尾分别在哪） #### 双链表（链表的升级版） 双链表每个节点由两个指针，一个指针指向后面数据的地址，另一个指针指向前面数据的地址。 **链表复杂度：** 顺序表（列表/数组）与链表 按元素值查找 按下标查找 在某元素后插入 删除某元素 **好处：**插入和删除快于顺序表 内存可以更灵活的分配 链式存储对树和图的存储有很大优势。 ### 哈希表 一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作： *insert* *get* *deleteI* **哈希表的应用--集合与字典、MD5算法、SHA2** 字典与集合都是通过哈希表来实现的。 使用哈希表存储字典，通过哈希函数将字典的键映射为下标。 如果发生哈希冲突，则通过拉链法或开发寻址法解决。 ### 树与二叉树 树是一种**数据结构**，比如：目录结构 树是一种可以**递归**定义的数据结构 树是由n个节点组成的集合： * ​ 如果n=0，那这是一棵空树； * ​ 如果n>0，那存在一个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。 **概念：** * ​ 根节点、叶子节点 * ​ 树的深度：高度 * ​ 树的度：及为树种最多叶子的数量 * ​ 孩子节点/父节点 * ​ 子树 #### 二叉树 度不超过2的树 每个节点最多有两个孩子节点 两个孩子节点被区分为左孩子节点和右孩子节点 [此处有图](https://img2018.cnblogs.com/blog/1614606/201909/1614606-20190923173004999-1885663318.png) **满二叉树：**一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。 **完全二叉树：**叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。 **二叉树的存储方式（表示方式）：** * 链式存储方式 * 顺序存储方式 #### AVL树 AVL树是一颗自平衡的二叉搜索树。 AVL树具有以下性质： 根的左右子树的高度之差的绝对值不能超过1 根的左右子树都是平衡二叉树。