设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0

admin2013-04-26 66

问题设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0 说明你所设计算法的时间复杂度和空间复杂度。

选项

答案上述算法中3个Reverse函数的时间复杂度分别为O(p／2)、O((n—p)／2)和O(n／2)，故所设计的算法的时间复杂度为O(n)，空间复杂度为O(1)。另解，借助辅助数组来实现。算法思想：创建大小为P的辅助数组S，将R中前P个整数依次暂存在s中，同时将R中后n—P个整数左移，然后将s中暂存的P个数依次放回到R中的后续单元。时间复杂度为O(n)，空间复杂度为O(p)。

解析

转载请注明原文地址:https://kaotiyun.com/show/95xi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0

计算机408

学硕统考专业

下列关于王政时代后期的叙述，不正确的是()。

简述西欧经济一体化的原因、进程和意义。

最早测量子午线的长度，并主持修订了当时最先进历法《大衍历》的是僧人()。

美国主张建立国际联盟的主要目的是()。

美国工业革命的有利条件包括()。①美国自然资源丰富②独立战争后，美国创立了资产阶级共和制度③地理位置优越，远离动乱的欧洲④拥有潜在的广阔的国内市场

1936年，张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成

以下()协议完成了从网卡到IP地址的映射。

一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中零元素的个数是()。

_______是指消费者对某种商品的购买次数和数量。

具有养阴生津功效的药物是()

治疗阵发性室上性心动过速的药物是__________。

某技术方案总投资3000万元，其中借贷资金占40％，借贷资金的资金成本为12％，企业自有资金的投资机会成本为15％，在不考虑其他影响因素的条件下，该技术方案的基准收益率至少应达到()。

作业行为导致爆炸的原因有()

下列有关文学常识的表述。不恰当的一项是：

(2012年石家庄事业单位)下列句子中标点符号使用正确的是一项是()。

【救国会】中国社会科学院2014年中国近现代史真题；云南大学2016年中国史基础真题

假设随机变量X的绝对值不大于1；P{x=-1}=1/8；P{x=1}=1/4；在事件{-1

矿物质