文档介绍：第一章算法的概念算法书中的算法特指计算机科学中的算法,即那些在计算机科学中描述为适宜于作为计算机程序执行的解决问题的方法 算法是一个有穷的规则序列。 是一个能完成特定任务的有穷指令集合。 决定了解决某一特定问题的一系列运算。即算法是一个指令的有限集合。算法复杂性分析在“正确地”前提下,评价有两个指标:时/空时间复杂性和空间复杂性算法程序运行时的消耗时间算法程序运行时所占用的存贮大小 最坏情况、最好情况、平均情况的复杂性如果给定输入大小,把复杂度取做所有输入(可能是有限个也可能是无限个)的最大复杂度,则称之为最坏情况复杂度;如果把复杂度取做所有输入的“平均”复杂度,则称之为平均情况复杂度(亦有称作期望时间复杂度)。在大多数情况下,我们主要研究个算法的最坏情况复杂度,因为它应用广泛,也比较容易处理渐进复杂性的意义我们关心的一般是最坏情况下的计算时间复杂度的上界渐近意义下的记号:O、Ω、θ T(n)=limtf(n)=○(f(n))趋势,渐进时间复杂度n→∞○(n)至多要用时间的数量级。掌握算法渐进复杂性的分析学习目的:能设计出好的算法;2)能分析评价算法的好坏第二章递归与分治策略算法总体思想1、将问题分解成k个子问题,对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。2、将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。递归的概念直接或间接地调用自身的算法称为递归算法递归算法应用1、阶乘2、i数列3、Ackerman函数4、Hanoi塔问题优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此为设计算法、调试程序带来很大方便。缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。分治法的适用条件分治法所能解决的问题一般具有以下几个特征:该问题的规模缩小到一定的程度就可以容易地解决;该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解;该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。分治法的基本步骤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);//将各子问题的解合并为原问题的解}分治法的复杂性分析分治法的算法应用二分法搜索大整数的乘法Strassen矩阵乘法棋盘覆盖合并排序与快速排序线性时间选择最接近点对问题循环赛日程表第三章动态规划动态规划基本思想保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。动态规划基本步骤找出最优解的性质,并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息,构造最优解。动态规划算法的基本要素最优子结构性质2、重叠子问题动态规划算法举例完全加括号的矩阵连乘积最长公共子序列凸多边形最优三