导图社区算法分析与设计

算法分析与设计

关于算法分析与设计的思维导图，算法是满足终止性、确定性、能行性、输入、输出条件的计算。无论使用哪一种算法求解最优解，一定一定要明确最优解的定义是什么。

编辑于2023-10-28 17:00:08

考研考公
软件专业
算法分析与设计

罐装旺仔

他的近期作品查看更多>>

算法分析与设计

社区模板帮助中心，点此进入>>

罐装旺仔

他的近期作品查看更多>>

相似推荐
大纲

互联网9大思维
- 33.7k
- 904
- 2.4k
- 389
MindMaster
安全教育的重要性
- 6.5k
- 853
- 96
- 18
issen
组织架构-单商户商城webAPP 思维导图。
- 14.6k
- 3
- 184
- 10
Kacyun
个人日常活动安排思维导图
- 7.2k
- 0
- 77
- 1
少儿栏目外景策划波波老师
域控上线
- 1.6k
- 162
- 11
- 4
jackrao
西游记主要人物性格分析
- 15.2k
- 1.3k
- 635
- 105
issen
17种头脑风暴法
- 193.2k
- 3.8k
- 11.5k
- 3.9k
MindMaster
python思维导图
- 5.4k
- 522
- 242
- 7
(*^▽^*)
css
- 1.2k
- 1
- 43
- 3
A张舫
CSS
- 3.2k
- 261
- 188
- 33
journey

算法分析与设计

chapter1绪论

算法是满足以下条件的计算

目的：解决问题

终止性

确定性

能行性

输入

输出

计算

给定计算模型机械的执行的规则或计算步骤序列被称为计算

一个计算机程序是一个计算

计算不是算法

问题

定义了输入输出之间的关系

算法秋节的是一个完整的问题，不是一个简单的问题实例

分析算法

算法的正确性：对于所有输入都终止并且产生正确的输出

不正确算法：不终止或者是对于某个输入产生不正确的输出

近似算法/随机算法的正确性：对所有输入都终止，产生近似正确的解或者是不多的不正确的解

正确性证明的原因

调试程序不能证明没有错误

方法

对所有输入都终止

每个输入都有正确的输出

算法的复杂性

目的：分析算法对不同的输入所需要的资源量

时间复杂性，空间复杂性，输入输出次数等等

输入大小得函数

输入大小：size(α)

实例时间复杂性：对特定输入的结果产生最需要进行的操作数

特定输入的时间复杂性

实例空间复杂性

特定输入

空间复杂性，对输入产生结果所需要的存储空间大小

是输入大小的函数S(n)

最坏时间复杂性

算法最小复杂性

算法平均复杂性

出现的概率乘以复杂性的所有可能性之和

算法分析模型

随机访问模型

并行多处理机模型

时间复杂性分析

不是一个程序解决问题需要话费多啥时间，而是当问题规模扩大之后时间长度增长的有对快

常数级别的时间复杂性

直接插入算法的时间复杂性分析

当读入第k个数的时候，与前面的数字积极性比较，

算法正确性分析

循环不变量方法

循环不变量P：所操作的数据和数据结构具有关键的性质

比如说是在排序算法中数字顺序不变的性质就可以作为循环不变量

循环初始

循环步骤

循环终止

设计算法

分治

动态规划

贪心算法

树搜索算法

问题划分

图灵机

确定的图灵机在多项式时间内求解的问题的P

不确定的图灵机在多项式时间内可解的问题NP

不确定的图灵机不能再Non-NP

子主题

chapter 2 数学基础

2.1 计算复杂性函数的阶

同阶函数集合f(x)=θ(g(x)) 其中函数集合是：θ(g(x)) 紧界

低阶函数f(n)=0(g(n)) 上界或者是比他更加低阶上界

高阶函数 f(n)=Ω(g(n)) 下界最好情况

不能够说明大小关系只能够说明的是阶级关系；高阶函数不一定大于他的下界；尤其是高阶函数【不是严格高阶函数】

θ(g(n))⊆0(g(n)) f(n)=O(n^k ) 多项式界限

严格低阶函数上界但是不是紧界 f(n)=o(g(n))

f(n)=o(g(n))⇒(lim)┬(n→∞) f(n)/g(n) =0

严格高阶函数下界但是不是紧界 f(n)=ω(g(n))

f(n)=ω(g(n))当且仅当g(n)=o(f(n))

