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

VIP免费

2025-01-13 2 0 30.26KB 2 页 5.9玖币

侵权投诉

1. 将下列两组函数按如下方式排序：如果

(

)

(

)

，则

(

)

排在

(

)

前；当且仅当

(

)

=Θ

(

)

时，函数

f(n)

和函数

g(n)

之间排序表示为 {

(

)

(

)

}。如无特殊说明，

log n=log2n

。例：如果函数为

√

则正确的排序应为(

√

, {

√

})或(

√

, {

√

})。

A组

(logn)2022

n2log(n2022)

4n3/2

2.022n

nlog4n

B组

22n

(

n/2

)

n !

(

)

提示：可以通过判断

log f

(

)

和

log g

(

)

、或

(

)

和

(

)

之间的关系来判断函数

f(n)

和函数

g(n)

间关系。

2. 在操作系统 Anix 中，一个文件可以被看作是有序字符串的集合，该文件内的第

个字

符串被称为该文件的第

行。对于文件可以进行如下简单的变换操作：

在文件中插入新的一行

从文件中删除已有的一行

交换文件中相邻的两行

其中，交换两行的操作比较便宜（因为他们已经存在文件中），而插入和删除相对较贵。

在Anix 中，存在一个文件比较功能 diff(A,B)，它可以通过将一系列变换操作应用在文件

A上使其转换为文件 B。假设文件 A和B都有且仅有

行，变换中每一行最多仅可以进行

一次交换操作，且每次交换的两行需要在文件 A和B中分别相邻。请给出非变换操作次

数最少的 diff 实现算法。

1. 给出求解此问题的动态规划递归关系。

2. 用循环实现基于该递归公式构造的动态规划算法伪代码。

3. 分析该伪代码的时间复杂度。

——1——

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

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

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

1.将下列两组函数按如下方式排序：如果f(n)=O(g(n))，则f(n)排在g(n)前；当且仅当f(n)=Θ(g(n))时，函数f(n)和函数g(n)之间排序表示为{f(n),g(n)}。如无特殊说明，logn=log2n。例：如果函数为n√nn+√n则正确的排序应为(√n,{n,n+√n})或(√n,{n+√n,n})。A组(logn)2022n2log(n2022)4n3/22.022nnlog4nB组22nn3(nn/2)n!(n3)提示：可以通过判断logf(n)和logg(n)、或2f(n)和2g(n)之间的关系来判断函数f(n)和函数g(n)间关系。2.在操作系统Anix中，一个...

展开>> 收起<<

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

共2页,预览1页

还剩页未读，继续阅读

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

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

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: