首页 > 试题广场 >

阅读算法programXP1,并回答两个问题。

[问答题]

阅读算法programXP1,并回答两个问题。

void programXP1(int a[],int n,int max){
     int* temp=new int[n];
     int* count= new int[max];
     for(int i=0;i<n;i++)
         temp[i]=a[i];
     for(int i=0;i<max;i++)
         count[i]=0;
     for(int i=0;i<n;i++)                          (1)
         count[a[i]]=count[a[i]]+1;
     for(int i=0;i<max;i++)                                 (2)
         count[i]=count[i-1]+count[i];
     for(int i=n-1;i>=0;i--)                         (3)
         a[--count[temp[i]]]=temp[i];
}

【问题1】假设将整数序列(7,3,8,9,6,1,8,1,2,7,7,3,4,5)存放在数组arr中,试写出调用算法programXP1(arr,14,10)时,执行(1)、(2)和(3)循环语句之后,数组a与数组count的状态。

执行(1)语句之后数组count的状态:

执行(2)语句之后数组count的状态:

执行(3)语句之后数组a的状态:

【问题2】

分析这个算法的时间复杂度,并给出适用场合。

时间复杂度________________________________________________________

适用场合__________________________________________________________


1,O(n)
2,去重排序。
3,在需要时间,空间富裕的情况下可以使用
发表于 2017-11-28 19:23:30 回复(0)