- 1、本文档共20页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
算法分析与枚举策略
O(f(n))中的f(n)的计算 c1·|f(n)|≤|T(n)|≤c2·|f(n)| 一般来说取满足上式的f(n)来表示时间复杂度较为精确。但是满足条件的f(n)还是很多,为了方便准确的表示时间复杂度,f(n)应用下面的方法求得: 令f(n)=T(n),然后忽略常数和低次项(增长次数的排序见下张幻灯片)求得f(n)。例如3n^4+8n^2+n+2=O(n^4),其中f(n)=n^4。 Accepted or TLE 一般来说评测机每秒处理基本操作10^8次左右,所以将题目最大数据带入O(f(n))就基本可以估计出是否会超时。 空间复杂度 ACM题目对空间方面一般不会有太严格的要求,只要保证程序申请的内存空间小于题目要求就行了。不过这个不能随便估计要精确计算。 再普及一下应该都知道的知识: char = 1 B short = 2B int = 4 B double = 8 B long long = 8 B 1MB = 1024 KB = 1024*1024 B 时空权衡 一般来说可以通过花费更多的空间换取更少的时间,或者花费更多的时间换取更少的空间。 我们要根据要求来时空权衡设计算法。 这一点大家会在今后学习更多的算法后得到体会,这里就不深入讲解了。 简单的例题 HOJ 1128 HOJ 1459 简单性 健壮性 效率——时间复杂度 占用空间——空间复杂度 一个算法对特定输入的时间复杂性是该算法对该输入产生结果需要的基本操作或“步”数。 假设我们求出算法过程中执行基本操作的次数,为c(n)次。我们进一步规定在特定计算机上算法的基本操作的执行时间为t,则可以估计出整个算法的运行时间T≈t·c(n)。 时间复杂度只能衡量c(n)相对于n的增长速度情况,和t没有直接关系。但考虑整个算法的运行时间时千万不要忽略了基本操作的执行时间t。 设f(n)是关于n的函数,我们用关于f(n)的一个函数来表示算法的渐进时间复杂度。严格的定义是这样的:若存在两个正常数c和m,对于任意nm都有|T(n)|≤c·|f(n)|,(这可以看作是极限的思想:n-∞时, f(n) 是T(n)的同阶或高阶无穷大)则称T(n)在集合O(f(n))中,用O(f(n))表示算法的时间复杂度。 通常可以认为,算法过程中执行基本操作的次数为k时,g是对于某数的增长情况的函数,有g(k)≈g(f(n)),则该算法的时间复杂度为O(f(n))。 ?1.f[0]=f[1]=1, f[2]=2; for (i=3; i=n; i++) f[i]=f[i-1]+f[i-3]; ? 2.for (i=1; i=n; i++) for (j=1; j=i; j++) if (j==1 || j==i) f[i][j]=1; else f[i][j]=f[i-1][j]+f[i-1][j-1]; ? 3.for (i=1; i=n; i++) for (j=1; j=i*i; j++) f[j]++; 算法一的基本操作数为n-2,时间复杂度为O(n)。 算法二的基本操作数为(1+2+3+…+n)=n·(n+1)·1/2=1/2·n2+1/2·n,时间复杂度为O(n2)。 算法三的基本操作数为12+22+32+…+n2=1/6·n·(n+1)·(2n+1),时间复杂度为O(n3)。 int f?(int x) { if (x == 2) return 2; if (x 2) return 1; return f(x - 1) + f(x – 3); } 输入n 计算f(n) 设计算f(n)的基本操作数为g(n) 则有g(n)=g(n-1)+g(n-3) g(0)=g(1)=g(2)=1 可知g(n)=C0P0n+C1P1n+C2P2n 可知f(n)的时间复杂度为O(an) 所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的。能使命题成立,即为其解。 枚举是一种确定范围后的有哪些信誉好的足球投注网站。枚举的几个主要步骤如下:对命题建立正确的数学模型;根据命题确定的数学模型中各变量的变化范围;利用循环语句、条件判断语句逐步求解或证明。 枚举的优点是简单、直观、便于理解和证明。主要缺点就是计算规模大,效率低下。 但枚举类的题目不一定简单,在有多种枚举策略的时候,要分析每种策略的优劣,选取最好的策略来满足题目的要求。 x+2y+3z = 200,求正整数解的个数。 三种枚举方法: 可以比较一下优劣 枚举x,枚举y,枚举z,验证。 枚举x,枚举y,验证2
您可能关注的文档
最近下载
- 线性代数的几何意义_任广千,谢聪,胡翠芳编著.pdf
- 《给水排水管道工程施工及验收规定》GB50268-2023.pdf
- 《文言文虚词》复习教案全面版.doc
- 2024光伏发电工程交流汇流箱技术规范.pdf
- Unit 6 Understanding ideas Longji Rice Terraces 课件-高中英语外研版(2019)必修第一册.pptx VIP
- 《高职军事理论实用教程(第三版)》全套教学课件.pptx
- 08S208室内固定消防炮选用及安装(高清-有效).pdf
- 行政组织学简答题、述题及解答(第1-5章).doc
- 超星网课《舞台人生走进戏剧艺术》超星尔雅答案2023章节测验答案.docx
- 体育场地与设施--教学大纲.pdf
文档评论(0)