算法设计与分析北航研究生算法(2020精心整理-HJP)

VIP免费

2025-01-13 2 0 1.22MB 17 页 5.9玖币

侵权投诉

一：判断题

1、一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。（×）

2、NP 完全问题比其他所有 NP 问题都要难。（错）

NP 问题分为 NP-hard 问题和 NP 完全问题，NP 完全问题是最难的，但是 NP-hard 问题又

包含 NP 完全问题。

错：NP 完全问题至少同其他所有 NP 问题一样难。

3、回溯法用深度优先法或广度优先法搜索状态空间树。（错，仅深度优先）

错：回溯法用深度优先法搜索状态空间树。

4、在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。（错）

错：在动态规划中，各个阶段所确定的决策构成一个决策序列，通常称为一个策略。

5、P类和 NP 类问题的关系用 P⊂NP 来表示是错误的。（错）

错：P中所有问题均属于 NP。

P：存在求解判定问题 P1 的多项式时间算法。

NP：对 P1 的每一个肯定实例均存在一个多项式时间内的验证。（对一个实例为肯定实

例的证明称为该实例的证书。）

NPcomplete:P1 是一个 NP 问题，且 NP 中所有问题都可以多项式转化为 P1.

NPhard：NP 中所有问题都可以多项式转化为 P1。

NPhard 问题范围大于 NPcomplete 问题范围。

6、若近似算法 A求解某极小化问题一实例的解为 Sa，且已知该问题的最优解为 Sa/3，则该近似算法的性

能比为 3。（错）

错：性能比是所有实例可能的精确率的上界。3只是这一实例的精确率，不是所有实例

的。

7、通常来说，算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。（对）

8、若 P2 多项式时间转化为(polynomial transforms to)P1，则 P2 至少与 P1 一样难。（错）

错：应该是 p1 至少和 p2 一样难，有可能 p1 更难。

总是可以在可比时间内用 P1 的算法解决 P2，但不能说 P1 和P2 一样难。事实上，有时

候可能 P2 简单而 P1 更难。

9、快速排序算法的平均时间复杂度是 O(nlogn)，使用随机化快速排序算法可以将平均时间复杂度降得更

低。（错）

10、基于比较的寻找数组 A[1,…,n]中最大元素的问题下届是 Ω(n/3)。（错）

对：下界理论：问题的下界不唯一，越高越好。算法最优：下界=上界

几个问题的下界：

（1）排序问题：

(

n logn

)

（2）找最大：

Ω(n/2)

或

Ω(n−1)

（3）找最大最小：

Ω(3n

2−2)

下界是用分治策略得到的结果：将数组均分成两部分，

在每部分中找出最大值和最小值，在比较这两部分的最大值和最小值。

（4）找第二大元素：

Ω(n+logn−2)

找第一大元素需要比较 n-1 次，第一是通过两

两配对比较中较大的元素中最大的元素，第二大元素师两两比较中第二大的元

素，再找到第二大元素需要 logn-1 次比较，加在一起得到如上结果。

11、O(f(n))+O(g(n))=O(min{f(n),g(n)})（错）

错。应该是 max，O代表的是算法的上界。

12、若 f(n)=Ω(g(n))，g(n)=Ω(h(n))，则 f(n)=Ω(h(n))（对）

对：

相当于小于等于。

13、若 f(n)=O(g(n))，则 g(n)=Ω(f(n))（对）

对：O相当于大于等于。

14、贪婪技术所做的每一步选择所产生的部分解，不一定是可行性的。（错）

错：贪心算法每一步必须满足：可行的（即它必须满足问题的约束）、局部最优、不

可撤销。

贪心算法通常包含一个用以寻找局部最优解的迭代过程，在某些实例中这些局部最优

解转变成了全局最优解，而在另外一些实例中则无法找到全局最优解。

15、LasVegas 算法只要给出解就是正确的。（对）

16、一个完全多项式近似方案是一个近似方案{Aε}，其中每一个算法 Aε 在输入实例 I的规模的多项式时间

内运行。（错）

错：题目中定义的是多项式近似方案。

