NOIP复赛复习8算法分析与排序模板(共8页).docx

上传人:飞****2 文档编号:16794498 上传时间:2022-05-18 格式:DOCX 页数:8 大小:26.14KB
返回 下载 相关 举报
NOIP复赛复习8算法分析与排序模板(共8页).docx_第1页
第1页 / 共8页
NOIP复赛复习8算法分析与排序模板(共8页).docx_第2页
第2页 / 共8页
点击查看更多>>
资源描述

《NOIP复赛复习8算法分析与排序模板(共8页).docx》由会员分享,可在线阅读,更多相关《NOIP复赛复习8算法分析与排序模板(共8页).docx(8页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精选优质文档-倾情为你奉上NOIP复赛复习8算法分析与排序模板算法分析算法分析的目的是预测算法所需的资源,如计算时间(CPU消耗)、内存空间(RAM消耗)、通信时间(带宽消耗)等,以及预测算法的运行时间,即在给定输入规模时,所执行的基本操作数量,或者称为算法复杂度。算法的运行时间取决于输入的数据特征,输入数据的规模和运行时间的上限(因为运行时间的上限是对使用者的承诺)。算法分析一般忽略掉那些依赖于机器的常量,而关注运行时间的增长趋势。一般仅考量算法在最坏情况下的运行情况,使用O记号法表示最坏运行情况的上界。例如:线性复杂度O(n)表示每个元素都要被处理一次。平方复杂度O(n2)表示每个元素都要

2、被处理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!)指数级的操作,快速的增长。不同时间复杂度中元素数量与操作次数的关系图:而通常时间复杂度与运行时间有一些常见的比例关系:复

3、杂度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计算代码块的渐进运行时间,即算法复杂度的方法有如下

4、步骤: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;

5、 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

6、 - 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

7、通过使用矩阵乘方的算法来优化斐波那契数列算法。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) in

8、t 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=(r

9、es3)+(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(r

10、esi); 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

11、,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、堆排序#includeinlin

12、e 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

13、(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

14、 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 base=1,i=1;iS;i+,base*=10) for(int j=0;jS;j+)szj=0; for(int j=1;j=n;j+) int step=aj/base%10; sstep+szstep=aj; int tot=0; for(int j=0;jS;j+) for(int k=1;k=szj;k+) a+tot=sjk; for(int i=1;i=n;i+)printf(%d%c,ai,i=n?n: );专心-专注-专业

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 教案示例

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