# 算法 ## 评判算法的优劣标准 ### 时间复杂度 #### 概念 ​ 时间复杂度是用来估计算法运行时间的一个式子（单位）。 ​ 一般来说，时间复杂度高的算法比复杂度低的算法慢。 #### 常见的时间复杂度（按效率排序） ​ 常数阶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 根的左右子树都是平衡二叉树。 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://1951995428.gitbook.io/ghostcn-z/suan-fa.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.