完全多项式近似方案：是一个近似方案

{Aε}

，其中每一个算法

Aε

在输入实例

的规模

和

1/ε

两者的多项式时间内运行

二：简答

1、二叉查找树属于减治策略的三个变种中的哪一个的应用？什么情况下二叉查找树表现出最差的效率？

此时的查找和插入算法的复杂性如何？

答：减治策略有 3个主要的变种，包括减常量、减常数因子和减可变规模。 (1) 二叉查找树属于减可变规

模变种的应用。(2) 当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度等于 n，此时

二叉查找树表现出最差的效率，(3) 查找和插入算法的时间效率都属于 Θ(n)。

1.（1）属于减可变规模的应用。（2）当关键字的个数等于二叉查找树的高度时表现出最差的效率。时间

复杂度为 O(n)。（3）此时查找和插入算法在最坏情况（查找当前序列的最大值或者插入最大值）的时间

复杂度都是 O(n)。

1.二叉查找树属于减治策略中的减去的规模是可变的。当二叉查找树是严格歪斜的时候，

效率最差，此时的查找和插入效率为

Θ(n)

。

（1）二叉查找树属于减治策略中减少可变规模变种中的应用；

（2）当树的高度=节点个数-1，即树是一颗严格歪树时表现出最差的效率；

（3）此时查找和插入算法的时间复杂度为 O(n)。

减治法的三种变种：

（1）减去一个常量：

递归法求

;

插入排序；最坏

平均

n2/4

快速排序+插入排序

拓扑排序：减一

生成排序：减一要求 1-n 的排序先求 1-（n-1）的排序

生成子集：减一

（2）减去一个常数因子：

二分搜索

假币问题

俄式乘法

约瑟夫问题

（3）减去可变规模

欧几里得除法

插值查找：最差O(n)

二叉查找树:最差O(n) 平均 O(logn)

变治的 3种类型：

（1）实例化简：变换为同样问题的一个更简单或更方便的实例

预排序：如果列表是有序的，许多问题更容易求解。

-检验数组中元素的唯一性：先对数组排序，然后只检查连续元素，如果该数组有

相等的元素则一定有一对元素是相互紧挨着的复杂度：排序+查找紧邻元素是否

相同即 O（nlogn+n）=o(nlogn)。

-查找数字列表中出现频率最高的一个数：先对输入排序（之后有相等的数值都会

邻接在一起），求出该有序数组中邻接次数最多的等值元素。

高斯消去：把n个线性方程构成的 n元联立方程组变换为一个等价的方程组，该方

程组有一个上三角系数矩阵，该矩阵主对角线下的元素都为 0.

LU 分解

AVL 树：把集合变为二叉树

-AVL 树是一棵二叉树，其中每个节点的平衡银子定义为该节点左子树和右子树的高

度差，这个平衡因子要么是0要么是1要么是-1.

（2）改变表现：变换为同样实例的不同表现

2-3 树：平衡查找树

堆和堆排序

霍纳法则

二进制幂

（3）问题化简：变换为另一个问题的实例，这种问题的算法是已知的

最小公倍数：通过两数乘积与其最大公约数之商求得

函数极值：已知最小求最大，目标函数加负号

线性规划

简化为图

2、何谓伪多项式算法？如何将一 Monte Carlo 算法转化为 Las Vegas 算法？

答：若一个数值算法的时间复杂度可以表示为输入数值 N的多项式，但其运行时间与输入数值 N的二进制

位数呈指数增长关系，则称其时间复杂度为伪多项式时间。

Las Vegas 算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时

用拉斯维加斯算法找不到解。

Monte Carlo 算法每次都能得到问题的解，但不保证所得解的准确性

转化：可以在 Monte Carlo 算法给出的解上加一个验证算法，如果正确就得到解，如果错误就不能生成问

题的解，这样 Monte Carlo 算法便转化为了 Las Vegas 算法。

2.（1）伪多项式时间算法是 NPC 的一种，存在复杂度是关于实例规模和实例所有参数中绝对值最大数是

成多项式关系的算法。

