算法分析与设计

算法分析与设计教案教案一：算法复杂度与算法分析一、教学目标：1.理解算法复杂度的概念2.掌握算法复杂度的计算方法3.能够通过算法复杂度分析算法的效率4.学会如何选择适合的算法二、教学内容：1.算法复杂度概述a.时间复杂度和空间复杂度的概念b.算法的执行时间和占用空间的计算方法c.算法的最好情况、平均情况和最坏情况的概念和关系2.算法复杂度分析a.常见的算法复杂度i.常数阶ii. 对数阶iii. 线性阶iv. 线性对数阶v.平方阶b.算法复杂度的表示方法和计算示例3.算法效率的比较与选择a.算法效率的评价标准b.如何选择适合的算法c.通过实际例子对比算法效率三、教学方法：1.讲授理论知识，介绍算法复杂度的概念和计算方法2.针对具体算法实例，进行算法复杂度的分析和计算3.进行实际例子的比较，分析不同算法的效率四、教学过程：教师活动学生活动教学方法时间引入介绍本节课的内容和目标倾听并记录讲授 5分钟讲解介绍算法复杂度概念和分类倾听并记录讲授 15分钟示例分析通过具体例子分析和计算算法复杂度思考并记录讲授和讨论20分钟案例分析分析不同算法的效率，并选择合适的算法思考并讨论讲授和讨论20分钟总结总结本节课的内容和要点倾听并记录讲授 5分钟五、教学资源：1.PPT课件2.计算器3.教材和参考书籍六、教学评估：通过学生的课堂参与情况、小组讨论和问题回答情况来评估学生对算法复杂度与算法分析的掌握情况。

七、教学延伸：1.可邀请相关行业的专业人士进行讲座，分享在实际工程中使用算法复杂度和算法分析的经验2.给学生布置一些算法的分析和设计任务，让学生通过实际动手操作来深入理解算法复杂度与算法分析的概念和方法。

教案二：动态规划的基本原理与应用一、教学目标：1.理解动态规划的基本原理和思想2.掌握动态规划的基本步骤和方法3.能够使用动态规划解决实际问题4.学会如何设计动态规划的算法二、教学内容：1.动态规划概述a.动态规划的定义和基本思想c.动态规划的基本步骤和方法2.动态规划的应用a.最优子结构的性质b.重叠子问题的性质c.通过子问题的解计算原问题的解d.动态规划的算法设计与实现3.动态规划的经典问题a.背包问题b.最长公共子序列问题c.最短路径问题d.斐波那契数列问题三、教学方法：1.讲授理论知识，介绍动态规划的基本原理和方法2.运用具体问题进行示例分析，演示动态规划的应用和算法设计3.进行实际问题的解决，让学生亲自动手设计动态规划算法四、教学过程：教师活动学生活动教学方法时间引入介绍本节课的内容和目标倾听并记录讲授 5分钟讲解介绍动态规划的概念和基本原理倾听并记录讲授 15分钟示例分析通过具体问题示例进行动态规划的分析和解决思考并记录讲授和演示 20分钟算法设计学生自主设计动态规划算法并进行实际问题的解决思考并动手实践讨论和指导25分钟总结总结本节课的内容和要点倾听并记录讲授 5分钟五、教学资源：1.PPT课件2.教材和参考书籍3.计算器六、教学评估：通过学生的课堂参与情况、小组讨论和问题回答情况来评估学生对动态规划的理解和应用掌握情况。

电大计算机本科_算法设计与分析
算法设计与分析是计算机科学和数学领域的重要课程。

它涉及到一系
列算法设计、分析和实现的方面，涉及到算法流程、语法、数据结构等多
方面。

在算法设计与分析这门课程中，学生首先要学习怎么设计一个算法，
怎么从实际问题中提取算法，怎么分析算法复杂度，怎么评价算法效率。

接下来要学习算法，基本排序算法和选择算法，分治算法，贪婪算法，动
态规划，回溯算法，朴素贝叶斯，马尔科夫链等等各种算法。

学生还要熟
悉现代算法建模工具（如Matlab、SAS、C++），熟悉算法的优化技巧，
掌握算法的编码实现方法，并研究其实际应用。

