算法

评判算法的优劣标准

时间复杂度

概念

​ 时间复杂度是用来估计算法运行时间的一个式子（单位）。

​ 一般来说，时间复杂度高的算法比复杂度低的算法慢。

常见的时间复杂度（按效率排序）

​ 常数阶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)

空间换时间

​ 现阶段内存价格不是很贵，成本较低，所以现阶段一般牺牲空间，来换取时间复杂度的优势。

算法

递归

两个特点：

• ​ 调用自身

• ​ 结束条件

递归实例（汉诺塔问题）

此处有图

'''
这里的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)

​ 快速排序

​ 堆排序

​ 归并排序

一般情况下，就运行时间而言：快速排序<归并排序<堆排序

三种排序算法的缺点：

​ 快速排序：极端情况下排序效率低。

​ 归并排序：需要额外的内存开销。

​ 堆排序：在快的排序算法中相对较慢。

此处有图

高阶：

​ 希尔排序

​ 计数排序

​ 基数排序

冒泡排序

​ 列表每两个相邻的数，如果前面的比后面大，则交换这两个数。

​ 一趟排序完成后，则无序区减少一个数，有序区增加一个数。

​ 代码关键点：趟、无序区范围。

​ 如果冒泡排序中的一趟排序没有发生交换，则说明列表已经有序，可以直接结束算法。

时间复杂度：O(n^2)

选择排序

• ​ 一趟排序记录最小的数，放到第一个位置。

• ​ 再一趟排序记录记录列表无序区最小的数，放到第二个位置。

• ​ ......

• 算法关键点：有序区和无序区、无序区最小数的位置。

时间复杂度：O(n^2)

插入排序

​ 初始时有序区有一张牌。

​ 每次从无序区摸一张牌，插入到手里已有牌的正确位置。

时间复杂度：O(n^2)

快速排序

特点：速度快。

快速排序思路：

此处有图

• 取一个元素P(第一个元素)，使元素P归位；

• 列表被P分成两部分，左边都比P小，右边都比P大；

• 递归完成排序。

快速排序的时间复杂度：O(nlogn)

快速排序的问题：

​ 最坏情况

​ 递归

堆排序

一种特殊的完全二叉树结构（二叉树介绍在文后）

此处有图

大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大。

小根堆：一棵完全二叉树，满足任一个节点都比其孩子节点小。

堆的向下调整性质:

• 假设根节点的左右子树都是堆，但根节点不满足堆的性质。

• 可以通过一次向下的调整来将其变成一个堆。

堆排序的过程：

1. 建立堆。

2. 得到堆顶元素，为最大元素。

3. 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序。

4. 堆顶元素为第二大元素。

5. 重复步骤3，直到堆变空。

堆排序的时间复杂度：O(nlogn)

堆排序的内置模块：

​ Python内置模块——heapq

​ 常用函数：

​ heapify(x)

​ heappush(heap,item)

​ heappop(heap)

topk问题：

​ 现在有n个数，设计算法得到前k大的数。（k<n）

解决思路：

​ 排序后切片 O(nlogn)

​ 排序初阶 O(mn)

​ 堆排序思路 O(nlogk)：

• ​ 取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数。

• ​ 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整；

• ​ 遍历列表所有元素后，倒序弹出堆顶。

归并排序

​ 两个有序列表，合成一个有序列表

​ 分解：将列表越分越小，直至分成一个元素。

​ 终止条件：一个元素是有序的。

​ 合并：将两个有序列表归并，列表越来越大。

希尔排序

希尔排序是一种分组插入排序算法。

原理：

• 首先取一个整数d1=n/2，将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序；

• 取第二个整数d2=d1/2，重复上述分组排序过程，直到d1=1，即所有元素在同一组内进行直接插入排序。

• 希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使所有数据有序。

希尔排序的时间复杂度讨论比较复杂，并且和选取的gap序列有关。

计数排序

对列表进行排序，已知列表中的数范围都在0到100之间。设计时间复杂度为O(n)的算法。

桶排序

在计数排序中，如果元素的范围比较大（比如在1到1亿之间），如何改造算法？

​ 首先将元素分在不同的桶中，再对每个桶中的元素排序。

桶排序的表现取决于数据的分布。也就是需要对不同数据排序时采取不同的分桶策略。

平均情况时间复杂度：O(n+k)

最坏情况时间复杂度：O(n^2k)

空间复杂度：O(nk)

基数排序

例子：此处有图

数据结构

​ 数据结构就是设计数据以何种方式组织并存储在计算机中。

​ 程序=数据结构+算法

数据结构的分类

按照逻辑结构可分为：线性结构、树结构、图结构。

​ 线性结构：数据结构中的元素存在一对一的相互关系。

​ 树结构：数据结构中的元素存在一对多的相互关系。

​ 图结构：数据结构中的元素存在多对多的相互关系。

线性结构

列表（数组）

​ 列表（其他语言称数组）是一种基本数据类型。

栈

​ 栈是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表。由栈顶、栈底构成。

栈的特点：

​ 后进先出

栈的基本操作：

​ 进栈（压栈）：push/append

​ 出栈：pop

​ 取栈顶：gettop/l[-1]

栈的应用：

​ 括号匹配

队列

​ 队列是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。

​ 进行插入的一端称为队尾（rear），插入动作称为进队或入队。

​ 进行删除的一端称为队头（front），删除动作称为出队。

队列的特点：

​ 先进先出（First-in，First-out）

队列的实现方式：

​ 环形队列（保证可删除可插入不浪费空间）。

​ 此处有图

​ 双向队列（两端都可进可出）。

队列的内置模块：

#使用方法：
from collections import deque
#创建队列：
queue=deque()
#进队：
append()
#出队：
popleft()
#双向队列队首进队：
appendleft()
#双向队列队尾出队：
pop()

栈和队列的应用（迷宫问题）

此处有图

链表

链表是由一系列节点组成的元素集合。每个节点包含两个属性，数据域item和指向下一个位置的next指针。

链表的创建

头插法：从头部插入

尾插法：从尾部插入（需要知道头尾分别在哪）

双链表（链表的升级版）

双链表每个节点由两个指针，一个指针指向后面数据的地址，另一个指针指向前面数据的地址。

链表复杂度：

顺序表（列表/数组）与链表

按元素值查找

按下标查找

在某元素后插入

删除某元素

好处：插入和删除快于顺序表

内存可以更灵活的分配

链式存储对树和图的存储有很大优势。

哈希表

一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作：

insert get deleteI

哈希表的应用--集合与字典、MD5算法、SHA2

字典与集合都是通过哈希表来实现的。

使用哈希表存储字典，通过哈希函数将字典的键映射为下标。

如果发生哈希冲突，则通过拉链法或开发寻址法解决。

树与二叉树

树是一种数据结构，比如：目录结构

树是一种可以递归定义的数据结构

树是由n个节点组成的集合：

• ​ 如果n=0，那这是一棵空树；

• ​ 如果n>0，那存在一个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。

概念：

• ​ 根节点、叶子节点

• ​ 树的深度：高度

• ​ 树的度：及为树种最多叶子的数量

• ​ 孩子节点/父节点

• ​ 子树

二叉树

度不超过2的树

每个节点最多有两个孩子节点

两个孩子节点被区分为左孩子节点和右孩子节点

此处有图

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

二叉树的存储方式（表示方式）：

• 链式存储方式

• 顺序存储方式

AVL树

AVL树是一颗自平衡的二叉搜索树。

AVL树具有以下性质：

根的左右子树的高度之差的绝对值不能超过1

根的左右子树都是平衡二叉树。