算法设计与分析算法考试练习题

VIP免费

2025-01-13 2 0 859.82KB 7 页 5.9玖币

侵权投诉

习题

1. 在分析插入排序时，一个重要的临界值是

M=∑

j=1

，即输入中“反转”的个

数（

是A[i]左侧且大于它的元素个数）。请给出一个最坏情况下时间复杂

度为

O(nlogn)

的算法，从输入中计算 M。

【答案】

由于 M的本质是计算原始输入数列中当

i<j

时

[

]

>A[j]

的个数，因此考虑改

写归并排序实现。

首先，定义“归并反转”为：进行 Merge 操作，即复制

[

p … q

]

到

、

[

q+1…r

]

到

后，

x∈L

、

y∈R

同时

x>y

。

由于在归并排序中，数组元素改变位置的唯一方式是在 Merge 过程中，同时由

于合并会使

中的元素保持相同的相对顺序，相应地

中的元素也保持相同的

相对顺序，因此两个元素改变其相对顺序的唯一方式就是较大的元素出现在

中，较小的元素出现在

中，因此，每一次“反转”都意味着一次“归并反

转”，即它们为一一对应关系。假设我们有一个涉及值

和

的归并反转，其

中

原本是

[

]

，

原本是

A[j]

。由于

位于

中，而

位于

中，

必须

位于包含

的子数组之前的子数组中。因此，

一开始位于

的原始位置

之

前的位置

，所以

(

i , j

)

是一个反转。

所以，设计基于归并排序的反转计数算法如下：

让

成为

中大于

的最小值。在合并过程中的某个时刻，

和

将成为

和

中“暴露”的值，也就是说，我们将在 Merge 过程的第 13 行中看到

z=L[i]

和

y=R[j]

。此时，将出现包含

和

L[i]

，

L[i+1]

，

[

i+2

]

，…

L[n1]

的

归并反转，而这

n1−i+1

归并反转将是唯一涉及

的归并反转。

因此，我们仅需要检测

和

在合并过程中的首次暴露，并将此时的

n1−i+1

加入归并反转的总次数中。

2. 有 n 个螺母和 n 个螺栓，每个螺母正好适合一个螺栓。比较这些螺母和螺栓

是否适配的唯一方法是

Test(x, y): x 是螺母，y是螺栓；返回 "螺母太大"、"螺母太小" 或 "螺母完全

合适"。

(a) 设计并分析匹配螺母和螺栓的 O(n2)算法

(b) 为同一问题设计 O(nlog n)算法

【答案】

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

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

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

习题1.在分析插入排序时，一个重要的临界值是M=∑j=1ndj，即输入中“反转”的个数（dj是A[i]左侧且大于它的元素个数）。请给出一个最坏情况下时间复杂度为O(nlogn)的算法，从输入中计算M。【答案】由于M的本质是计算原始输入数列中当iA[j]的个数，因此考虑改写归并排序实现。首先，定义“归并反转”为：进行Merge操作，即复制A[p…q]到L、A[q+1…r]到R后，x∈L、y∈R同时x>y。由于在归并排序中，数组元素改变位置的唯一方式是在Merge过程中，同时由于合并会使L中的元素保持相同的相对顺序，相应地R中的元素也保持相同的相对顺序，因此两个元素改变其相对顺序的唯一方式就是较大...

展开>> 收起<<

算法设计与分析算法考试练习题.docx

共7页,预览2页

还剩页未读，继续阅读

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

算法设计与分析算法考试练习题

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: