算法
科技名词定义中文名称：算法英文名称：algorithm定义：模型分析的一组可行的、确定的和有穷的规则。所属学科： [url=http://baike.baidu.com/view/35670.htm]地理学[/url]（一级学科）；[url=http://baike.baidu.com/view/206169.htm]数量地理学[/url]（二级学科）本内容由[url=http://baike.baidu.com/view/1490464.htm]全国科学技术名词审定委员会[/url]审定公布百科名片[url=http://baike.baidu.com/image/b3508d13005a6bbf6538dbc1][img]http://imgsrc.baidu.com/baike/abpic/item/b3508d13005a6bbf6538dbc1.jpg[/img][/url]算法
[float=left]
算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。[/float]
目录[url=http://baike.baidu.com/view/7420.htm#1]算法的定义[/url][list=1][*][url=http://baike.baidu.com/view/7420.htm#1_1]1、有穷性[/url][*][url=http://baike.baidu.com/view/7420.htm#1_2]2、确切性[/url][*][url=http://baike.baidu.com/view/7420.htm#1_3]3、输入[/url][*][url=http://baike.baidu.com/view/7420.htm#1_4]4、输出[/url][*][url=http://baike.baidu.com/view/7420.htm#1_5]5、可行性[/url][/list][url=http://baike.baidu.com/view/7420.htm#2]算法的复杂度[/url][list=1][*][url=http://baike.baidu.com/view/7420.htm#2_1]时间复杂度[/url][*][url=http://baike.baidu.com/view/7420.htm#2_2]空间复杂度[/url][/list][url=http://baike.baidu.com/view/7420.htm#3]算法设计与分析的基本方法[/url][list=1][*][url=http://baike.baidu.com/view/7420.htm#3_1]1.递推法[/url][*][url=http://baike.baidu.com/view/7420.htm#3_2]2.递归[/url][*][url=http://baike.baidu.com/view/7420.htm#3_3]3.穷举搜索法[/url][*][url=http://baike.baidu.com/view/7420.htm#3_4]4.贪婪法[/url][*][url=http://baike.baidu.com/view/7420.htm#3_5]5.分治法[/url][*][url=http://baike.baidu.com/view/7420.htm#3_6]6.动态规划法[/url][*][url=http://baike.baidu.com/view/7420.htm#3_7]7.迭代法[/url][/list][url=http://baike.baidu.com/view/7420.htm#4]算法分类[/url][url=http://baike.baidu.com/view/7420.htm#5]举例[/url][url=http://baike.baidu.com/view/7420.htm#6]算法经典专著[/url][url=http://baike.baidu.com/view/7420.htm#7]算法的历史[/url][url=http://baike.baidu.com/view/7420.htm#1]算法的定义[/url][list=1][*][url=http://baike.baidu.com/view/7420.htm#1_1]1、有穷性[/url][*][url=http://baike.baidu.com/view/7420.htm#1_2]2、确切性[/url][*][url=http://baike.baidu.com/view/7420.htm#1_3]3、输入[/url][*][url=http://baike.baidu.com/view/7420.htm#1_4]4、输出[/url][*][url=http://baike.baidu.com/view/7420.htm#1_5]5、可行性[/url][/list][url=http://baike.baidu.com/view/7420.htm#2]算法的复杂度[/url][list=1][*][url=http://baike.baidu.com/view/7420.htm#2_1]时间复杂度[/url][*][url=http://baike.baidu.com/view/7420.htm#2_2]空间复杂度[/url][/list][url=http://baike.baidu.com/view/7420.htm#3]算法设计与分析的基本方法[/url][list=1][*][url=http://baike.baidu.com/view/7420.htm#3_1]1.递推法[/url][*][url=http://baike.baidu.com/view/7420.htm#3_2]2.递归[/url][*][url=http://baike.baidu.com/view/7420.htm#3_3]3.穷举搜索法[/url][*][url=http://baike.baidu.com/view/7420.htm#3_4]4.贪婪法[/url][*][url=http://baike.baidu.com/view/7420.htm#3_5]5.分治法[/url][*][url=http://baike.baidu.com/view/7420.htm#3_6]6.动态规划法[/url][*][url=http://baike.baidu.com/view/7420.htm#3_7]7.迭代法[/url][/list][url=http://baike.baidu.com/view/7420.htm#4]算法分类[/url][url=http://baike.baidu.com/view/7420.htm#5]举例[/url][url=http://baike.baidu.com/view/7420.htm#6]算法经典专著[/url][url=http://baike.baidu.com/view/7420.htm#7]算法的历史[/url]展开
[url=http://baike.baidu.com/view/7420.htm#]编辑本段[/url]
算法的定义 [b]算法（Algorithm）是一系列解决问题的清晰指令[/b]，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用[b][url=http://baike.baidu.com/view/540497.htm]空间复杂度[/url][/b]与[b][url=http://baike.baidu.com/view/104946.htm]时间复杂度[/url][/b]来衡量。 一个算法应该具有以下五个重要的特征： 算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。1、有穷性 算法的有穷性是指算法必须能在执行有限个步骤之后终止2、确切性 算法的每一步骤必须有确切的定义；3、输入 一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；4、输出 一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；5、可行性 算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成。 [url=http://baike.baidu.com/view/92404.htm]计算机科学[/url]家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》，可见算法在计算机科学界与计算机应用界的地位。[url=http://baike.baidu.com/view/7420.htm#]编辑本段[/url]
算法的复杂度 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。[url=http://baike.baidu.com/view/757280.htm]算法分析[/url]的目的在于选择合适算法和改进算法。一个算法的评价主要从[b]时间复杂度[/b]和[b]空间复杂度[/b]来考虑。时间复杂度 算法的时间复杂度是指执行算法所需要的时间。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做 T(n)=Ο(f(n)) 因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。空间复杂度 算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。 详见百度百科词条"[url=http://baike.baidu.com/view/7527.htm]算法复杂度[/url]"[url=http://baike.baidu.com/view/7420.htm#]编辑本段[/url]
算法设计与分析的基本方法1.递推法 递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的，此方法称为递推法。2.递归 [url=http://baike.baidu.com/view/96473.htm]递归[/url]指的是一个过程：函数不断引用自身，直到引用的对象已知3.穷举搜索法 [url=http://baike.baidu.com/view/1189634.htm]穷举搜索法[/url]是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。4.贪婪法 [url=http://baike.baidu.com/view/112297.htm]贪婪法[/url]是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。5.分治法 [url=http://baike.baidu.com/view/1583824.htm]分治法[/url]是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。6.动态规划法 [url=http://baike.baidu.com/view/28146.htm]动态规划[/url]是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。7.迭代法 [url=http://baike.baidu.com/view/649495.htm]迭代法[/url]是[url=http://baike.baidu.com/view/295760.htm]数值分析[/url]中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。[url=http://baike.baidu.com/view/7420.htm#]编辑本段[/url]
算法分类 算法可大致分为[b]基本算法[/b]、[b]数据结构的算法[/b]、[b][url=http://baike.baidu.com/view/17568.htm]数论[/url]与代数算法[/b]、[b]计算几何的算法[/b]、[b][url=http://baike.baidu.com/view/79350.htm]图论[/url]的算法[/b]、[b]动态规划[/b]以及[b]数值分析[/b]、[b][url=http://baike.baidu.com/view/155969.htm]加密算法[/url][/b]、[b][url=http://baike.baidu.com/view/297739.htm]排序算法[/url][/b]、[b]检索算法[/b]、[b]随机化算法[/b]、[b]并行算法[/b]。 算法可以宏泛的分为三类： [b]有限的，确定性算法 [/b]这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。 [b]有限的，非确定算法[/b] 这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。 [b]无限的算法[/b] 是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。[url=http://baike.baidu.com/view/7420.htm#]编辑本段[/url]
举例 经典的算法有很多，如："[url=http://baike.baidu.com/view/1241014.htm]欧几里德算法[/url]，[url=http://baike.baidu.com/view/31917.htm]割圆术[/url]，[url=http://baike.baidu.com/view/1431260.htm]秦九韶算法[/url]"。[url=http://baike.baidu.com/view/7420.htm#]编辑本段[/url]
算法经典专著 目前市面上有许多论述算法的书籍，其中最著名的便是《[url=http://baike.baidu.com/view/1078138.htm]计算机程序设计艺术[/url]》（The Art Of Computer Programming) 以及《[url=http://baike.baidu.com/view/98410.htm]算法导论[/url]》（Introduction To Algorithms）。[url=http://baike.baidu.com/view/7420.htm#]编辑本段[/url]
算法的历史 “算法”即演算法的大陆中文名称出自《[url=http://baike.baidu.com/view/52535.htm]周髀算经[/url]》；而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi，因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为"algorism"，意思是阿拉伯数字的运算法则，在18世纪演变为"algorithm"。[url=http://baike.baidu.com/view/795549.htm]欧几里得算法[/url]被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位[url=http://baike.baidu.com/view/39175.htm]程序员[/url]。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为"well-defined procedure"缺少数学上精确的定义，19世纪和20世纪早期的数学家、[url=http://baike.baidu.com/view/1838.htm]逻辑[/url]学家在定义算法上出现了困难。20世纪的英国数学家[url=http://baike.baidu.com/view/2130.htm]图灵[/url]提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为[url=http://baike.baidu.com/view/117065.htm]图灵机[/url]。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要作用的。 [b]求素数的埃拉托塞尼筛法和求方根的开方的方法公式（算法不等于公式，公式却是提供一种算法）[/b] [table]
[tr][td]
[/td][td] 典型算法举例： 历史上有三大算法：1，求最大公约数的欧几里得辗转相除法；2，求素数的埃拉托塞尼筛法；3，求方根的开方算法。后面两种方法都可以用公式表达。 一，求素数的埃拉托塞尼筛法公式。属于递归的。 筛法与公式的关系： 公元前250年同样是古希腊的数学家埃拉托塞尼提出一种筛法： （一）“要得到不大于某个自然数N的所有素数，只要在2---N中将不大于√N的素数的倍数全部划去即可”。 （二）将上面的内容等价转换：“如果N是合数，则它有一个因子d满足1<d≤√N”。（《基础数论》13页，U杜德利着，上海科技出版社）。. （三）再将（二）的内容等价转换：“若自然数N不能被不大于(根号)√N的任何素数整除，则N是一个素数”。见（代数学辞典[上海教育出版社]1985年。屉部贞世朗编。259页）。 （四）这句话的汉字可以等价转换成为用英文字母表达的公式： N=p1m1+a1=p2m2+a2=......=pkmk+ak 。(1) 其中p1，p2，.....，pk表示顺序素数2，3，5，,,,,。a≠0。即N不能是2m+0，3m+0，5m+0，...，pkm+0形。若N<P（k+1）的平方 [注：后面的1，2，3，....，k，（k+1）是脚标，由于打印不出来，凡字母后面的数字或者i与k都是脚标]，则N是一个素数。 （五）可以把（1）等价转换成为用同余式组表示： N≡a1(modp1)， N≡a2(modp2)，.....，N≡ak(modpk)。 (2) 例如，29，29不能够被根号29以下的任何素数2，3，5整除，29=2x14+1=3x9+2=5x5+4。 29≡1(mod2)，29≡2(mod3)， 29≡4(mod5)。29小于7的平方49，所以29是一个素数。 以后平方用“*”表示，即：㎡=m*。 由于（2）的模p1，p2，....，pk 两两互素，根据孙子定理(中国剩余定理）知，（2）在p1p2.....pk范围内有唯一解。 例如k=1时，N=2m+1，解得N=3，5，7。求得了（3，3*）区间的全部素数。 k=2时，N=2m+1=3m+1，解得N=7，13，19； N=2m+1=3m+2，解得N=5，11，17，23。求得了（5，5*）区间的全部素数。 k=3时, ---------------------| 5m+1-|- 5m+2-| 5m+3,| 5m+4.| ---------------------|---------|----------|--------|---------| n=2m+1=3m+1= |--31----|--7, 37-|-13,43|--19----| n=2m+1=3m+2= |-11,41-|-17,47-|--23---|---29---| ------------------------------------------------------------ 求得了（7，7*）区间的全部素数。 仿此下去，可以求得任意大的数以内的全部素数。 二，求方根的开方方法公式; 开方的反馈方法或者叫做自动调节开方。方法是迭代的。 公式： X_(n+1)={X_n+【A/(X^（k-1）)-X_n】1/k} "_"表示下角标，“^”表示上角标。例如，X^2,表示x的平方；X_1表示第一个X。[/td][/tr]
[tr][td]
[/td][/tr]
[/table] [table]
[tr][td]
[/td][td] 例如，A=5，k=3.即开3次方。 公式：X(n+1）=Xn+（A/Xn^2-Xn）1/3 5介于1^3至2^3之间（1的3次方=1，2的3次方=8） X_0可以取1.1，1.2，1.3，1.4，1.5，1.6，1.7，1.8，1.9，2.0都可以。例如我们取2.0.按照公式： 第一步：X_1={2.0+[5/(2.0^2)-2.0]1/3=1.7.}。即5/2×2=1.25，1.25-2=-0.75，0.75×1/3=0.25， 2-0.25=1.75，取2位数值,即1.7。 第二步：X_2={1.7+[5/(1.7^2)-1.7]1/3=1.71}.。即5/1.7×1.7=1.73010，1.73-1.7=0.03，0.03×1/3=0.01， 1.7+0.01=1.71。取3位数，比前面多取一位数。 第三步：X_3={1.71+[5/(1.71^2)-1.71]1/3=1.709} 第四步：X_4={1.709+[5/(1.709^2)-1.709]1/3=1.7099}. 这种方法可以自动调节，第一步与第三步取值偏大，但是计算出来以后输出值会自动转小；第二步，第四步输入值偏小，输出值自动转大。X_4=1.7099. 当然也可以取1.1，1.2，1.3，。。。1.8，1.9中的任何一个。 ......a必须大于或等于零``，即a为非负数 开平方公式 X（n + 1） = Xn + (A / Xn − Xn)1 / 2.。（n，n+1与是下角标） 例如，A=5： 5介于2的平方至3的平方;之间。我们取初始值2.1，2.2，2.3，2.4，2.5，2.6，2.7，2.8，2.9都可以，我们最好取 中间值2.5。 第一步：2.5+（5/2.5-2.5)1/2=2.2； 即5/2.5=2，2-2.5=-0.5，-0.5×1/2=-0.25，2.5+(-0.25)=2.25，取2位数2.2。 第二步：2.2+(5/2.2-2.2)1/2=2.23； 即5/2.2=2.27272，2.27272-2.2=-0.07272，-0.07272×1/2=-0.03636，2.2+0.03636=2.23。取3位数2.23。 第三步：2.23+(5/2.23-2.23)1/2=2.236。 即5/2.23=2.2421525，,2.2421525-2.23=0.0121525，,0.0121525×1/2=0.00607，,2.23+0.006=2.236.，取4位数。 每一步多取一位数。这个方法又叫反馈开方，即使你输入一个错误的数值，也没有关系，输出值会自动调节，接近准确值。 例如A=200. 200介如10的平方---20的平方之间。初始值可以取11，12，13，14，15，16，17，18，19。我们去15. 15+（200/15-15)1/2=14。取19也一样得出14.。：19+（200/19-19)1/2=14.。 14+(200/14-14)1/2=14.1。 14.1+（200/14.1-14.1)1/2=14.14. 中间值，即1.5。 1.5+（5/1.5^2;-1.5）1/3=1.7。 顺便介绍开5次方公式： X(n+1)=Xn+(A/X^4-Xn)1/5 . (n，n+1是下角标） 例如：A=5; 5介入1的5次方至2的5次方之间。2的5次方是32，5靠近1的5次方。初始值可以取1.1，1.2，1.3，1.4，1.5，1.6，1.7，1.8，1.9.例如我们取中间值1.4； 1.4+（5/1.4^4-1.4)1/5=1.38 1.38+（5/1.38^4-1.38)1/5=1.379. 1.379+(5/1.379^4-1.379)1/5=1.3797. 计算次数与精确度成为正比。即5=1.3797^5.。 这个方法的依据是根据牛顿切线法得来。也可以通过牛顿二项式定理推出。（王晓明） 三，求最大公约数的欧几里得算法还没有找到公式。[/td][/tr]
[/table]
页:
[1]