本课程可以使学生充分发挥自己的能力，培养学生的算法设计能力，
提高实践能力，掌握算法的基本原理及运用，把握算法分析及其优化技术。

它不仅帮助学生提高数学思维能力，同时也有助于他们在计算机编程方面
的能力。

学习算法设计与分析有助于学生全面掌握算法设计这一重要组成
部分，也可以拓展学生的应用领域，使学生更具有竞争力。

学习算法设计与分析也有其困难之处，首先是算法编程比较抽象，学
生需要有较强的理论功底和数学能力。

单选题1.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是()。

A.快速排序B.堆排序C.归并排序D.直接插入排序答案:C2.下面命名规则中，哪项不是现在比较常用的命名规则()。

A.匈牙利命名法B.骆驼命名法C.下划线命名法D.图灵命名法答案:D3.十进制的123，1的位权是（）。

A.1B.2C.10D.100答案:D4.一个良好算法的基本单元是：顺序结构、循环结构和()。

A.线性结构B.离散结构C.数据结构D.选择结构答案:D5.遗传算法用于解决()。

A.排序问题B.规划问题C.最优化问题D.决策问题答案:C6.下列叙述中正确的是（）A.数据的逻辑结构与存储结构必定是一一对应的B.由于计算机在存储空间上是向量式的存储结构，因此，利用数组只能处理线性结构C.程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D.以上说法都不对答案:D7.按F5开始调试，程序便会直接运行到断点处。

接下来可以逐行来运行程序，查看各个变量的值，也可以直接运行到下一个断点或程序结束，这样过程被称作()。

A.设置断点B.单步调试C.程序编译D.程序调试答案:B8.下列说法错误的是()A.使用高级计算机语言，如C、C++、Java，编写的程序，都需要经过编译器编译或解释，才能转化成机器能够识别并能执行的二进制代码。

B.如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为调试程序。

C.自动化的工具同样也能够帮助你跟踪程序，尤其当程序很复杂时效果更加明显，这种工具叫做调试器。

D.调试器并能解决程序中出现的问题。

答案:D9.注释从功能上可以分为文件注释、函数注释和()。

A.程序员注释B.功能注释C.时间注释D.版权注释答案:B10.二进制数1101.0101转换为十进制数是（）。

A.11.3225B.12.3125C.13.0125D.13.3125答案:D11.十六进制数C1B转换为二进制数是（）。

计算机算法的设计与分析计算机算法的设计和分析随着计算机技术的不断发展，算法成为了关键的核心技术之一。

算法的设计和分析是指通过一系列的步骤和方法来解决计算机问题的过程。

本文将详细介绍计算机算法的设计和分析。

一、算法设计的步骤：1. 理解和定义问题：首先需要明确所要解决的问题，并对其进行深入的理解，确定问题的输入和输出。

2. 分析问题：对问题进行分析，确定问题的规模、特点和约束条件，以及可能存在的问题解决思路和方法。

3. 设计算法：根据问题的性质和特点，选择合适的算法设计方法，从而得到解决问题的具体算法。

常见的算法设计方法包括贪心算法、分治算法、动态规划算法等。

4. 实现算法：将步骤3中设计的算法转化为计算机程序，并确保程序的正确性和可靠性。

5. 调试和测试算法：对实现的算法进行调试和测试，包括样本测试、边界测试、异常输入测试等，以验证算法的正确性和效率。

二、算法分析的步骤：1. 理解算法的效率：算法的效率是指算法解决问题所需的时间和空间资源。

理解算法的时间复杂度和空间复杂度是进行算法分析的基础。

2. 计算时间复杂度：时间复杂度用来表示算法解决问题所需的时间量级。

常用的时间复杂度包括常数时间O(1)、对数时间O(logn)、线性时间O(n)、平方时间O(n^2)等。

3. 计算空间复杂度：空间复杂度用来表示算法解决问题所需的空间资源量级。

常用的空间复杂度包括常数空间O(1)、线性空间O(n)、指数空间O(2^n)等。

4. 分析算法的最坏情况和平均情况：算法的最坏情况时间复杂度和平均情况时间复杂度是进行算法分析的关键指标。

