计算机算法基础

会计学1计算机算法基础计算机算法基础第1页/共102页第2页/共102页第3页/共102页第4页/共102页第5页/共102页1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。 例：不符合确定性的运算n 5/0 n 将6或7与x相加n 未赋值变量参与运算第6页/共102页第7页/共102页4）输出 一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。第8页/共102页第9页/共102页第10页/共102页4.算法描述语言自然语言自然语言, ,数学语言数学语言, ,流程图流程图, ,程序设计语言等等程序设计语言等等. .5.问题的求解过程2)建立数学模型1)问题的陈述3)算法设计用科学规范的语言用科学规范的语言, ,对所求解的问题做准确的描述对所求解的问题做准确的描述. .通过对问题的分析通过对问题的分析, ,找出其中的所有操作对象及操作对象之间找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述的关系并用数学语言加以描述. .根据数学模型设计问题的计算机求解算法根据数学模型设计问题的计算机求解算法. .第11页/共102页4)算法的正确性证明5)算法的程序实现6)算法分析证明算法对一切合法输入均能在有限次计算后产生正确输出证明算法对一切合法输入均能在有限次计算后产生正确输出. .对执行该算法所消耗的计算机资源进行估算对执行该算法所消耗的计算机资源进行估算. .将算法正确地编写成机器语言程序将算法正确地编写成机器语言程序. .第12页/共102页进行算法分析的基本技术：抽象第13页/共102页第14页/共102页第15页/共102页第16页/共102页第17页/共102页第18页/共102页第19页/共102页第20页/共102页第21页/共102页第22页/共102页第23页/共102页第24页/共102页第25页/共102页第26页/共102页第27页/共102页第28页/共102页第29页/共102页high)/2(low第30页/共102页hjjjjhh(14256789)j第31页/共102页第32页/共102页第33页/共102页第34页/共102页第35页/共102页2）下界函数第36页/共102页)()(ngnf3）“平均情况”限界函数第37页/共102页)(gf)(hg)(hf、)(gf)( fg)(gf)( fg第38页/共102页h(n)i)()(ngif)(11knikni第39页/共102页第40页/共102页第41页/共102页第42页/共102页循环: while cond do S repeat loop S until cond repeat for vblestart to finish by increment do S repeat 2. 同质异项3. 其它 函数的定义与调用、函数和过程、变量与形式参数第43页/共102页第44页/共102页第45页/共102页procedure ADD(item,STACAK,n,top) if top n then call STACKFULL endif top top +1 STACK(top) itemend addprocedure DELETE(item,STACK,top) if top 0 then call STACKEMPTY 0 then call STACKEMPTY endif endif item item STACK(top) top top-1end DELETE第46页/共102页第47页/共102页节点插入 call GETNODE(T) DATA(T) itemitem LINK(T) STACK LINK(T) STACK STACK T STACK T节点删除 item DATA(STACK)DATA(STACK) T STACK T STACK STACK LINK(SATCK) STACK LINK(SATCK) call RETNODE(T) call RETNODE(T)ASTACK0第48页/共102页第49页/共102页第50页/共102页第51页/共102页用链接表表示 每个结点三个信息段：TAG,DATA,LINK TAG0，DATA存数据；TAG=1,DATA存链接信息，指向一棵子树第52页/共102页2k-1,k0。第53页/共102页第54页/共102页第55页/共102页第56页/共102页第57页/共102页第58页/共102页第59页/共102页第60页/共102页第61页/共102页第62页/共102页第63页/共102页第64页/共102页第65页/共102页 （1）（2）（3）（4）（5）（6）（7）（8）（9）（10）0021112合并操作U(1,2)后：（Parent1=2）（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）2021112第66页/共102页U操作为常量时间，F操作则与查找元素在集合树中的层数有关。 第67页/共102页第68页/共102页（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）-4-321112第69页/共102页第70页/共102页第71页/共102页第72页/共102页第73页/共102页第74页/共102页第75页/共102页第76页/共102页第77页/共102页第78页/共102页第79页/共102页第80页/共102页第81页/共102页GCD(22,8)GCD(8,6)GCD(6,2)GCD(2,0)2递推递推递递推推递递推推递递推推回回归归回回归归回回归归回归回归结果为结果为GCD(22,8)=2第82页/共102页第83页/共102页第84页/共102页第85页/共102页第86页/共102页第87页/共102页第88页/共102页第89页/共102页第90页/共102页第91页/共102页第92页/共102页第93页/共102页第94页/共102页 渐进分析 时间复杂性渐进阶分析的规则:(最坏情况) 1). 赋值,比较,算术运算,逻辑运算,读写单个变量(常量)只需1单位时间 2). 执行条件语句 if c then S1 else S2 的时间为TC +max(TS1,TS2). 3). 选择语句 case A of a1: s1；a2: s2；.； am: sm 需要的时间为 max（TS1,TS2 ,., TSm）. 4). 访问数组的单个分量或纪录的单个域需要一个单位时间一个单位时间. 5). 执行for循环语句的时间=执行循环体时间执行循环体时间*循环次数循环次数. 6). while c do s (repeat s until c)语句时间=(Tc+Ts)*循环次数循环次数. 7). 用goto从循环体内跳到循环体末或循环后面的语句时,不需额外时间 8). 过程或函数调用语句 对非递归调用,根据调用层次由里向外用规则1-7进行分析； 对递归调用,可建立关于T(n)的的递归方程,求解该方程得到T(n). 例例 题题1-1第95页/共102页 算法1-2:二分查找 (假定c是A的最后一元)例例 题题 1-1分析:问题规模为n,元运算执行时间设为赋值a,判断t, 加法s, 除法d, 减法b.最坏情况Tmax(n) = 6a+4t+2s+d+(2a+2s+3t+d) lognfunction b-search(c) L:=1; U:=n; 2 found:=false; 1 w h i l e n o t f o u n d a n d U = L d o 3 i:=(L+U)div2; 3 if c=Ai 1then found:=true 1else if cAi 1 then L:=i+1 1 else U:=i-1 if found then b-search:=i else b-search:=0 1 Logn+1第96页/共102页算法设计与分析算法设计与分析 已知不重复且从小到大排列的m个整数的数组A1.m,m=2K,K为正整数.对于给定的整数c,要求找到一个下标i,使得Ai=c.找不到返回0.例例 题题 1-1function b-search(c,L,U) if Uc then 1 b-search:= b-search(c,L, index-1); 3+T(m/2) else b-search:= b-search(c,index+1,U); 3+T(m/2) ; 设T(m)是b-search在最坏情况下的时间复杂性,则T(m)满足如下递归方程:2 2 m=m=0 013 13 m=1m=1 11+T(11+T(mm/2) /2) m1m1T(m)=T(m)=解得: T(m) =11logm+13= (logm)算法1-3:二分查找递归算法第97页/共102页 求Fibonacci数列的前N项 a a0 0, a, a1 1, a, aNN 其中, a0=0, a1=1, a ai i= a= ai-1i-1+ + a ai-2i-2算法1-4Procedure seq(n) function A(n) if n=0 then 1 A:=0 1 else if n=1 then 1 A:=1 1 else A:=A(n-1)+A(n-2) 6+F(n-1)+F(n-2) ; if n1 n1F(n)=F(n)=ni0例例 题题 1-2ni0第98页/共102页4).套用公式法 若递归方程形如:T(n)=aT(n/b)+ f(n),可根据f(n)的不同情况套用公式 1)若0,使得 f(n)=O(n logb b a-),则T(n)= (n logb b a) 2)若f(n)=(n logb b a), 则T(n)= (n logb b a logn) 3)若0,使得f(n)=(n logb b a+),且 c1, 当n充分大时有 a f(n/b) c f(n), 则 T(n)= (f(n)设a0 ,a1,an,.是任意数列,称 f(x)=a0+a1x+ anxn+为数列的母函数若取数列为算法的时间复杂性函数 T(n) ,则其母函数为: f(x)=T(0)+T(1) x+ T(n) xn 若能由T(n)的递归方程求出T(n)的母函数,其展开式第n项系数即为T(n).递归方程解的渐进阶1).母函数法2).迭代法 将递归方程的的右端项通过迭代展开成级数,然后估计级数和的渐进阶.3).数学归纳法(代入法) 先估计递归方程的显式解,再用数学归纳法证明.第99页/共102页第100页/共102页第101页/共102页