f(n)=ω(g(n))⇒(lim)┬(n→∞) f(n)/g(n) =∞

函数的阶的性质

传递性包含上面五个

自反性包含前三个

对称性紧界

反对称性

f(n)=0(g(n)) 当且仅当g(n)=Ω(f(n))

f(n)=o(g(n))当且仅当 g(n)=ω(f(n))

数学公式中函数阶的含义

2.2 和式的估计和界限

线性和

级数

直接求和的界限

子主题

2.3递归方程使用自身来定义自身

求解递归方程的三个主要方法

替换猜测+数学归纳

迭代转换成为和式+估计和

Master 定理

子主题

Chapter3 排序与分治算法

3.1 分治原理

设计阶段

分：子问题未必相同划分时间D(n)

治：求解各个子问题 aT(n)

和：合并子问题的解 C(n)

总的时间复杂度：T(n) = a(T(n/b))+D(n)+C(n)

分析阶段

建立递归方程

求解

3.2 基于分治的排序算法

快排主要工作是进行划分算法需要知道边界条件

排序问题的下界

3.3 中位数和订单统计

减治原理

比如说是折半查找

选择问题

3.4 查找距离最近的点对

划分和合并的方法，降低f(n)

一维空间算法

首先进行排序

分治算法

分

治

和

二维空间算法

3.5 线性时间进行排序

Counting

使用A、B、C三个数组

总体的思想：输入数组-A，输出数组：B，计数数组：C【数组基数是A的取值范围【0-k【A中最大值】】】（要求：需要A为整数数组）

【注】空间消耗很大的时候使用桶结构

存在的问题

A[i]为整数

并且输入数组的取值范围0-k需要小一些,否则效率会大大降低

排序过程中，需要长度为 max 的计数空间和长度为 len 辅助输出空间，这个空间是比较大的，空间复杂度为 O(len+max) 。

时间复杂度：O(n+k)

Radix

特点

stable

从最低位向最高位进行排序

算法

输入要求：相同位数d的数组整数

时间复杂度：O（d(n+k[输入的取值范围，影响相对比较小可以忽略]))

问题：d过大

扩展使用类似于分治算法

将位数为b的数组划分为b/r向上取整个位数为r的数据，每个数据的取值范围0-2^r-1

使用计数排序

r的最优取值：lgn 向下取整

注意：在r不大的时候可以使用

Bucket 桶排序

桶排序的一种假设：输入独立均匀的分布在0-1之间【期望达到线性的条件】

桶排序的思想

划分0-1到大小均匀的桶里

输入分入桶中

桶中数据进行排序

列出所有已经排序完成的数据在每个桶中的

时间复杂度：紧界n

算法的一些判断标准

stable：按照输入顺序合理的排序输出

in-place：没有另外开辟空间

3.6 查找凸包

问题定义

输入：平面上面的点的集合，输出凸包

性质

凸多边形P，连接P内任意两点的边都在P内

Graham-Scan算法

逆时针，按照极角大小排序

向左进行旋转

须知

xy最大最小值都在凸包上面，首先确定其中一个点为起点，绘制一条水平线，从这条水平线开始遍历上面的点【选择的是最小的点】

伪代码

求 Q中y-坐标值最小的点

逆时针排序Q中其余点

推入栈S中

如果构成费向左移动的时候把栈顶元素pop出来

时间复杂性：f(n)=0(n log⁡n )

正确性分析：循环不变量【在处理某个节点之前，栈S自底向顶存储了CH（Qi-1）】

分治算法

边界条件

分

划分为Ql、Qr

治

和

在合并的序列上面运行Graham-Scan即可

合并序列的方法

3.7 快速傅里叶变换 FFT

3.8 整数乘法

优化划分阶段降低a

问题定义：输入——n位二进制整数X和Y；输出——X、Y的乘积

chapter 4 动态规划算法

算法总结

有一种穷举的感觉

就是罩子问题和服问题之间的关系之后再使用穷举的方法最后选定最小值作为最优解

注意：覆盖所有情况

4.1 动态规划要素

原因：如果子问题不是相互独立的，分值方法将会重复计算公共子问题，效率很低

目的：优化问题——优化问题就是给定一个代价函数，在问题的解空间中搜索具有最小或最大代价的优化解

动态规划问题是解决优化问题的常见方法