最坏情况时间复杂度表示在最不利条件下算法所需的时间量级，平均情况时间复杂度表示在一般情况下算法所需的时间量级。

5. 比较算法的优劣：通过对不同算法的时间复杂度和空间复杂度进行分析，可以对算法的优劣进行比较，从而选择合适的算法。

三、常见的算法设计与分析方法：1. 贪心算法：贪心算法通过每一步的选择来寻求最优解，并且这些选择并不依赖于其他选择。

算法设计与分析算法是计算机科学中的核心概念，它是解决问题的一系列步骤和规则的有序集合。

在计算机科学的发展中，算法设计和分析扮演着至关重要的角色。

本文将探讨算法设计和分析的相关概念、技术和重要性。

一、算法设计的基本原则在设计算法时，需要遵循一些基本原则来确保其正确性和有效性：1. 正确性：算法设计应确保能够正确地解决给定的问题，即输出与预期结果一致。

2. 可读性：设计的算法应具有清晰的结构和逻辑，易于理解和维护。

3. 高效性：算法应尽可能地减少时间和空间复杂度，以提高执行效率。

4. 可扩展性：算法应具备良好的扩展性，能够适应问题规模的变化和增长。

5. 可靠性：设计的算法应具备稳定性和鲁棒性，对不同的输入都能给出正确的结果。

二、常见的算法设计技术1. 枚举法：按照规定的顺序逐个尝试所有可能的解，直到找到满足条件的解。

2. 递归法：通过将一个大问题分解成若干个小问题，并通过递归地解决小问题，最终解决整个问题。

3. 贪心算法：在每个阶段选择最优解，以期望通过一系列局部最优解达到全局最优解。

4. 分治算法：将一个大问题划分成多个相互独立的子问题，逐个解决子问题，并将解合并得到整体解。

5. 动态规划：通过将一个大问题分解成多个小问题，并存储已解决子问题的结果，避免重复计算。

三、算法分析的重要性算法分析可以评估算法的效率和性能。

通过算法分析，可以：1. 预测算法在不同规模问题上的表现，帮助选择合适的算法解决具体问题。

2. 比较不同算法在同一问题上的性能，从而选择最优的算法。

3. 评估算法在不同硬件环境和数据集上的表现，选择最适合的算法实现。

四、常见的算法分析方法1. 时间复杂度：衡量算法所需执行时间的增长率，常用的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)和O(n^2)等。

2. 空间复杂度：衡量算法所需占用存储空间的增长率，常用的空间复杂度有O(1)、O(n)和O(n^2)等。

3. 最坏情况分析：对算法在最不利情况下的性能进行分析，可以避免算法性能不稳定的问题。

算法分析与设计在计算机科学领域，算法是解决问题的一种方法或步骤。

对于任何给定的问题，可能有许多不同的算法可用于解决。

算法的效率直接影响着计算机程序的性能，在实践中，我们通常需要进行算法分析和设计来确保程序的高效性和可靠性。

算法分析算法分析是用来评估算法性能的过程。

主要关注的是算法的效率和资源消耗。

常见的算法分析方法包括时间复杂度和空间复杂度。

时间复杂度时间复杂度描述了算法运行时间随输入规模增加而增加的趋势。

通常用大O符号表示，比如O(n)、O(log n)等。

时间复杂度越低，算法执行速度越快。

空间复杂度空间复杂度描述了算法在运行过程中所需的内存空间大小。

同样用大O符号表示。

空间复杂度越低，算法消耗的内存越少。

算法设计算法设计是指为了解决特定问题而创造新的算法的过程。

常见的算法设计方法包括贪心算法、分治法、动态规划等。

贪心算法贪心算法是一种在每一步选择当前状态下最优解的算法。

虽然贪心算法并不总是能得到全局最优解，但它的简单性和高效性使其在实际应用中很受欢迎。

分治法分治法将复杂问题分解为子问题来求解，然后将子问题的解合并起来得到原问题的解。

典型的应用有归并排序和快速排序等。

动态规划动态规划是一种将问题分解为重叠子问题、并存储子问题解的方法。

通过利用已解决的子问题来解决更大规模的问题，动态规划能够显著提高算法的效率。

