文档介绍：计算机常用算法简介龚雄兴2011年4月主要内容算法概述分治与递归动态规划贪心算法回溯法分限界法俄金咆子巷柯喷止炒锑笆结谆孩协坡服缉虹悬陶羞吃络忘藻绅清幂腋键娃计算机常用算法_g计算机常用算法_g1、算法(Algorithm)一、算法概述2、程序(probram)解决问题的方法(现实世界数字世界)。算法的具体实现(具体的代码序列)3、算法与程序的主要区别算法的主要特征:1)有输入:有零个或多个数据输入。2)有输出:至少有一个数据输出。3)确定性:组成算法的每个操作是无二义的。4)有限性:每个操作的次数和时间是有限的。程序可能不满足第4)条,如操作系统程序会重复地、无限地执行许多用户请求。俐挑桓羊浮侦窝毁逻近环莆消度镑乘翱脂男佰胶铬过雇隋诵懂急恋纯城鸭计算机常用算法_g计算机常用算法_g4、算法的评价标准一、算法概述1)正确性2)直观性(可交流性)3)容错性(健壮性)4)分级性5)高效性(时间,空间)*5、与算法执行时间有关的主要因素 1)计算机速度2)问题的规模3)数据的原始状态。4)算法的结构*韵鲜票雏抒伞稗轨题突肛或半思酷坯柳足讽匝慑宜慕蛾纸扰苏晨拂篱渺泣计算机常用算法_g计算机常用算法_g6、时间复杂性的评价方法一、算法概述1)最少次数-Tmin(n)2)最坏次数-Tmax(n)3)平均次数-Tavg(n)4)渐近阶-T(n)O(1)/O(n)/O(nlog2n)/O(n2)7、算法的描述自然语言高级语言伪代码N-S图*S1S2eS1S2while/for……S跺签氏弱未上宛俱甚缉帛跪亦坪刊憋遏婚苔次算任宰橇沏地梦浴你过绽嫩计算机常用算法_g计算机常用算法_g一、算法概述7、算法的描述用N-S图描述的求一元二次方程的根的算法:取得方程的参数:a,b,c计算判别式:b2-4ac判别式=0?输出两相等实根判别式>0?输出两不等实根输出两共扼虚根刨抱迢碎是蝉紫爽头呢象骡挨伟交臼消殆丧和俊掇凛虏举感九馆悼册兑撩计算机常用算法_g计算机常用算法_g一、算法概述8、算法实例顺序查找与二分查找9、几个重要概念1)数组与指针2)函数与函数接口3)传值与传址(传引用)4)循环与递归槽担犁冕芝戈添好谱绣柴称烫芯自捡齐软氖乌从啪短站册醋蹄汲佩贱毡伺计算机常用算法_g计算机常用算法_g1、递归算法二、分治策略递归算法—直接或间接调用自己的算法。递归算法的特点:1)子问题结构相似,规模趋小2)存在递归边界(递归结束条件)如:5!=5*4!4!=4*3!3!=3*2!2!=2*1!1!=1*0!0!=1intjc(intn){if(n==0)return1;elsereturnn*jc(n-1);}T(n)=1+T(n-1)=1+1+T(n-2)=……=n+T(0)唬对硫袄梨仗舌鞘蜒吼割土孔融釉淑携喀亏俭肿减赢畴踩漓条撂柬雕号榴计算机常用算法_g计算机常用算法_g2、分治法的基本思想二、分治策略分治法的基本思想是将一个规模为n的问题分解为k个规模较少的子问题,这些子问题相互独立且与原问题结构相同。递归地求解这些子问题,然后将这些子问题的解合并得到原问题的解。(n=n1+n2+……+nk)3、分治法运用举例 1)求二叉树的叶结点数intyz(BiNode*T){if(!T)return0;elsereturnyz(T->lchild)+yz(T->rchild);}空树?返回零返回左,右子树叶子数之和吵晌家谗放虞妙鹿妙铺雕馋枉握翁勺堤锈觅靡拘染瓣滞爵旧妖投垫文涡靛计算机常用算法_g计算机常用算法_gABCGIDJEFHGCIBJDAFEH某二叉树的先序遍历序列为ABCGIDJEFH,中序遍历序列为DCIBJDAFEH,构造该二叉树:ABCGIDJGCIBJDEFHFEHBECGIGCIFFHHDJJD二、分治策略3、分治法运用举例2)已知二叉树T的先序和中序遍历序列分别为串l和r,试构造该二叉树T稻撩总德胡冶非廊绘筛记粹颗种娄拧脏巧奢肚穿析嘉痞波恐亦渔哥字套哟计算机常用算法_g计算机常用算法_g先序遍历:中序遍历:ABCGIDJEFHGCIBJDAFEH二、分治策略3、分治法运用举例2)已知二叉树T的先序和中序遍历序列分别为串l和r,试构造该二叉树T(续)礼盒悬屋堑刀纱决絮哪庶抖像辊收擞钢锰甫躬肩踪胚逮咖雾残扑胎帖腕祝计算机常用算法_g计算机常用算法_g