快10倍的计算机所能解决的问题规模? T(n Che lange n'/n 10n 100010000 n'′=10n 10 20n 5005000 n′=10n 10 5 n log n2501.842√10n<n'<10n7.37 2n2 70 223 n"'=y10n 3.16 2 13 16 n'=n+3 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 快10倍的计算机所能解决的问题规模? 2 13 16 n ’ = n + 3 ----- n 2n 2 70 223 n ’ = 10n 3.16 5n log n 250 1,842 10 n < n ’ < 10n 7.37 20n 500 5,000 n ’ = 10n 10 10n 1,000 10,000 n ’ = 10n 10 T(n) n n ’ Change n ’/n
2时空限制 设计一个算法,将数组A(0.n-1)中的元素循环右移k 位,假设原数组序列为a,a1,…an-2,an1;移动后 的序列为ank,an-k+1,…,a0,a an-k 要求只 用一个元素大小的附加存储,元素移动或交换次数为 0(n)。例如,n=10,k=3,则算法要求如下: 原始数组:0123456789 右移后的:7890123456 i-k ●● i+k +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 2. 时空限制 设计一个算法，将数组A(0..n-1)中的元素循环右移k 位，假设原数组序列为a0, a1, …, an-2,an-1；移动后 的序列为an-k, an-k+1, …, a0, a1, …, an-k-1。要求只 用一个元素大小的附加存储，元素移动或交换次数为 O(n)。例如，n=10, k=3，则算法要求如下： 原始数组： 0 1 2 3 4 5 6 7 8 9 右移后的： 7 8 9 0 1 2 3 4 5 6 … i-k … i … i+k …
n=10.k=3 原始数组:0123456789 右移后的:7890123456 n-2K, n-k-1 n-k, n-1 口如果可以使用k个元素大小的附加存储空间 口只需将数组最后k个元素按顺序保存在临时 数组中,等价于 Tmp[o. k-1]= Arrayln-k. n-1] 1然后将数组中第n-k-1个元素移动到n-1的位置上,第n k2个元素移动到n2的位置上 ■依此类推,直到将数组前端元素都移动k位 ■最后将临时数组的内容拷贝到数组的前k位,即 Arrayl0.k-1=Tmp[0. k-11 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 如果可以使用k个元素大小的附加存储空间 只需将数组最后k个元素按顺序保存在临时 数组中，等价于 ◼ Tmp[0..k-1] = Array[n-k..n-1] ◼ 然后将数组中第n-k-1个元素移动到n-1的位置上，第nk-2个元素移动到n-2的位置上 ◼ 依此类推，直到将数组前端元素都移动k位 ◼ 最后将临时数组的内容拷贝到数组的前k位，即 Array[0..k-1] = Tmp[0..k-1] n-2k, n-k-1 n-k, n-1 n=10, k=3 原始数组： 0 1 2 3 4 5 6 7 8 9 右移后的： 7 8 9 0 1 2 3 4 5 6
浪费时间:0(kn) void MultiDolphin(int Array, int n, int k)i int i, j int X k=k%n;if(k=:0)reur;/边界 for(i=1; k<=k; i++)( X= Array[n-i] 保存最后一位 for(=n-i; j>o j- Array[j]= Array[j-1 Aray[o]=× 补回 口注意:0(kn)!=0(n) 例如,k=n/2,则0(k.n)=0(n2) +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 浪费时间： O(k.n) void MultiDolphin(int *Array, int n, int k) { int i,j; int X; k = k % n; if (k == 0) return; // 边界 for (i=1; i<=k; i++) { X = Array[n-i]; // 保存最后一位 for (j=n-i; j>0 j--) Array[j] = Array[j-1] Array[0] = X; //补回x } } 注意：O(k.n) != O(n) ◼ 例如， k=n/2, 则O(k.n) = O(n2)
浪费空间:辅助空间为尺 void SHift(int *Array, int n, int k) int *Tmp= new int[k] nt 1, J: for(i=0: i<k; i++) Tmp[i]= Array[n-k+i] for(i=n-k;i >=0; i-) Array[i+k]= Array[i] for(i=0: k<k; i++) Array[i]=Tmp[] delete [] Tmp: +规数水也是王线零x,《物不故索盐们,右世,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 浪费空间：辅助空间为k void KShift(int *Array, int n, int k) { int *Tmp = new int[k]; int i, j; for (i=0; i<k; i++) Tmp[i] = Array[n-k+i]; for (i=n-k; i >= 0; i--) Array[i+k] = Array[i]; for (i=0; i<k; i++) Array[i] = Tmp[i]; delete [] Tmp; }