计算机算法分析与设计 计算机算法分析与设计(共33张PPT)全文共33页，当前为第1页。 学习目标 掌握算法分析与设计的基本理论 掌握进行算法分析与设计的基本方法（时间、空间复杂度分析，算法正确性的证明） 掌握计算机领域中常用的非数值计算方法，并学会用这些算法解决实际问题 计算机算法分析与设计(共33张PPT)全文共33页，当前为第2页。 课程要求 教学方式：理论(32学时)，实践(16学时) 考核方式：考试(80%)+实验作业(20%) 课程学分：3 先修课程：《离散数学》《数据结构》《数值分析》《C语言程序设计》 计算机算法分析与设计(共33张PPT)全文共33页，当前为第3页。 授课教材 选用教材： 《计算机算法基础》（第二版） 余祥宣，崔国华，邹海明 华中科技大学出版社 参考书目： 《算法引论》 张益新，沈雁 国防科技大学出版社 《算法设计与分析》 周培德 机械工业出版社 计算机算法分析与设计(共33张PPT)全文共33页，当前为第4页。 第一章 导引 ---计算机算法分析与设计是面向设计的、处于核心地位的教育课程 ---计算机算法是计算机科学和计算机应用的核心。 1.什么是算法？ 2.如何分析算法？ 3.如何表示算法？ 4.基本数据结构 计算机算法分析与设计(共33张PPT)全文共33页，当前为第5页。 1.什么是算法 算法 数值计算方法（求解数值问题，插值计算、数值积分等） 非数值计算方法（求解非数值问题，主要进行判断比较） 算法笼统的定义：求解一确定类问题的任意一种特殊方法。 非形式描述：算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。 计算机算法分析与设计(共33张PPT)全文共33页，当前为第6页。 例1 求两个正整数m,n的最大公因子 算法1-1 欧几里得算法 输入：正整数m和n 输出：m和n的最大公因子 第一步：求余数。r m%n 第二步：判断r=0?，若是，终止(n为答案)，否则，转第三步。 第三步：互换,m n,n r,返回第一步。 Begin R m%n r=0？ Swap(m.n) End N Y 计算机算法分析与设计(共33张PPT)全文共33页，当前为第7页。 例1 求两个正整数最大公因子的一个实例 假设 m=21 和 n=45，求21和45的最大公因子 第一步：r=m%n=21%45=21； 第二步：r 不等于0，转入第三步； 第三步：互换，m=n=45, n=r=21，返回第一步。 第一步：r=m%n=45%21=3； 第二步：r 不等于0，转入第三步； 第三步：互换，m=n=21, n=r=3，返回第一步。 第一步：r=m%n=21%3=0； 第二步：r 等于0，算法结束，3即为21和45的最大公因子。 计算机算法分析与设计(共33张PPT)全文共33页，当前为第8页。 算法的五个重要特性 确定性 每一种运算必须要有确切的定义，无二义性 可行性 运算都是基本运算，原理上能在有限时间内完成 输入 有 1个或多个输入 输出 一个或多个输出 有穷性 在执行了有穷步运算后终止 计算机算法分析与设计(共33张PPT)全文共33页，当前为第9页。 算法的特性 凡是算法，都必须满足以上五条特性。 只满足前四条特性的一组规则不能称之为算法，只能叫做计算过程。 操作系统就是计算过程的一个典型例子。设计操作系统的目的是为了控制作业的运行，当没有作业时，这一计算过程并不终止，而是处于等待状态，一直等到一个新的作业的进入。 计算机算法分析与设计(共33张PPT)全文共33页，当前为第10页。 算法学习的五个内容 如何设计算法 运用一些基本设计策略规划算法 如何表示算法 用恰当的方式表示算法 如何确认算法 算法正确性的证明(算法确认algorithm validation) 如何分析算法 通过时间和空间复杂度的分析，确定算法的优劣 如何测试程序 测试程序是否会产生错误的结果 计算机算法分析与设计(共33张PPT)全文共33页，当前为第11页。 2.如何分析算法 算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。 算法分析步骤： 首先确定使用那些运算以及执行这些运算所用的时间。(运算包括基本数值运算和一些更基本的任意长序列的运算) 其次是要确定出能反映算法在各种情况下工作的数据集。（即要求我们编造出能产生最好、最坏和有代表性情况的数据配置，通过使用这些数据来运行算法，以更了解算法的性能） 计算机算法分析与设计(共33张PPT)全文共33页，当前为第12页。 全面分析一个算法的两个阶段 事前分析(a priori analysis) 求出该算法的一个时间限界函数(一些关于参数的函数) 事前分析只限于每条语句的频率计数(frequency count，该语句的执行次数，与所用的机器无关，且独
计算机算法分析与设计是计算机科学领域中的核心课程，旨在教授学生如何有效地设计和评估算法，以便解决各种计算问题。这门课程通常包含理论教学和实践环节，通过学习，学生应能够掌握基本理论、分析方法以及设计策略。
理解算法的本质至关重要。算法是一组有序的规则，用于解决特定类型的问题，它可以是数值计算，如插值计算和数值积分，也可以是非数值计算，如判断和比较。欧几里得算法就是一个非数值计算的例子，用于求解两个正整数的最大公约数。算法应具有确定性、可行性、输入、输出和有穷性这五个关键特性。确定性确保每一步都有明确的定义，可行性保证算法能在有限时间内完成，输入和输出定义了算法处理的数据，而有穷性意味着算法必须在有限步骤后终止。
在设计算法时，通常会使用一些基本的设计策略，如分治法、动态规划、贪心法和回溯法。同时，正确地表示算法也很重要，常见的表示方式包括伪代码、流程图和高级编程语言。算法的正确性需要通过证明来确认，这可能涉及到归纳法或其他逻辑推理方法。
算法分析是评估算法性能的关键步骤，主要关注时间和空间复杂度。时间复杂度描述算法运行所需的时间量级，而空间复杂度则衡量算法执行过程中所需的存储空间。分析通常包括事前分析（a priori analysis），通过计数算法中各语句的执行次数来预估复杂度，以及事后测试（a posteriori testing），收集实际运行时的统计数据。例如，可以使用大O符号（O-notation）来表示算法的最坏、平均或最好情况的时间复杂度。
课程的学习还包括如何测试程序，确保它们不会产生错误结果。这可能涉及单元测试、集成测试和压力测试等多种测试方法。此外，课程通常要求学生具备一定的先修知识，如离散数学、数据结构、数值分析和C语言程序设计。
为了深入学习算法分析与设计，推荐使用指定教材，如《计算机算法基础》（余祥宣，崔国华，邹海明著）和参考书籍，如《算法引论》（张益新，沈雁著）及《算法设计与分析》（周培德著）。通过这些资源，学生可以系统地学习并掌握计算机科学中这一至关重要的主题，从而更好地应用算法解决实际问题。
