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

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

admin2013-04-26  61
问题 设将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题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)