结语算法分析和设计是计算机科学中至关重要的一部分，它帮助我们理解算法的效率和性能，并指导我们选择合适的算法来解决问题。

通过不断学习和实践，我们可以不断提升自己在算法领域的能力，为创造更高效、更可靠的计算机程序做出贡献。

算法分析与设计试题及答案一、选择题1. 下列哪个是属于分治算法的例子？A. 冒泡排序B. 归并排序C. 顺序查找D. 选择排序答案：B2. 在排序算法中，时间复杂度最优的是：A. 冒泡排序B. 插入排序C. 归并排序D. 快速排序答案：C3. 哪个不是动态规划的特点？A. 具有重叠子问题B. 通过递归求解C. 需要保存子问题的解D. 具有最优子结构答案：B4. 在图的广度优先搜索算法中，使用的数据结构是：A. 栈B. 队列C. 数组D. 堆栈答案：B5. 在最小生成树算法中，下列哪个不属于贪心策略？A. Kruskal算法B. Prim算法C. Dijkstra算法D. Prim-Kruskal混合算法答案：C二、简答题1. 请简述分治算法的思想和应用场景。

答案：分治算法的思想是将原问题分解成若干个规模较小且类似的子问题，然后解决子问题，最后将子问题的解合并得到原问题的解。

其应用场景包括排序算法（如归并排序、快速排序）、搜索算法（如二分查找）等。

2. 什么是动态规划算法？请给出一个动态规划算法的示例。

答案：动态规划算法是一种通过将问题分解成子问题并解决子问题来解决复杂问题的方法。

它的特点是具有重叠子问题和最优子结构性质。

以斐波那契数列为例，可以使用动态规划算法求解每一项的值，而不需要重复计算。

3. 图的深度优先搜索和广度优先搜索有什么区别？答案：图的深度优先搜索（Depth First Search，DFS）是一种先访问子节点再访问兄弟节点的遍历算法，通常使用递归或者栈实现。

而广度优先搜索（Breadth First Search，BFS）则是以层次遍历的方式展开搜索，使用队列来实现。

DFS更适合用于搜索路径，BFS则适用于寻找最短路径等。

4. 请简述贪心算法的特点及其应用场景。

答案：贪心算法的特点是每一步都采取当前状态下最优的选择，以期望得到全局最优解。

然而，贪心算法并不一定能求解所有问题的最优解，但对于一些特定问题，贪心算法往往能得到近似最优解。

《算法分析与设计》课程复习资料一、名词解释：1.算法2.程序3.递归函数4.子问题的重叠性质5.队列式分支限界法6.多机调度问题7.最小生成树 二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。

2.简述回溯法解题的主要步骤。

3.简述动态规划算法求解的基本要素。

4.简述回溯法的基本思想。

5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。

6.简要分析分支限界法与回溯法的异同。

7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？ 8.贪心算法求解的问题主要具有哪些性质？简述之。

9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。

10.简述分析贪心算法与动态规划算法的异同。

三、算法编写及算法应用分析题：1.已知有3个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。

2.按要求完成以下关于排序和查找的问题。

①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。

②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。

③给出上述算法的递归算法。

④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。

3.已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=12，r 5=5，r 6=50，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序（要求给出计算步骤）。

4.根据分枝限界算法基本过程,求解0-1背包问题。

已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。

一、选择题（20分）1．最长公共子序列算法利用的算法是（B ）。

A、分支界限法B、动态规划法C、贪心法D、回溯法2．实现棋盘覆盖算法利用的算法是（A ）。

A、分治法B、动态规划法C、贪心法D、回溯法3.下面是贪心算法的基本要素的是（C ）。

A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解4.回溯法的效率不依赖于下列哪些因素（ D ）A.满足显约束的值的个数B. 计算约束函数的时间C. 计算限界函数的时间D. 确定解空间的时间5.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ）A．递归函数 B.剪枝函数C。

随机数函数 D.搜索函数6．采用最大效益优先搜索方式的算法是（A ）。

A、分支界限法B、动态规划法C、贪心法D、回溯法7．贪心算法与动态规划算法的主要区别是（B ）。

A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解8. 实现最大子段和利用的算法是（B ）。

