算法

2019-06-25 15:00:01   79  举报





AI智能生成

算法是一系列解决问题或执行任务的清晰指令。它被设计成在给定输入后产生期望的输出。算法可以用于各种计算任务，如排序、搜索、数据压缩等。一个好的算法应该具有明确定义的步骤、有效性和效率。在计算机科学中，算法的设计和分析是一个重要的研究领域，因为它直接影响到程序的性能和资源利用率。算法的应用广泛，涵盖了从日常生活中的决策制定，到科学研究中的复杂模型建立等多个领域。

学习计算机算法

作者其他创作

大纲/内容

分治法

定义

通过将大问题拆分为多个子问题，求解子问题并将解集合并为原问题的解

运行时间计算

一般式

T(n) = aT(n / b) + f(n) f(n)∈Θ(n^d) d > 0 T(n)表示解决问题所需要的时间，f(n)是将子问题解拼成最终解的时间

主定理

if a < b^d, T(n)∈Θ(n^d)

if a = b^d, T(n)∈Θ(n^d log n)

if a > b^d, T(n)∈Θ(n^(logb(a)))

归并排序

T(n) = 2 * T(n / 2) + f(n)

主定理：T(n) ∈ nlogn

快速排序

最差：当序列已经有序时

最好：当序列恰好二分后都排好序

最差: T(n) = T(n - 1) + Θ(n)，T(n)∈Θ(n^2)

最好: T(n) = 2 * T(n / 2) + Θ(n), T(n)∈Θ(nlogn)

平均: T(n) ∈ Θ(nlogn)

寻找关节点
Articulation

关节点定义

删除该点会使得当前图不再连通(生成两棵树)

步骤

1. 使用DFS构成DFS树，记录树边以及回边
回边：深度搜索时遇到非直接父节点的已遍历节点

2.
* DFS树中，叶子节点永远不会是关节点
* 当根节点有两棵以上子树时，根节点才是关节点
* 内部节点中，假如A节点的任何子节点B与A节点的
任何祖先C之间存在回边，则A不是关节点

AVL树

定义

AVL树是一棵二叉树，节点上左右子树的高度差称为该节点的平衡因子；
AVL树中每个节点的平衡因子均不超过1；
空子树的高度为-1

顶点增删导致不平衡
四种处理方式

1. 单左旋

2. 单右旋

3. 双左右旋

4. 双右左旋

高度判定

某一边的子树高度是从0开始计算的
比如左子树只有一个节点，则左子树高度为0

高度差为左子树高度-右子树高度

堆与优先队列

定义

1. 堆是一棵完全二叉树
2. 堆的元素之间只有上下关系，不保证左右关系
3. 上面元素大的称为最大堆，反之为最小堆

创建

1. 自顶向下O(nlogn)

向堆中插入新元素，然后将新元素往上浮

2. 自底向上O(n)

对已经生成的未排序堆，检查每个中间节点以及其子树是否满足堆要求

爬山，Best-first，分支定界

爬山是按照当前活动节点梯度进行深度优先搜索解

Best-first是按照所有可能的活动节点中梯度最大的进行广度优先搜索解

什么是算法

有限性

算法需要在有限步骤中完成问题

定义

一个算法有清晰的定义

输入

输出

效率

算法分析

时间效率

理论分析

基本操作与输入规模的乘积 T(n) ≈ op * C(n)

基本操作：直接影响算法运行时间的操作

输入规模：

排序：排序元素数量

矩阵相乘：矩阵元素数量

图：边/点

空间效率

优化极限

大O

f(n)∈O(g(n)): 意味着fn的增长速度不会超过(<=)gn

小o

与大O相似，只是此时fn < gn 没有等于号

大Θ

f(n)∈Θ(g(n)): 意味着fn增长与gn近似

大Ω

f(n)∈Ω(g(n)): 意味着fn增长要比gn快(>=)

小Ω

与大Ω类似，只是此时fn > gn 没有等于号

规则

f1n∈O(g1n)且g1n∈O(g2n)，则f1n∈O(g2n)

f1n∈O(g1n)且f2n∈O(g2n)，则f1n + f2n∈O(max{g1n, g2n})

log(n) < n^a < a^n < n! < n^n

注意对递归算法的运行时估算——数列递推公式求通项公式

红黑树

定义

红黑树是一棵拥有以下特性的二叉搜索树：
1. 每个节点要么是红的，要么是黑的
2. 根节点一定是黑的
3. 每个叶子节点都是为NIL的黑色的节点
4. 假如一个节点是红色的，则该节点的直接子节点以及直接父节点必须是黑的
5. 每个节点为起点到后代叶子节点所经过的所有路径，包含的黑色节点(不包括起点)数量是相同的
(这也被称为黑树高度)

3种插入修正方式

Knuth-Morris-Pratt
KMP

算法过程

该算法预先生成一张偏移表
当出现不匹配情况时，根据偏移表决定下一次匹配的开始位置

偏移表-Π

该表中记录了每个字符位置出现不匹配时
前面已经匹配成功的字符串中有多少个字符可以使用

假设字符串ababa

abab已经匹配成功

则前缀aba串也可以看作是后缀aba，故可以免去校验3个字符

匹配过程

匹配串与被匹配串从左往右开始匹配
匹配串初始偏移值为0
若校验了n个字符，其中n-1个字符不匹配
则匹配串下次的偏移值为S = S + (n - Π(n))

BM算法