NOIP复赛复习8算法分析与排序模板

NOIP复赛复习8算法分析与排序模板算法分析算法分析的目的是预测算法所需的资源，如计算时间（CPU消耗）、内存空间（RAM消耗）、通信时间（带宽消耗）等，以及预测算法的运行时间，即在给定输入规模时，所执行的基本操作数量，或者称为算法复杂度。算法的运行时间取决于输入的数据特征，输入数据的规模和运行时间的上限（因为运行时间的上限是对使用者的承诺）。算法分析一般忽略掉那些依赖于机器的常量，而关注运行时间的增长趋势。一般仅考量算法在最坏情况下的运行情况，使用O记号法表示最坏运行情况的上界。例如：线性复杂度O(n)表示每个元素都要被处理一次。平方复杂度O(n2)表示每个元素都要被处理n次。复杂度标记符号描述常量（Constant）O(1)操作的数量为常数，与输入的数据的规模无关。对数（Logarithmic）O(log2n)操作的数量与输入数据的规模n的比例是log2(n)。线性（Linear）O(n)操作的数量与输入数据的规模n成正比。平方（Quadratic）O(n2)操作的数量与输入数据的规模n的比例为二次平方。立方（Cubic）O(n3)操作的数量与输入数据的规模n的比例为三次方。指数（Exponential）O(2n)O(kn)O(n!)指数级的操作，快速的增长。不同时间复杂度中元素数量与操作次数的关系图：而通常时间复杂度与运行时间有一些常见的比例关系：复杂度102050100100010000O(1)1s1s1s1s1s1s1sO(log2(n)1s1s1s1s1s1s1sO(n)1s1s1s1s1s1s1sO(n*log2(n)1s1s1s1s1s1s1sO(n2)1s1s1s1s1s2s3-4 minO(n3)1s1s1s1s20s5 hours231 daysO(2n)1s1s260 dayshangshangshangshangsO(n!)1shangshangshangshangshangshangsO(nn)3-4 minhangshangshangshangshangshangs计算代码块的渐进运行时间，即算法复杂度的方法有如下步骤：1、确定决定算法运行时间的组成步骤。2、找到执行该步骤的代码，标记为1。3、查看标记为1的代码的下一行代码。如果下一行代码是一个循环，则将标记1修改为1倍于循环的次数1 * n。如果包含多个嵌套的循环，则将继续计算倍数，例如1 * n * m。4、找到标记到的最大的值，就是运行时间的最大值，即算法复杂度描述的上界。如，斐波那契数列：Fib(0) = 0，Fib(1)= 1，Fib(n) = Fib(n-1) + Fib(n-2)F() = 0, 1, 1, 2, 3,5, 8, 13, 21, 34 .例1int Fibonacci(int n) if (n = 1) return n; else return Fibonacci(n - 1) + Fibonacci(n -2);这里，给定规模n，计算Fib(n)所需的时间为计算Fib(n-1)的时间和计算Fib(n-2)的时间的和。T(n=1) = O(1)，T(n)= T(n-1) + T(n-2) + O(1)，通过使用递归树的结构描述可知算法复杂度为O(2n)。例2int Fibonacci(int n) if (n = 1) return n; else int f = new intn + 1; f0 = 0; f1 = 1; for (int i = 2; i = n; i+) fi = fi - 1 + fi - 2; returnfn; 同样是斐波那契数列，我们使用数组f来存储计算结果，这样算法复杂度优化为O(n)。例3int Fibonacci(int n) if (n = 1) return n; else int iter1 = 0; int iter2 = 1; int f = 0; for (int i = 2; i = n; i+) f = iter1 + iter2; iter1 = iter2; iter2 = f; return f; 同样是斐波那契数列，由于实际只有前两个计算结果有用，我们可以使用中间变量来存储，这样就不用创建数组以节省空间。同样算法复杂度优化为O(n)。例4通过使用矩阵乘方的算法来优化斐波那契数列算法。static intFibonacci(int n) if (n = 1) return n; int, f = 1, 1 , 1, 0 ; Power(f, n - 1); return f0, 0;static voidPower(int, f, int n) if (n = 1) return; int, m = 1, 1 , 1, 0 ; Power(f, n / 2); Multiply(f, f); if (n % 2 != 0) Multiply(f, m);static voidMultiply(int, f, int, m) int x = f0, 0 * m0, 0 + f0, 1 *m1, 0; int y = f0, 0 * m0, 1 + f0, 1 *m1, 1; int z = f1, 0 * m0, 0 + f1, 1 * m1,0; int w = f1, 0 * m0, 1 + f1, 1 *m1, 1; f0, 0 = x; f0, 1 = y; f1, 0 = z; f1, 1 = w;优化之后算法复杂度为O(log2n)。排序算法1、快速排序#includeinline void Rd(int&res) res=0;char c; while(c=getchar(),c48); dores=(res3)+(res47);int res;void qsort(int L,intR) if(L=R)return; int key=resL,low=L,high=R; while(lowhigh)while(lowhigh&key=reshigh)-high; if(lowhigh)reslow+=reshigh;while(low=reslow)+low; if(lowhigh)reshigh-=reslow; reslow=key; qsort(L,low-1),qsort(low+1,R);int main() int n;Rd(n); for(int i=1;i=n;i+)Rd(resi); qsort(1,n); for(int i=1;i=n;i+)printf(%d%c,resi,i=n?n: );2、归并排序#includeinline void Rd(int&res) res=0;char c;short f=1; while(c=getchar(),c48&c!=-); do if(c=-)f=-1; elseres=(res3)+(res47); res*=f;const int M=;int aM,bM;void Merge(int L,intR) if(L=R)return; int mid=L+R1; Merge(L,mid);Merge(mid+1,R); int low=L,high=mid+1,c=L;while(low=mid&high=R)/L,low) if(alow=ahigh)bc+=alow+; else bc+=ahigh+; while(low=mid)bc+=alow+; while(high=R)bc+=ahigh+; for(int i=L;i=R;i+)ai=bi;int main() int n;Rd(n); for(int i=1;i=n;i+)Rd(ai); Merge(1,n); for(int i=1;i=n;i+)printf(%d%c,ai,i=n?n: );3、堆排序#includeinline void Rd(int&res) res=0;char c; while(c=getchar(),c48); dores=(res3)+(res47);struct Heap static const int M=; int heapM,sz; Heap()sz=0; inline void swap(int *a,int *b) if(a=b)return; int t=*a;*a=*b;*b=t; int top()return heap1; void push(int val) heap+sz=val; int pos=sz; while(pos1) int nxt=pos1; if(heapnxtheappos)swap(&heapnxt,&heappos); else break; pos=nxt; void pop() int pos=1; heappos=heapsz-; while(pos1)=sz) int nxt=pos1; if(nxt+1=sz&heapnxt+1heapnxt)+nxt;if(heapnxtheappos)swap(&heappos,&heapnxt); else break; pos=nxt; q;int main() int n;Rd(n); for(int i=1,x;i=n;+i)Rd(x),q.push(x); for(int i=1;i=n;i+) printf(%d,q.top(); putchar(i=n?n: ); q.pop(); 4、基数排序#includeinline void Rd(int&res) res=0;char c; while(c=getchar(),c48); dores=(res3)+(res47);static const intM=,S=10;intaM,sSM,szS;int main() int n;Rd(n); for(int i=1;i=n;+i)Rd(ai); for(int