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

VIP免费
2025-01-13 0 0 30.26KB 2 页 5.9玖币
侵权投诉
1. 将下列两组函数按如下方式排序：如果
f
(
n
)
=O
(
g
(
n
)
)
，则
f
(
n
)
排在
g
(
n
)
前；当且仅当
f
(
n
)
=Θ
(
g
(
n
)
)
时 ， 函 数
f(n)
和 函 数
g(n)
之 间 排 序 表 示 为 {
f
(
n
)
,
}。 如 无 特 殊 说 明 ，
log n=log2n
。例：如果函数为
n
√
n
n+
√
n
则正确的排序应为(
√
n
, {
n
,
n+
√
n
})或(
√
n
, {
n+
√
n
,
n
})。
A组
(logn)2022
n2log(n2022)
4n3/2
2.022n
nlog4n
B组
22n
n3
(
n
n/2
)
n !
(
n
3
)
提示：可以通过判断
log f
(
n
)
和
log g
(
n
)
、或
2f
(
n
)
和
2g
(
n
)
之间的关系来判断函数
f(n)
和函数
g(n)
间关系。
2. 在操作系统 Anix 中，一个文件可以被看作是有序字符串的集合，该文件内的第
i
个字
符串被称为该文件的第
i
行。对于文件可以进行如下简单的变换操作：
在文件中插入新的一行
从文件中删除已有的一行
交换文件中相邻的两行
其中，交换两行的操作比较便宜（因为他们已经存在文件中），而插入和删除相对较贵。
在Anix 中，存在一个文件比较功能 diff(A,B)，它可以通过将一系列变换操作应用在文件
A上使其转换为文件 B。假设文件 A和B都有且仅有
n
行，变换中每一行最多仅可以进行
一次交换操作，且每次交换的两行需要在文件 A和B中分别相邻。请给出非变换操作次
数最少的 diff 实现算法。
1. 给出求解此问题的动态规划递归关系。
2. 用循环实现基于该递归公式构造的动态规划算法伪代码。
3. 分析该伪代码的时间复杂度。
——1——
摘要：

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

相关推荐

更多
立即下载
分类：计算机 价格：5.9玖币 属性：2 页 大小：30.26KB 格式：DOCX 时间：2025-01-13

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 2
评分 收藏
分享
立即下载 VIP免费下载
客服
关注