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

admin2021-01-13  28

问题 现要对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)