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

admin2013-04-26 116

问题设将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

学硕统考专业

下列现象由中国近代社会的半殖民地半封建性质所决定的有()。①民族资产阶级提不出彻底的民主革命纲领②中国无产阶级先于中国民族资产阶级而产生③帝国主义在华的“租界”林立④中国革命必须走农村包围城市的道路

叙述并评价二战后西欧主要国家的“福利国家”政策。

汉代积极地经营西域地区，在河西走廊设有四郡，其中不包括()

抗日战争进入战略反攻阶段后，蒋介石集团却越来越暴露其日益腐朽的弊病，导致此种情况的根本原因在于()。

论述魏晋南北朝历史更替的线索．并评价这个时期的政权情况。(东北师范大学2013年历史学综合真题)

第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式，最早提出这种方式的是()

编写判定给定的二叉树是否是二叉排序树的函数。

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。

操作数地址存放在寄存器的寻址方式叫()。

中国共产党在大革命失败后，将工作重心由城市转向农村，标志着向农村进军的新起点是【】

Americansocietyisnotnap(午睡)-friendly.Infact,saysDavidDinges,asleepspecialistattheUniversityofPennsylvanianScho

患者外伤后胁肋疼痛难忍，痛处固定而拒按，脉弦。治宜选用

A、痉挛性偏瘫步态B、醉酒步态C、慌张步态D、蹒跚步态E、间歇性跛行佝偻病患者多见

PDCA循环具有()特点。GB/T19000-2000族标准质量管理的系统方法包括()。

附有证书的牛奶检定参照物(该奶粉具有确定的成分)

甲公司诉乙公司经济纠纷一案经人民法院审判并于2002年10月10日发生法律效力，法律文书规定的履行最后期限为2002年10月20日。若乙公司不履行该生效的法律文书，甲公司申请执行的期限是()。

在老年人的认知和情绪问题中，突发性意识障碍常表现为()。

建筑与雕塑都是占有三维空间的造型艺术，但是建筑在哪些方面有别于雕塑?

以下关系表达式中，其值为True的是______。