问答题
设将n(n，1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P(0＜P＜n)个位置，即将R中的数据由(X1，X2，…，Xn)变换为(Xp，Xp+1，…，Xn，X1，…，Xp-1)
[要求]
问答题
给出算法的基本设计思想。
【正确答案】基本设计思想：
将数组{a1，a2，a3，…，ap，ap+1，…，an}先进行全部逆转，然后分别对{ap，…，an-1，an}{a1，a2，a3，…，ap}进行再次逆转。
【答案解析】
问答题
根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。
【正确答案】算法描述：
void sift_left(int a[],int n,int p){
Reverse(a,0,n-1); //移动了3n/2次数据;
Reverse(a,0,n-p-1); //移动了3(n-p)/2次数据;
Reverse(a,n-p,n-1);} //移动了3p/2次数据;
void Reverse(int A[],int left,int right){
int n=right-left+1; //设置一个辅助空间;
if(n＜=1)return 0; //数组为空;
for(int i=0;i＜n/2;i++){ //进行逆转;
int temp=A[i];
A[i-1]=A[n-i+1];
A[n-i+1]=temp;
}
}
【答案解析】
问答题
说明你所设计算法的时间复杂度和空间复杂度。
【正确答案】算法的时间复杂度和空间复杂度：
算法的时间复杂度为O(n)；
算法的空间复杂度为O(1)。
【答案解析】