2. 计算机
  3. 现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下，则该算法的时间和空间复杂度为_____________。 i=0；j=n-1 while i＜j do while A[

现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下，则该算法的时间和空间复杂度为_____________。 i=0；j=n-1 while i＜j do while A[

admin2021-01-13  41
问题 现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下，则该算法的时间和空间复杂度为_____________。
i=0；j=n-1
while i＜j do
  while A＜0 d。
     i=i+1：
  while A[j]＞0 do
    j=j－1；
  if i＜j do
    交换A和A[j]
   
选项 A、 
B、 
C、 
D、 
答案C
解析 算法中用到了两个辅助变量i和j，算法的空间复杂度为(1)。在重新排列过程中，从数组的两端进行比较，从i=0开始判断A是否为负数，i为负数的时候，i=i+1，直到A为正数；从j=n－1开始判断A是否为正数，如果为正数，j=j－1，直到A[j]为负数。当i＜j的时候交换A和A[j]的值。然后继续判断A和A[j]的值。数组A中的元素个数为n，A＜0和A[j]＞0的比较次数共为72+2，i=i+1和j=j－1执行的次数最多为n+2次，if语句中的i＜j的比较和交换A和A[j]的操作分别最多执行n－1次，Wbile循序的条件判断至多执行n次。可见，算法的时间复杂度为(n)。
转载请注明原文地址:https://kaotiyun.com/show/xXCZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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