下载文档原格式
几种常见的算法案例分析算法不仅是数学及其应用的重要的组成局部，也是计算机科学的重要根底，其中算法的重要思想在几种常见的算法例案中得以较好的表达。
本文从几种常见算法案例出发，来探究一下算法的内涵。
一、辗转相除法所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数，假设余数不为零，那么将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，那么这时的较小的数就是原来两个数的最大公约数。
例1． 写出求两个正数,()a b a b >的最大公约数的一个算法。
算法设计：第一步：输入两个正整数,()a b a b >；第二步：把a b ÷的余数赋予r ；第三步：如果0r ≠，那么把b 赋予a ，把r 赋予b ，转到第二步；否那么转到第四步；第四步：输入最大公约数b 。
程序框图下列图所示：用伪代码表示：input “a=,b=〞；a,bdo r=mod(a,b)a=bb=rloop until r=0print bend二、更相减损术所谓更相减术，就是对于给定的两个数，以其中较大的数减去较小的数，然后将差和较小的数构成一对新数，再用较大的数减去较小的数，反复执行此步骤，直到差数和较小的数相等，此时相等的两个数就是原两个数的最大公约数。
在我国古代的<<九章算术>>中有这样的描述“约分术曰：可半者半之，不可半者会置分母分子之数，以少减多，更相损减，求其等也，以等数约之。
〞意思是说如果分母、分子都是偶数，那么先除以2；如果不全是偶数，便将分子与分母互减，以少减多，直到得出最大公约数为止，用最大公约数约分子与分母，便可使分数最简。
如果两个数都是偶数，也不除以2，直接求最大公约数。
这是一种多么奇妙的方法啊，我们古代人在许多方面都比西方先进，这是值得我们自豪的。
以上题为例，算法可以这样来设计：第一步：输入两个正整数,()a b a b >；第二步：假设a 不等于b ，那么执行第三步；否那么执行第五步；第三步：把a b -的差赋予r ；第四步：如果b r >，那么把b 的值赋予a ，否那么把r 的值赋予a ，执行第二步； 第五步：输出最大公约数b 。
计算机五大算法范文
一、排序算法
1. 冒泡排序（Bubble Sort）：冒泡排序算法是比较两个相邻的元素，将值大的元素交换至右端。
两两比较得到最大值后，再进行下一轮比较，
直至最后一个元素。
依次比较相邻的两个元素，将大的数放在后面，小的
数放在前面，一次排序过程把最大的数放到最后的位置。
2. 选择排序（Selection Sort）：选择排序法是每次选出最小的值
与第一个位置的值进行交换，比较完毕后，第一个位置的值是最小的，然
后再比较第二个位置与剩余的值中的最小值，将最小值放到第二个位置之后，依次类推，直到最后一个位置为止。
3. 插入排序（Insertion Sort）：插入排序法的思想是将一个数插
入到已排序区域，将有序区域右移，腾出空间给插入被操作数。
比如将一
个数据插入到一个有序序列时，可以从有序序列的最右边开始，比较当前
位置和插入的被操作数，如果比插入的被操作数要大，将该有序序列元素
右移一位，再与被操作数比较；如果比被操作数小，将该被操作数插入到
这个位置，这样通过一轮比较就可以找到有序序列中要插入位置。
4. 希尔排序（Shell Sort）：希尔排序是插入排序的一种，它通过
不断减小增量来不断改善排序性能。
常用算法举例范文在计算机科学中，算法是解决问题的一系列有序步骤，它能够帮助我们解决各种各样的问题。
以下是一些常用的算法及其举例：1.排序算法：-冒泡排序：通过比较相邻元素并交换位置来将最大的元素逐渐移动到数组的末尾。
-快速排序：选择一个基准元素，将数组分为两部分，左边的元素小于基准，右边的元素大于基准，然后递归地对两部分进行快速排序。
-归并排序：将数组划分为两个子数组，对每个子数组分别进行归并排序，然后将两个有序子数组合并成一个有序数组。
2.查找算法：-二分查找：对于有序数组，通过与中间元素进行比较，将查找范围缩小一半，直到找到目标元素或确定不存在。
-哈希查找：通过将关键字映射到数组的索引位置来进行查找，可以在常数时间内找到目标元素。
3.图算法：-广度优先（BFS）：从起始节点开始，逐层遍历图中的节点，直到找到目标节点。
-深度优先（DFS）：从起始节点开始，沿着一条路径一直向下，直到找到目标节点或无法继续为止。
4.动态规划算法：-背包问题：给定一组物品和一个容量限制，选择一些物品放入背包中，使得总价值最大。
-最长公共子序列（LCS）：给定两个字符串，找到它们的最长公共子序列的长度。
5.数学算法：-欧几里得算法：计算两个整数的最大公约数。
-快速幂算法：计算一个数的幂运算，通过将指数进行二进制拆分来减少计算次数。
6.字符串处理算法：-KMP算法：通过利用已匹配字符的信息来避免不必要的回溯，实现高效的字符串匹配。
- Boyer-Moore算法：利用模式串中的信息来进行快速的字符串匹配。
7.图像处理算法：-图像平滑算法：通过对图像进行滤波处理，去除图像中的噪声，使其更加平滑。
-图像边缘检测算法：通过检测图像中的边缘信息，突出物体的轮廓。
8.机器学习算法：-K均值聚类算法：将数据集划分为K个簇，使得同一个簇内的数据点之间的距离最小化。
-支持向量机（SVM）：将数据集映射到高维空间，并通过找到最优的超平面来实现分类。
程序员常用的算法及其实现方法作为技术人员，程序员们经常需要解决一些算法问题。
算法是程序设计的基础，可以帮助程序员更有效地解决问题。
本文将介绍几种常用的算法及其实现方法，帮助程序员更好地应对算法问题。
一、排序算法在编程中，排序算法是最常见的算法之一。
常见的排序算法有冒泡排序、选择排序、快速排序、归并排序等。
1.冒泡排序冒泡排序是一种简单的排序算法，时间复杂度为O(n^2)。
其基本思想是比较相邻的元素，如果前一个元素大于后一个元素，则交换两个元素的位置，直到数组排好序为止。
冒泡排序的实现方法如下：void bubbleSort(int arr[], int n)int i, j;for (i = 0; i < n-1; i++)for (j = 0; j < n-i-1; j++)if (arr[j] > arr[j+1])swap(&arr[j], &arr[j+1]);}其中swap函数为交换两个元素的值的函数。
2.选择排序选择排序是一种常用的排序算法，时间复杂度同样为O(n^2)。
其基本思想是在未排序的数组中选择最小的元素，将其放在已排序的数组的末尾，反复执行该操作，直到将整个数组排好序为止。
选择排序的实现方法如下：void selectionSort(int arr[], int n)int i, j, min_idx;for (i = 0; i < n-1; i++){min_idx = i;for (j = i+1; j < n; j++)if (arr[j] < arr[min_idx])min_idx = j;swap(&arr[min_idx], &arr[i]);}}3.快速排序快速排序是一种高效的排序算法，其时间复杂度为O(nlogn)。
其基本思想是选取一个基准值，将数组分为两个子数组，将小于等于基准值的元素放到左侧，大于等于基准值的元素放到右侧，然后对左右两个子数组分别进行递归排序。
程序设计五大算法算法是计算机程序设计中非常重要的概念，它是一系列解决问题的步骤和规则。
在程序设计中，有许多经典的算法被广泛应用于各种领域。
下面将介绍程序设计中的五大算法，包括贪心算法、分治算法、动态规划算法、回溯算法和图算法。
1. 贪心算法贪心算法是一种简单而高效的算法，它通过每一步都选择当前最优解来达到全局最优解。
贪心算法通常适用于那些具有最优子结构的问题，即问题的最优解可以通过子问题的最优解来推导。
例如，找零钱问题就可以使用贪心算法来解决，每次选择面额最大的硬币进行找零。
2. 分治算法分治算法将问题分解成更小的子问题，然后递归地求解这些子问题，最后将子问题的解合并起来得到原问题的解。
分治算法通常适用于那些可以被划分成多个相互独立且相同结构的子问题的问题。
例如，归并排序就是一种典型的分治算法，它将待排序的数组不断划分成两个子数组，然后分别对这两个子数组进行排序，最后将排序好的子数组合并成一个有序数组。
3. 动态规划算法动态规划算法通过将问题划分成多个重叠子问题，并保存子问题的解来避免重复计算，从而提高算法的效率。
动态规划算法通常适用于那些具有最优子结构和重叠子问题的问题。
例如，背包问题就可以使用动态规划算法来解决，通过保存每个子问题的最优解，可以避免重复计算，从而在较短的时间内得到最优解。
4. 回溯算法回溯算法是一种穷举法，它通过尝试所有可能的解，并回溯到上一个步骤来寻找更好的解。
回溯算法通常适用于那些具有多个决策路径和约束条件的问题。
例如，八皇后问题就可以使用回溯算法来解决，通过尝试每个皇后的位置，并检查是否满足约束条件，最终找到所有的解。
5. 图算法图算法是一类专门用于处理图结构的算法，它包括图的遍历、最短路径、最小生成树等问题的解决方法。
图算法通常适用于那些需要在图结构中搜索和操作的问题。
例如，深度优先搜索和广度优先搜索就是两种常用的图遍历算法，它们可以用于解决迷宫问题、图的连通性问题等。
什么是算法举例说明常见的算法在计算机科学和数学领域，算法是一套有序的步骤，用于解决问题或获取某个结果。
它可以被看作是一种计算机程序的逻辑描述，能够通过输入得到所需的输出。
算法广泛应用于计算机科学、人工智能、数据处理等领域。
本文将举例说明一些常见的算法，帮助读者更好地理解什么是算法以及它们在实际应用中的作用。
一、排序算法排序算法是将一组数据按照特定的规则进行排序的算法。
常见的排序算法有冒泡排序、选择排序、插入排序、归并排序、快速排序等。
下面举例说明一种常见的排序算法——冒泡排序。
冒泡排序算法的基本思想是重复地遍历待排序的元素，比较相邻两个元素的大小，如果顺序错误就交换它们，直到所有元素都排好序为止。
举例说明：假设有一个整数数组arr = [5, 2, 8, 6, 3]，现在我们要对它进行冒泡排序。
第一轮比较：5 > 2，交换两个元素位置，arr = [2, 5, 8, 6, 3]5 < 8，不用交换8 > 6，交换两个元素位置，arr = [2, 5, 6, 8, 3]8 > 3，交换两个元素位置，arr = [2, 5, 6, 3, 8]第一轮比较结束后，最大的元素8已经排在最后。
第二轮比较：2 < 5，不用交换5 > 6，交换两个元素位置，arr = [2, 5, 6, 3, 8]6 > 3，交换两个元素位置，arr = [2, 5, 3, 6, 8]第二轮比较结束后，第二大的元素6已经排在倒数第二。
继续进行下一轮比较，直到所有元素都排好序。
排序结束后，结果为arr = [2, 3, 5, 6, 8]，数组中的元素按照从小到大的顺序排列。
二、查找算法查找算法是在给定的数据集合中寻找特定元素的算法。
常见的查找算法有线性查找、二分查找等。
下面举例说明一种常见的查找算法——二分查找。
二分查找是一种高效的查找算法，但要求要查找的数据集必须是有序的。
举例说明：假设有一个有序整数数组arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]，现在我们要在其中查找数字9。
计算机五大算法
计算机五大算法指的是分治算法、动态规划算法、贪心算法、回溯算法和分支定界算法。
这些算法在计算机科学中被广泛使用，可以解决各种问题，从排序和搜索到最优化和最大化问题。
分治算法是一种递归算法，它将问题分解成更小的子问题，然后将子问题的解组合成原问题的解。
它常用于排序算法，如归并排序和快速排序。
动态规划算法也是一种递归算法，但它通常用于解决最优化问题。
动态规划将问题分解成更小的子问题，并将子问题的最优解保存下来以便后续使用。
它通常用于计算最短路径、最长公共子序列等问题。
贪心算法是一种启发式算法，它基于贪心策略，在每个步骤中选择当前最优解，希望达到全局最优解。
贪心算法通常用于优化问题，如霍夫曼编码和最小生成树问题。
回溯算法是一种搜索算法，它尝试找到所有可能的解，并选择其中符合条件的解。
回溯算法通常用于解决组合问题，如八皇后和组合求和问题。
分支定界算法是一种搜索算法，它通过将搜索空间分解成更小的子集来减少搜索次数。
分支定界算法通常用于解决最大化问题，如背包问题和最大流问题。
这五种算法在不同的场景下都有其独特的优势和应用，它们共同构成了计算机科学中的基础算法之一。
- 1 -。
计算机科学中的经典算法及其应用计算机科学中的算法可以被定义为一组清晰的指令，这组指令可以在计算机上被执行以完成特定的任务。
计算机科学中有许多经典的算法，这些算法在计算机科学领域中被广泛使用。
本文将讨论一些在计算机科学领域中广泛使用的算法及其应用。
1.排序算法排序算法用于将一组元素按照特定的顺序排列。
排序算法在计算机科学中非常重要，由于数据的快速排序和检索是许多应用的基础，如数据库管理和搜索引擎等。
一些常见的排序算法包括冒泡排序、选择排序、插入排序、快排和归并排序。
其中，快排和归并排序是最快的排序算法，因为它们的时间复杂度为O(nlogn)。
例如，在线商店中，当顾客进行全站搜索时，网站会使用快速排序算法将搜索结果按照相关性和价格排序，以便顾客更好地了解他们所需的商品。
2.哈希算法哈希算法用于将给定的输入映射到固定长度的输出，称为哈希值。
哈希算法广泛用于数据存储和加密等领域。
由于哈希算法对于敏感数据的保护及其在图像和音频等领域中的广泛应用，所以在当前的计算机领域中非常重要。
例如，在社交媒体网站中，当用户上传一张照片时，网站会使用哈希算法将该照片的数字签名与其他用户上传的照片进行比较，以确定是否有重复。
3.查找算法查找算法用于在给定的集合中查找特定的元素。
查找算法是计算机科学中最基本的算法，广泛用于计算机科学领域中。
查找算法包括顺序查找、二分查找和哈希表查找等。
其中，顺序查找最简单的查找算法，但它的时间复杂度比其他查找算法高。
相反，二分查找和哈希表查找算法具有更高的效率和更短的执行时间。
例如，当用户在在线电商网站中搜索商品时，网站将使用二分查找算法对商品目录进行搜索，以便提供更准确和更迅速的搜索结果。
4.图形算法图形算法广泛应用于三维图形和虚拟现实等领域。
它们用于计算物体的三维坐标、旋转、缩放和平移，并使计算机生成逼真的图像。
在计算机科学领域，图形算法包括光线追踪、多边形填充和纹理映射等。
光线追踪算法用于快速计算光线与物体之间的交点，以便计算机生成逼真的图像表面。
计算机算法分析与设计计算机算法分析与设计是计算机科学中的重要领域，涉及到设计和分析各种算法以解决特定问题的方法和技巧。
本文将介绍计算机算法分析与设计的基本概念、常见算法和它们的应用案例。
一、算法分析与设计的概念算法分析与设计是指对解决问题的方法、步骤和操作序列进行评估和设计的过程。
算法分析主要关注算法的效率和性能，通过评估算法的时间复杂度和空间复杂度来衡量算法的优劣。
算法设计则强调如何根据问题的特性和要求来构思和设计算法，以实现高效解决问题的目标。
二、常见算法及其应用案例1. 排序算法排序算法是计算机算法设计中最基本也是最常用的算法之一。
常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序等。
这些算法可以在各种场景中应用，比如对数组、链表等数据结构进行排序，按照规则将数据进行有序排列。
2. 查找算法查找算法用于在给定数据集中搜索目标元素的位置。
常见的查找算法包括线性查找、二分查找、哈希查找等。
这些算法在各种应用中发挥着重要作用，比如在数据库查询、关键词搜索、图像匹配等方面。
3. 图算法图算法用于解决与图相关的问题，如最短路径问题、最小生成树问题、网络流问题等。
著名的图算法包括Dijkstra算法、Kruskal算法、Floyd算法等。
图算法在交通规划、通信网络设计、社交网络分析等领域得到广泛应用。
4. 动态规划算法动态规划算法用于解决一类具有最优子结构的问题，通过将问题分解为较小的子问题，并通过保存子问题的解来避免重复计算，从而得到问题的最优解。
背包问题、最长公共子序列问题等都可采用动态规划算法求解。
5. 贪心算法贪心算法是一种简单而高效的算法策略，它采用每一步局部最优的选择来达到全局最优解。
常见的贪心算法包括霍夫曼编码、Prim算法、Kruskal算法等。
贪心算法在压缩编码、最小生成树等领域有重要应用。
三、算法分析与设计的重要性算法分析与设计在计算机科学中具有重要的地位和作用，主要体现在以下几个方面：1. 效率提升：通过对算法进行分析和设计，可以提高计算机程序的效率和性能。
算法设计案例算法设计案例是指在计算机科学中，通过编写程序来解决特定问题的过程。
这些问题可以是数学问题、数据处理问题、图形问题等等。
下面是一些常见的算法设计案例：1. 排序算法：排序算法是计算机科学中最基本的算法之一。
常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等等。
这些算法的目的是将一组数据按照一定的规则进行排序，以便更方便地进行后续的处理。
2. 图形算法：图形算法是指在计算机图形学中用来处理图形的算法。
常见的图形算法有线段裁剪、多边形填充、三角形剖分等等。
这些算法的目的是将图形进行处理，以便更好地显示在屏幕上。
3. 搜索算法：搜索算法是指在计算机科学中用来搜索特定数据的算法。
常见的搜索算法有深度优先搜索、广度优先搜索、A*搜索等等。
这些算法的目的是在大量数据中找到特定的数据，以便更好地进行后续的处理。
4. 数据压缩算法：数据压缩算法是指在计算机科学中用来压缩数据的算法。
常见的数据压缩算法有哈夫曼编码、LZW编码等等。
这些算法的目的是将大量数据进行压缩，以便更好地存储和传输。
5. 加密算法：加密算法是指在计算机科学中用来加密数据的算法。
常见的加密算法有DES、AES、RSA等等。
这些算法的目的是将数据进行加密，以便更好地保护数据的安全性。
6. 数据挖掘算法：数据挖掘算法是指在计算机科学中用来挖掘数据的算法。
常见的数据挖掘算法有聚类分析、关联规则挖掘、分类算法等等。
这些算法的目的是从大量数据中挖掘出有用的信息，以便更好地进行决策。
7. 机器学习算法：机器学习算法是指在计算机科学中用来训练机器学习模型的算法。
常见的机器学习算法有线性回归、逻辑回归、决策树、支持向量机等等。
这些算法的目的是通过训练机器学习模型来预测未来的数据。
8. 神经网络算法：神经网络算法是指在计算机科学中用来训练神经网络的算法。
常见的神经网络算法有前馈神经网络、循环神经网络、卷积神经网络等等。
这些算法的目的是通过训练神经网络来实现人工智能。
摘要算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
其中最常见的五中基本算法是递归与分治法、动态规划、贪心算法、回溯法、分支限界法。
本文通过这种算法的分析以及实例的讲解，让读者对算法有更深刻的认识，同时对这五种算法有更清楚认识关键词：算法，递归与分治法、动态规划、贪心算法、回溯法、分支限界法AbstractAlgorithm is the description to the problem solving scheme,a set of clear instructions to solve the problem and represents the describe the strategy to solve the problem using the method of system mechanism . That is to say, given some confirm import，the Algorithm will find result In a limited time。
If an algorithm is defective or is not suitable for a certain job, it is invalid to execute it. Different algorithms have different need of time or space, and it's efficiency are different.There are most common algorithms: the recursive and divide and conquer、dynamic programming method、greedy algorithm、backtracking、branch and bound method.According to analyze the five algorithms and explain examples, make readers know more about algorithm , and understand the five algorithms more deeply.Keywords: Algorithm, the recursive and divide and conquer, dynamic programming method, greedy algorithm、backtracking, branch and bound method目录1. 前言 (4)1.1 论文背景 (4)2. 算法详解 (5)2.1 算法与程序 (5)2.2 表达算法的抽象机制 (5)2.3 算法复杂性分析 (5)3．五中常用算法的详解及实例 (6)3.1 递归与分治策略 (6)3.1.1 递归与分治策略基本思想 (6)3.1.2 实例——棋盘覆盖 (7)3.2 动态规划 (8)3.2.1 动态规划基本思想 (8)3.2.2 动态规划算法的基本步骤 (9)3.2.3 实例——矩阵连乘 (9)3.3 贪心算法 (11)3.3.1 贪心算法基本思想 (11)3.3.2 贪心算法和动态规划的区别 (12)3.3.3 用贪心算法解背包问题的基本步骤： (12)3.4 回溯发 (13)3.4.1 回溯法基本思想 (13)3.3.2 回溯发解题基本步骤 (13)3.3.3 实例——0-1背包问题 (14)3.5 分支限界法 (15)3.5.1 分支限界法思想 (15)3.5.2 实例——装载问题 (16)总结 (18)参考文献 (18)1. 前言1.1 论文背景算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。
一个状态到另一个状态的转移不一定是确定的。
随机化算法在内的一些算法，包含了一些随机输入。
计算机的有限资源促使人们关注程序的执行性能，进而催生了计算机算法这一研究领域。
自上世纪60年代开始至今，已出现了大量解决不同问题的有效算法。
由于属于同一问题类的不同问题之间具有相似性，其解决算法也具有一定的共性，因此产生了一般的算法设计技术，如递归技术、分治、动态规划、贪心、图的遍历、回溯、分支限界等。
掌握算法、分析算法、将算法应用到其他领域、创造更高效的算法，是对每一个计算机学着的基本要求。
本文主要分析五中常用的算法（递归与分治法、动态规划、贪心算法、回溯发、分支限界发），以及对相应算法的实例详细讲解。
通过对五中常用算法的单独讲解、综合对比，分析出各种算法的特点以及适用领域，最后列举相应的算法实例，让读者对这五中常用算法有更深的了解。
2. 算法详解2.1 算法与程序算法：是满足下述性质的指令序列。
•输入：有零个或多个外部量作为算法的输入。
•输出：算法产生至少一个量作为输出。
•确定性：组成算法的每条指令清晰、无歧义。
•有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。
程序：是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质(4)即有限性。
2.2 表达算法的抽象机制1.从机器语言到高级语言的抽象高级程序设计语言的主要好处是：（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高2.抽象数据类型抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。
抽象数据类型带给算法设计的好处有：（1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。
2.3 算法复杂性分析算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。
这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。
如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。
一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)。
一般只考虑最坏情况、最好情况和平均情况下的复杂度。
3．五中常用算法的详解及实例3.1 递归与分治策略3.1.1 递归与分治策略基本思想任何一个可以用计算机求解的问题所需要的计算时间都与其规模有关，问题的规模越小，解题所需的时间往往越少，从而比较容易处理，但想直接解决一个较大的问题，有时是相当困难的。
分治法的设计思想，是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分解出来的子问题都可解，并且利用这些子问题的解求出原问题的解，那么这种分治法是可行的。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复使用分治手段，可以使子问题与原问题类型一致而规模却不断减小，最终使子问题缩小到很容易求出其解。
这样就自然导致递归算法的产生。
分治与递归像一对孪生兄弟，经常同时应用在算法设计中，并由此产生许多高效算法。
图3.1 递归与分治策略基本思想其中，|P|表示问题P的规模，n0为一阀值，表示问题P的规模不超过n0，问题已容易求解，不再分解。
Adhoc（P）是该分治法中的基本算法，用于直接解小规模的问题P。
因此，当P的规模不超过n0时，直接用算法Adhoc（P）求解。
算法Merge(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1，P2，P3,…,Pk合并为P的解。
3.1.2 实例——棋盘覆盖(1):问题描述在一个2k×2k（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格，显然，特殊方格在棋盘中出现的位置有4k种情形，因而就有种不同的棋盘(如图3.2)。
图3.2 4×4棋盘格式棋盘覆盖问题要求用如图3.3所示的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
图3.3 4中L型骨牌(2)：算法实现棋盘覆盖问题中数据结构的设计：①棋盘：用二维数组Board[size][size]表示一个棋盘， Board[0][0]是棋盘的左上角方格。
其中size=2k。
为了在递归处理的过程中使用同一个棋盘，将数组Board设为全局变量；②子棋盘：在棋盘数组Board[size][size]中，由子棋盘左上角的下标tr、tc和棋盘边长s表示；③特殊方格：用Board[dr][dc]表示，dr和dc是该特殊方格在棋盘数组Board中的下标；④L型骨牌：一个4k的棋盘中有一个特殊方格，所以用到L型骨牌的个数为( -1)/3将所有L型骨牌从1开始连续编号，用一个全局整型变量tile表示，其初始值为0。
算法的输入参数是：tr:棋盘左上角方格的行号tc:棋盘左上角方格的列号dr:特殊方格所在的行号dc:特殊方格所在的列号(3)算法详细实现图3.4 棋盘覆盖算法本算法的时间复杂度为T（K）=O（4k）,需要骨牌个数为（4k-1）/3,是一个在渐进意义下的最优算法。
3.2 动态规划3.2.1 动态规划基本思想动态规划过程中，每次决策依赖于当前状态，又随即引起状态的转移。
一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
