阅读算法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】
分析这个算法的时间复杂度,并给出适用场合。
时间复杂度________________________________________________________
适用场合__________________________________________________________