A、分治策略B、动态规划法C、贪心法D、回溯法9.优先队列式分支限界法选取扩展结点的原则是（C ）。

A、先进先出B、后进先出C、结点的优先级D、随机10.下列算法中通常以广度优先方式系统搜索问题解的是（A）。

A、分支限界法B、动态规划法C、贪心法D、回溯法二、填空题（22分每空2分）1.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。

2、大整数乘积算法是用分治法来设计的。

3、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。

4、舍伍德算法总能求得问题的一个解。

5、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

6.快速排序template<class Type>void QuickSort (Type a[], int p, int r){if (p<r) {int q=Partition(a,p,r);QuickSort (a,p,q-1); 哈密顿环问题的算法可由回溯法设计实现。

算法分析与设计作业及参考答案作业题目1、请分析冒泡排序算法的时间复杂度和空间复杂度，并举例说明其在实际中的应用场景。

2、设计一个算法，用于在一个未排序的整数数组中找到第二大的元素，并分析其时间复杂度。

3、比较贪心算法和动态规划算法的异同，并分别举例说明它们在解决问题中的应用。

参考答案1、冒泡排序算法时间复杂度：冒泡排序的基本思想是通过相邻元素的比较和交换，将最大的元素逐步“浮”到数组的末尾。

在最坏情况下，数组完全逆序，需要进行 n 1 轮比较和交换，每一轮比较 n i 次（i 表示当前轮数），所以总的比较次数为 n(n 1) ／ 2，时间复杂度为 O(n^2)。

在最好情况下，数组已经有序，只需要进行一轮比较，时间复杂度为 O(n)。

平均情况下，时间复杂度也为 O(n^2)。

空间复杂度：冒泡排序只在原数组上进行操作，不需要额外的存储空间，空间复杂度为 O(1)。

应用场景：冒泡排序算法简单易懂，对于规模较小的数组，或者对算法的简单性要求较高而对性能要求不是特别苛刻的场景，如对少量数据进行简单排序时，可以使用冒泡排序。

例如，在一个小型的学生成绩管理系统中，需要对一个班级的少量学生成绩进行排序展示，冒泡排序就可以满足需求。

2、找到第二大元素的算法以下是一种使用遍历的方法来找到未排序整数数组中第二大元素的算法：｀｀｀pythondef find_second_largest(arr)：largest ＝ arr0second_largest ＝ float(＇inf'）for num in arr:if num ＞ largest:second_largest ＝ largestlargest ＝ numelif num ＞ second_largest and num!＝ largest:second_largest ＝ numreturn second_largest｀｀｀时间复杂度分析：这个算法需要遍历数组一次，所以时间复杂度为O(n)。

习题解析第1章1. 解析：算法主要是指求解问题的方法。

计算机中的算法是求解问题的方法在计算机上的实现。

2. 解析：算法的五大特征是确定性、有穷性、输入、输出和可行性。

3. 解析：计算的算法，其中n是正整数。

可以取循环变量i的值从1开始，算i的平方，取平方值最接近且小于或者等于n的i即可。

4. 解析：可以使用反证法，设i=gcd(m, n)=gcd(n, m mod n)，则设m=a*i，n=b*i，且a与b互质，这时m mod n=（a-x*b）*i，只需要证明b和a-x*b互质，假设二者不互质，可以推出a与b 不互质，因此可以得到证明。

5. 解析：自然语言描述：十进制整数转换为二进制整数采用“除2取余，逆序排列”法。

具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为0时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

流程图：如图*.1图*.1 十进制整数转换成二进制整数流程图6. 解析：a.如果线性表是数组，则可以进行随机查找。

由于有序，因此可以进行折半查找，这样可以在最少的比较次数下完成查找。

b.如果线性表是链表，虽然有序，则只能进行顺序查找，从链表头部开始进行比较，当发现当前节点的值大于待查找元素值，则查找失败。

7. 解析：本题主要是举例让大家了解算法的精确性。

过程中不能有含糊不清或者二义性的步骤。

大家根据可行的方式总结一下阅读一本书的过程即可。

8. 解析：数据结构中介绍的字典是一种抽象数据结构，由一组键值对组成，各个键值对的键各不相同，程序可以将新的键值对添加到字典中，或者基于键进行查找、更新或删除等操作。

由于本题已知元素唯一，因此大家可以据此建立一个自己的字典结构。

实现字典的方法有很多种：•最简单的就是使用链表或数组，但是这种方式只适用于元素个数不多的情况下；•要兼顾高效和简单性，可以使用哈希表；•如果追求更为稳定的性能特征，并且希望高效地实现排序操作的话，则可以使用更为复杂的平衡树。

算法设计与分析算法设计是计算机科学重要的研究方向之一。

其核心目的是在给定的计算机问题下，设计出一种能够高效完成任务的算法。

在算法设计的过程中，需要考虑多种因素，如算法的正确性、可理解性、可维护性、可移植性以及算法的时间和空间复杂度等。

常用的算法设计策略包括贪心算法、动态规划算法、回溯算法、分治算法等多种。

算法的正确性是算法设计的首要考虑因素之一。

如果一个算法不能够正确地解决问题，那么它的时间复杂度和空间复杂度再低也没有用处。

一般来说，算法的正确性可以通过数学证明来进行验证。

根据不同的算法类型，其正确性验证需要应用不同的证明方法。

时间复杂度和空间复杂度也是算法设计的关键考虑因素。

通常，一个算法的时间复杂度越低，运行时间就越短。

同样地，一个算法的空间复杂度越低，需要占用的内存就越少。

时间复杂度和空间复杂度之间通常是矛盾的，因此需要在两者之间做出权衡。

常用的算法比较基准是时间复杂度，时间复杂度大致可以分为常数阶、对数阶、线性阶、平方阶、立方阶等多个级别，并且可能还存在更高阶的时间复杂度。

在算法设计之后，需要进行算法的分析。

算法分析通常包括平均时间复杂度、最坏时间复杂度和最好时间复杂度的分析。

平均时间复杂度指的是在一组随机输入下的平均运行时间，通常是指输入数据分布的随机分布；最坏时间复杂度指的是运行时间的上界，通常是指特殊的输入情况时，算法运行时间达到最大值；最好时间复杂度指的是算法在最理想情况下的运行时间，通常指输入数据已经有序的情况下的运行时间。

除此之外，尚有许多其他因素需要考虑，例如算法的可扩展性、可移植性、可维护性、可复用性等。

其中的可扩展性指的是算法能够处理的数据规模的大小，通常需要根据不同的数据规模进行不同的优化；可移植性指的是算法能够运行在不同的计算机体系结构之上；可维护性指的是算法在输出结果有问题时，能够容易地找到错误所在并进行修改；可复用性指的是算法能够被其他程序员或其他算法模块所复用。

【关键字】分析《算法分析与设计》作业参考答案作业一一、名词解释：1.递归算法：直接或间接地调用自身的算法称为递归算法。

2.程序：程序是算法用某种程序设计语言的具体实现。

2、简答题：1.算法需要满足哪些性质？简述之。

算法是若干指令的有穷序列，满足性质：1）输入：有零个或多个外部量作为算法的输入。

2）输出：算法产生至少一个量作为输出。

3）确定性：组成算法的每条指令清晰、无歧义。

4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。

2.简要分析分治法能解决的问题具有的特征。

分析分治法能解决的问题主要具有如下特征：1）该问题的规模缩小到一定的程度就可以容易地解决；2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3）利用该问题分解出的子问题的解可以合并为该问题的解；4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。

将递归算法转化为非递归算法的方法主要有：1）采用一个用户定义的栈来模拟系统的递归调用工作栈。

该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。

2）用递推来实现递归函数。

3）通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。

后两种方法在时空复杂度上均有较大改善，但其适用范围有限。

三、算法编写及算法应用分析题：1.冒泡排序算法的基本运算如下：for i ←1 to n-1 dofor j ←1 to n-i doif a[j]<a[j+1] then交换a[j]、a[j+1]；分析该算法的时间复杂性。

解答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n的关系。

1）设比较一次花时间1；2）内循环次数为：n-i次,（i=1,…n），花时间为：3）外循环次数为：n-1，花时间为：2.设计一个分治算法计算一棵二叉树的高度。