定义：原始问题划分成一系列子问题【多项式级别的个数】

自底向上地求解子问题

自上而下是分治算法

适用范围：一类渔鸥化问题，子问题可以被重复使用

使用条件

优化子结构：当一个问题的优化解包含了子问题的优化解时，我们说这个问题具有优化子结构。

重叠子问题：在问题的求解过程中，很多子问题的解将被多次使用

不重叠的时候直接使用分治即可，否则还需要另辟存储空间

算法的设计步骤

– 分析优化解的结构【哪些子问题的优化解构成的，直接到边界条件就可以了】 – 递归地定义最优解的代价 – 递归地划分子问题，直至不可分 – 自底向上地求解各个子问题 – 计算优化解的代价并保存之 – 获取构造最优解的信息 – 根据构造最优解的信息构造优化解

4.2 矩阵链乘法

问题定义：输入p_i-1*p矩阵；输出计算最小代价的方法

矩阵连乘法

满足结合律，不同的计算顺序会有不同的代价

使用动态规划的方法

具有子问题重叠性

递归的定义最优解的代价

子主题

扩展解法：可以使用记忆化的方法，分值就可以变成动态规划，

4.3 最长公共子序列

问题定义

问题求解

⚫ 优化解的结构分析 ⚫ 建立优化解的代价递归方程 ⚫ 递归地划分子问题 ⚫ 自底向上计算优化解的代价记录优化解的构造信息 ⚫ 构造优化解

优化子结构分析

第i前缀：Xi

优化子结构

方便使用这种方法进行递归求解

三条直接证明的证明

子问题重叠性，需要处理的问题数量（至多有mn个子问题）

最好是所有情况覆盖

为了方便计算的边界条件

假如说边界条件不方便计算的时候，还需要至多O(m)或者o(n)的时间去计算边界

问题划分：使用上面定义的条件，就是说前面为了递归定义的条件

自底向上计算优化解代价之后根据上面的解向下求解

最后自底向上去求解，根据B标记的最优解的记号去求解，所求到的解是最终解得倒转

伪代码：是按行找的解，按照箭头去查找的自底向上进行查找

时间复杂性：O(mn)【子问题的数量】，其中构造最优解的时间是O(m+n)

空间复杂性O(mn)

空间优化策略：可以把C只设计成为两行m列或者是怎么样的

4.4 0/1背包问题

问题定义

在不超重的情况下获得使得包中物品价值最大的装包策略

初步分析：每种物品有两种选择，装或者不装；装取方案的计算代价是n【是否茶盅/价值计算之后使用常数时间去比较获取最大价值即可】

总计算代价是O(n2^n)

np完全问题

问题求解

优化解的结构分析

子问题的重叠性：当物品的重量相同都是1的时候就会有大量重叠子问题

不适合分治算法【可以尝试使用记忆化的】

问题定义

建立优化解代价的递归方程

定义代价矩阵m；

m[i,j]

i:起始的、计算子问题优化解的代价的矩阵时间

j:指的是包的容量

递归方程的总结

递归的划分子问题

计算m[i,j]需要知道

自底向上的计算优化解的代价，记录优化解的构造信息

构造优化解

总的代价计算：伪多项式算法

一共是有四种情况

4.5 二叉搜索树

问题定义

二叉搜索树的定义

影响搜索树的通体的查询代价：树的形状与节点的查询概率

树的期望代价值

奇数节点是叶节点

偶数节点是内节点

E(T)树的期望代价值

代价值与树的深度、代价增量有关

根节点一定是偶数位

问题求解

优化解的结构分析

优化子结构及证明

子树的贡献值：子树的位置固定、概率固定、贡献差值孤星

贡献增量：概率*深度差值

用优化子结构去构造优化解

子问题重叠性

建立优化解代价的递归方程

建立优化解的搜索代价递归方程

边界条件以及其他关起

全面覆盖

公式：概率+（代价+增量）【左子树+右子树】

W ：增量；E：期望代价；P：概率

增量的递归计算公式

W[i,j] = w(i,j-1)+pi+pj = w(i,r-1)+w(r+1,j)+pr

递归的划分子问题

自底向上的计算优化解的代价，记录优化解的构造信息

构造优化解

4.6 最小编辑距离

定义

两个字符串之间的转换

只包含有三种操作：插入字符、删除字符、替换字符【每一种都算一次基本操作】

字符的对齐方式影响效率

