算法导论中文课件讲.pptxVIP

西电软件学院1算法分析与设计

算法入门(Ch2)

西电软件学院2排序问题输入：n个自然数序列a1,a2,…,an输出：满足a’1≤a’2≤…≤a’n的排列a’1,a’2,…,a’n例如--输入：5,2,4,6,1,3--输出：1,2,3,4,5,6

西电软件学院3插入排序1nijsortedkey

西电软件学院4插入排序654321469758初始654321469758j=2654321469785j=3654321469875j=4654321469875j=5654321498765j=6-∞-∞-∞-∞-∞-∞

西电软件学院5算法分析关于计算机程序性能与资源利用率的理论研究性能是最重要的吗?--模块化 --界面友好程度--正确性--编程时间--可维护性--简洁性--功能性--可扩展性--健壮性--可靠性

西电软件学院6证明算法正确性的一种方法：定义并证明一个循环不变式初始：验证其在第一次循环开始前是成立的。保持：如果在某次循环开始前是成立的，则可验证其在下次循环开始前仍然成立。终止：当循环结束时，该不变式所给出的特性可表明算法是正确的。使用循环不变式证明算法正确性

西电软件学院7插入排序的循环不变式：--在每次循环开始前（循环变量为j），子数组A[1..j-1]中包含了原数组中A[1..j-1]的元素，并且已经是有序的。初始：j=2终止：j=n+1，整个数组是有序的。保持：A[j-1],A[j-2],…每次移动一个元素直到找到元素A[j]的合适位置。使用循环不变式证明算法正确性

西电软件学院8分析一个算法的目的：对于算法所使用的资源，包括内存、通信带宽或计算机硬件等，进行预测。在本课程中，我们最关心的是算法的计算时间。在分析算法之前，我们必须建立一个关于实现技术的模型，用以建模实现技术的相关资源及其开销情况。算法分析

西电软件学院9后续分析我们将基于一个通用的单处理器、随机存取机器（random-accessmachine(RAM)）的计算模型。--指令被依次执行，不存在并发操作。--每次执行程序中的一条原子指令，包括算术运算、逻辑运算、数据移动以及控制运算等。--上述每条指令的执行需要一个常数时间。--RAM的容量足够大。--…算法分析基于RAM模型：统计基本操作的数量

西电软件学院10tj：对于每次外层循环（循环变量为j），第5行处的while循环的循环条件检查次数。开销次数c1nc2n-10n-1c4n-1c5c6c7c8n-1插入排序分析

西电软件学院11插入排序的计算时间T(n)：将每行的开销与次数的乘积求和，得到：最好情况（输入数组已经是有序的）：--计算时间是n的线性函数。插入排序分析

西电软件学院12最坏情况（输入数组是逆序的，即降序）：--计算时间是n的二次函数。插入排序分析

西电软件学院13注意：--对于任意输入而言，计算时间的上界。--对于某些算法而言，最坏情况经常发生：例如：在数据库中检索某段特定信息--平均情况经常与最坏情况一样糟（但不总是！）最坏情况与最好情况分析

西电软件学院14通常我们仅关注计算时间的增长率：--忽略低阶次项，因为当n足够大时，低阶次项相对次要。--忽略最高次项前的常数系数，因为当n足够大时，系数对计算效率的增长率来说是不重要的。--因此，我们可以说：插入排序最好情况下的计算时间相对n是线性的，而最坏情况/平均情况是二次的。增长率

西电软件学院15讨论了插入排序--引入了RAM计算模型--基于RAM模型对插入排序进行了分析--讨论了如何只关心计算时间的增长率：最好情况：线性(O(n))，最坏情况：二次(O(n2))。--能否设计优于n2的排序算法？--我们将使用一种强大的算法设计策略来设计一个更好的排序算法。算法设计

西电软件学院16要求解问题P：--分：将问题P分解为规模更小的子问题P1,P2,…,Pk。--治：递归求解这些子问题。--合并：将子问题P1,P2,…,Pk的解合并为问题P的解