算法
2019-06-25 15:00:01 78 举报AI智能生成
登录查看完整内容
算法是一系列解决问题或执行任务的清晰指令。它被设计成在给定输入后产生期望的输出。算法可以用于各种计算任务，如排序、搜索、数据压缩等。一个好的算法应该具有明确定义的步骤、有效性和效率。在计算机科学中，算法的设计和分析是一个重要的研究领域，因为它直接影响到程序的性能和资源利用率。算法的应用广泛，涵盖了从日常生活中的决策制定，到科学研究中的复杂模型建立等多个领域。
作者其他创作
大纲/内容
分治法
定义
通过将大问题拆分为多个子问题，求解子问题并将解集合并为原问题的解
运行时间计算
一般式
T(n) = aT(n / b) + f(n) f(n)∈Θ(n^d) d > 0 T(n)表示解决问题所需要的时间，f(n)是将子问题解拼成最终解的时间
主定理
归并排序
T(n) = 2 * T(n / 2) + f(n)
主定理：T(n) ∈ nlogn
快速排序
最差：当序列已经有序时
最好：当序列恰好二分后都排好序
最差: T(n) = T(n - 1) + Θ(n)，T(n)∈Θ(n^2)
平均: 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)
log(n) < n^a < a^n < n! < n^n
注意对递归算法的运行时估算——数列递推公式求通项公式
红黑树
红黑树是一棵拥有以下特性的二叉搜索树：1. 每个节点要么是红的，要么是黑的2. 根节点一定是黑的3. 每个叶子节点都是为NIL的黑色的节点4. 假如一个节点是红色的，则该节点的直接子节点以及直接父节点必须是黑的5. 每个节点为起点到后代叶子节点所经过的所有路径，包含的黑色节点(不包括起点)数量是相同的 (这也被称为黑树高度)
3种插入修正方式
Knuth-Morris-PrattKMP
算法过程
该算法预先生成一张偏移表当出现不匹配情况时，根据偏移表决定下一次匹配的开始位置
偏移表-Π
该表中记录了每个字符位置出现不匹配时前面已经匹配成功的字符串中有多少个字符可以使用
假设字符串ababa
abab已经匹配成功
则前缀aba串也可以看作是后缀aba，故可以免去校验3个字符
匹配过程
匹配串与被匹配串从左往右开始匹配匹配串初始偏移值为0若校验了n个字符，其中n-1个字符不匹配则匹配串下次的偏移值为S = S + (n - Π(n))
BM算法
根据坏字符表和好后缀表的结果，计算两者各自的偏移值取最大偏移
坏字符
好后缀
扩展哈希
回溯
利用深度优先的方法，通过逐步修改状态，逼近解空间，一旦逼近过程中出现不可能的情况，则马上返回
0 条评论
回复 删除
下一页