求解

优化解的结构分析

最小编辑距离的性质

不重叠性：任意字符只能执行至多一次操作

顺序无关性

对称性

空扩展字符串

子问题重叠性

建立优化解代价的递归方程

四种情况

边界条件

首先需要考虑边界条件作为起始计算需要的条件

算法和算法复杂性

时间复杂性O(mn)

空间复杂性：O(mn)

优化空间结构

递归的划分子问题

自底向上的计算优化解的代价，记录优化解的构造信息

构造优化解

最小编辑距离判别问题

应用

字符串的相似度查询

定义

输入输出

分析

最小编辑距离不小于两者长度的绝对值

复杂性

两种不需要计算的情况

长度差值大于输入的判定阈值

计算是需要使用的上面的结果值大于2

空间复杂性

O（min{m,n}t）：可以优化

O(t)

时间复杂性

O(min{m,n}t)

每行/每列最多计算2*t+1个

chapter5 贪心算法

与前面两种算法的区别

子主题

贪心算法：原问题进行选择获取剩余子问题直至子问题为空

精巧

前面两种：原问题划分为子问题，繁重，自底向上

5.1 基本原理

基本概念

近似算法、启发式算法

局部最优解，当前看起来最好的选择

例子

兑换硬币问题

区域调度问题

用途

求解最优化问题

基本思想

求解最优化问题的算法包含一系列步骤，每一步都有一组选择，做出在当前看来最好的选择

希望达到全局最优解

一步步尝试，之后推翻载进行别的尝试来寻找贪心算法

逐步接近甚至于最后达到最优解

实例

产生优化解的条件

优化子结构

Greedy选择性

归纳法

算法步数进行归纳或者是对问题进行归纳

每一步都比其他算法好，产生一个最优解

包含的每一步的解都不必包含的解好

交换论证法

更加方便

最优性不变的前提下，从一个最优解逐步替换最终得到贪心算法的解

比较

设计步骤

贪心选择算法

剩余子问题

需要证明

对于贪心选择来说，所求解的问题具有优化子结构

对于贪心选择算法莱说，具有Greedy选择性

5.2 活动选择问题

问题定义

问题求解

设计贪心选择方法

优化解的结构分析

Greedy选择性证明

引理1

证明Greedy选择性

【注】需要明确优化解的条件是什么在这个问题里面，优化解就是相容的最多活动取决于数量和相容特性

引理2：优化子结构

反证法

引理3

算法设计

算法复杂性分析

5.3 Huffman编码

问题定义

二进制字符编码

固定长编码

可变长编码

前缀编码

定义

编码树

编码树的代价：代价是深度的期望和

C：字符集合

B:代价和

F：频数

贪心思想

循环选择具有最低频数的两个节点，生成一颗子树，直至形成树

问题求解

设计贪心选择方法

选择方法

剩余子问题的结构

优化解的结构分析

引理1：优化子结构证明

引理2：最深的位置，最小聘书的两个字符，相同最大长度

greedy选择性

优化前缀树包含最大长度的两个节点在相同深度

Greedy选择性证明

算法设计

算法复杂性分析

5.4 最小生成树

问题定义

Kruskal算法

设计

优化解结构

剩余子问题

收缩操作

扩张操作

优化子结构证明

Greedy选择性

算法复杂性

算法正确性

Prim算法

设计

优化解结构

Greedy选择性

算法复杂性

概要

Generic算法

框架

基本思想

算法描述

贪心选择性

定义

Cut(S,V-S)

跨Cut

遵守边集A的Cut

跨Cut的轻边

定理一

Kruskal：寻找遵循A【包含一系列连通分量】，和A中不包含的点之间跨Cut的轻边

Prim算法

回顾

最小完成时间5.5 Minimum Mackspan Scheduling

问题定义

近似算法

性能分析

chapter6 平摊分析

基本原理

基本思想

栈操作：忽视数据结构以及操作之间的关联

平摊分析方法

目的：分析给定数据结构上n个操作代价上界

各个操作的代价，通过总的代价【上界】平摊分析

确定的是上界，不是概率

聚集方法

平均

会计方法

预付【与数据对象相关联，数据对象的credit】

势能方法

积势【与整个数据结构相关联，能量】

聚集方法

分析

分析过程中要精细化，注意每个操作之间的关联

用数据对象上小的操作代价来来预付之后的大的操作代价