算法及其发展历程.doc

《算法及其发展历程.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法及其发展历程(资料来源：维基百科)算法(Algorithm)是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。一个算法应该具有以下五个重要的特征：一个算法必须保证执

2、行有限步之后结束;算法的每一步骤必须有确切的定义；1、有穷性2、确切性3、输入：一个算法有。个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是亳无意义的；5、可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。计算机科学家尼克劳斯•沃思曾著过一木著名的书《数据结构十算法二程序》，可见算法在计算机科学界与计算机应用界的地位。［编辑本段1算法的复杂度同一问题可用不同算法解决，而一个算法的质量优劣将影响

3、到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。时间复杂度算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n的函数f(n),算法的时间复杂度也因此记做T(n)=O(f(n))因此，问题的规模n越大，算法执行的时间的增长率与f(n)的增长率正相关，称作渐进时间复杂度(AsymptoticTimeComplexity)。空间复杂度算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间

4、复杂度相比，空间复杂度的分析要简单得多。详见百度百科词条”算法复杂度”［编辑本段1算法设计与分析的基本方法1.递推法递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻儿步的关系，从而达到目的，此方法称为递推法。2.递归递归指的是一个过程：函数不断引用自身，直到引用的对象已知3.穷举搜索法穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。4.贪婪法贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为

5、它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。5.分治法把一个殳杂的问题分成两个或更多的相同或相似的了问题，再把了问题分成更小的了问题......直到最后了问题可以简单的直接求解，原问题的解即了问题的解的合并。6.动态规划法动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠了问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过了问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算

6、机科学和工程领域。7.迭代法迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。［编辑本段1算法分类算法町大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法，算法可以宏泛的分为三类：有限的，确定性算法这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。有限的，非确定算法这

7、类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。无限的算法是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。［编辑本段1举例经典的算法有很多，［编辑本段1如：”欧儿里德算法,割圆术,秦九韶算法”。算法经典专著目前市面上有许多论述算法的书籍，其中最著名的便是《计算机程序设计艺术》(TheArtOfComputerProgramming)以及《算•法导论》(IntroductionToAlgorithms

8、)o［编辑本段1算法的历史“算法”即演算法的大陆中文名称出自《周髀算经》；而英文名称Algorithm来自于9世纪波斯数学家al-Khwarizmi,因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为“algorism”，意思是阿拉伯数字的运算