2.伪多项式时间算法是一种算法，它在 L值的多项式时间内运行，其中 L是输入实例中的最

大数值。这是 PPT 里的定义（维基百科：伪多项式算法：若算法的时间复杂度可以表示成

输入数值 N的多项式，则称其为伪多项式算法。）

（1）伪多项式算法是一种在 L值的多项式时间内运行的算法，其中 L是输入实例中的最

大数值；

（2）Monte Carlo 算法每次都能得到问题的解，但不保证所得的解的准确性；Las Vegas

算法每一次不一定得到问题的解，只要得到解一定是正确的解。可以在 Monte

Carlo 算法后加上一个验证算法，如果正确就得到解，如果错误就不能生成问题的

解，这样 Monte Carlo 算法便转化成了 Las Vegas 算法。

可以通过多次运行 Monte Carlo，并且满足每次运行时的随机选择都相互

独立，使产生非正确解的概率可以减到任意小，从而转化为 Las Vegas。

3、构造AVL 树和 2-3 树的主要目的是什么？它们各自有什么样的查找和插入的效率？

答：(1)当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度等于 n，此时二叉查找树

表现出最差的效率，为了解决这一问题，可以构造AVL 树或 2-3 树，使树的深度减小。一棵AVL 树要求它

的每个节点的左右子树的高度差不能超过1。2-3 树和 2-3-4 树允许一棵查找树的单个节点不止包含一个元

素。(2) AVL 树在最差情况下，查找和插入操作的效率属于 Θ(lgn)。2-3 树无论在最差还是平均情况下，查

找和插入的效率都属于 Θ(log n)。

3. 构建AVL 树和 2-3 树能够平衡左右子树的高度，减少树的层数，使得平均搜索效率更高。

插入和查找的时间复杂度均为 O(logn)。

3.二叉查找树属于减治策略中的减去的规模是可变的。当二叉查找树是严格歪斜的时候，

效率最差，此时的查找和插入效率为

Θ(n)

。

（1）构造AVL 树和 2-3 树的目的是使左右子树更加平衡，减小树的层数，使平均搜索效

率更高；

（避免出现2叉树中，树严格歪斜的情况，使以每个节点为根的左右子

树的高度接近，增加查找和插入的效率。）

（2）他们在最坏情况下插入和查找的时间复杂度为 O(log2n)。

4、写出0/1 背包问题的一个多项式等价(Polynomial Equivalent)的判定问题，并说明为什么它们是多项式

等价的。

答：0/1 背包问题：从M件物品中，取出若干件放在空间为 W的背包里，给出一个能获得最大价值的方案。

每件物品的体积为W1，W2……Wn，与之相对应的价值为 P1,P2……Pn。+

判定问题 I：从M件物品中，取出若干件放在空间为 W的背包里，是否存在一个方案，所获价值≥P*？。

每件物品的体积为W1，W2……Wn，与之相对应的价值为 P1,P2……Pn。

若判定问题 I存在多项式时间的解法，则反复调用该算法就可以在多项式时间内解决 0/1 背包的优化问题。

因而这个判定问题与原问题多项式等价。

0/1 背包问题的一个多项式等价判定问题是整数划分问题。

证明：1.背包优化问题可以多项式转化为背包判定问题。我可以利用背包优化问题的最优

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

一：判断题1、一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。（×）2、NP完全问题比其他所有NP问题都要难。（错）NP问题分为NP-hard问题和NP完全问题，NP完全问题是最难的，但是NP-hard问题又包含NP完全问题。错：NP完全问题至少同其他所有NP问题一样难。3、回溯法用深度优先法或广度优先法搜索状态空间树。（错，仅深度优先）错：回溯法用深度优先法搜索状态空间树。4、在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。（错）错：在动态规划中，各个阶段所确定的决策构成一个决策序列，通常称为一个策略。5、P类和NP类问题的关系用P⊂NP来...

展开>> 收起<<

算法设计与分析北航研究生算法(2020精心整理-HJP).docx

共17页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

算法设计与分析北航研究生算法(2020精心整理-HJP)

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: