- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
算法设计与分析
什么是算法—定义
输入:有零个或多个外部量作为算法的输入。
输出:算法产生至少一个量作为输出。
确定性:组成算法的每条指令清晰、无歧义。
有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限。
算法是解决问题的方法或过程,严格地讲是满足下述性质的指令序列。
“Algorithms:acommonlanguagefornature,human,andcomputer.”
—AviWigderson
什么是算法—计数
判断一个byte里面有多少个bit的值为1?
intCal(intiValue){
while(iValue!=0){
iReminder=iValue%2;
if(iReminder==1)
iCount++;
iValue=iValue/2;
}
returniCount;
}
如果这个子函数需要调用很多次,内存空间足够,怎样提高性能?
如果既想省时间,又想省空间,怎样改进?
intiTables[256]={…};
iCount=iTables[iValue];
HashMapMaps;
If(Maps.containsKey(Value)){
Count=Maps.get(Value)}
else{
Maps.put(Value,newInteger(Cal(iValue)))}
什么是算法—最大和连续子数列
问题描述:给定一个整数数列{A1,A2,…,An},求Ai+Ai+1+…+Aj-1+Aj
的最大值,并确定对应的子序列。如果所有的整数都是负数,那么最大
连续子数列和为0。
例如:
{1,-3,4,5}的最大子数列为{4,5},因为4+5最大;
{3,4,-5,8,-4}的最大子数列为{3,4,-5,8},因为3+4-5+8最大为10;
{4,3,-1,2}的最大子数列为{4,3,-1,2},因为4+3-1+2最大为8。
课程内容
算法复杂性
枚举策略
递归与分治
动态规划
贪心算法
有哪些信誉好的足球投注网站技术
时间复杂度分析
枚举算法
确定枚举对象枚举对象也可以理解为是问题解的表达形式,一般需要用若干参数来描述
参数之间需要相互独立,而且参数数目越少,问题解的有哪些信誉好的足球投注网站空间的维度也相应地小;
每个参数的取值范围越小,问题解的有哪些信誉好的足球投注网站空间也越小。
逐一列举可能解根据枚举对象的参数构造循环,一一列举其表达式的每一种取值情况
逐一验证可能解根据问题解的要求,一一验证枚举对象表达式的每一个取值,如果满足条件,则采纳它,否则,抛弃之
大道至简
百钱百鸡、二分枚举
分治策略
分治法所能解决的问题特征:
该问题的规模缩小到一定的程度就可以容易地解决
该问题可以分解为若干个规模较小的相同问题
利用该问题分解出的子问题的解可以合并为该问题的解
该问题所分解出的各个子问题是相互独立的
divide-and-conquer(P)
{
if(|P|=n0)adhoc(P);//解决小规模的问题
dividePintosmallersubinstancesP1,P2,...,Pk;//分解问题
for(i=1;i=k;i++)
yi=divide-and-conquer(Pi);//递归的解各子问题
returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解
}
治众如治寡,分数是也!
合并排序、快速排序、二分查找
动态规划
分析最优解的性质,并刻划其最优子结构特征
确定状态表示S(x1,x2,…)和状态转移方程,递归地定义最优值
确定状态转移顺序,以自底向上的方式计算出最优值
根据计算最优值时得到的信息,构造最优解
前事不忘,后事之师
矩阵连乘、多段图最短路径、最长公共子序列
算法篇-贪心算法
活动安排问题、哈夫曼编码,最小生成树
贪心算法的三个逻辑步骤:
分解将原问题求解过程划分为连续的若干个决策阶段
决策在每一个阶段依据贪心策略进行局部贪心决策,并缩小待求解问题的规模
合并将各个阶段的局部解合并为原问题的一个全局可行解
贪心算法也是一种基于子问题思想的策略。贪心算法是一个分阶段决策过程,在每个局部阶段,贪心法都做出一个当前最优的局部决策,并期
您可能关注的文档
最近下载
- 17周新模式英语1Unit1-4全套教案.pdf
- 安川机器人YASKAWA AR2010 说明手册.pdf
- 西南交通大学(材料力学B)机械类作业系统作业与详细解答.docx
- 基于人用经验的中药复方制剂新药临床研发指导原则(试行).pdf
- 《原电池 第1课时》示范课教学设计【化学人教版高中选择性必修第一册(新课标)】.docx
- GBZ 178-2017 粒籽源永久性植入治疗放射防护要求.pdf
- 中国国家标准 GB/T 4437.1-2023铝及铝合金热挤压管 第1部分:无缝圆管.pdf
- 教育评价引领学生健康成长20151212-黑龙江教育科研.ppt
- 现代名图说明书|Hyundai Mistra Owner's Manual.pdf
- 标底、工程量清单、招投标控制价和拦标价的区别.pdf
文档评论(0)