算法-百度百科

算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。

目录

    算法的定义
    算法的评价
    基本方法
    算法的表示形式
    算法分类
    应用举例
    算法经典专著

算法的定义
　　算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

　　一个算法应该具有以下七个重要的特征：
　　算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。
　　1、有穷性（Finiteness）
　　算法的有穷性是指算法必须能在执行有限个步骤之后终止
　　2、确切性(Definiteness)
　　算法的每一步骤必须有确切的定义；
　　3、输入项(Input)
　　一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
　　4、输出项(Output)
　　一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
　　5、可行性(Effectiveness)
　　算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）；
　　6、 高效性(High efficiency)
　　执行速度快，占用资源少；
　　7、 健壮性(Robustness)
　　对数据响应正确。
　　计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》，可见算法在计算机科学界与计算机应用界的地位。

算法的评价
　　同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
　　1.时间复杂度
　　算法的时间复杂度是指执行算法所需要的时间。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做
　　T(n)=Ο(f(n))
　　因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。
　　2.空间复杂度
　　算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
　　详见百度百科词条"算法复杂度"

基本方法
　　1.递推法
　　递推算法是一种用若干步可重复的简运算（规律）来描述复杂问题的方法.
　　递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。
　　2.递归法
　　程序调用自身的编程技巧称为递归（ recursion）。　一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。　注意：　(1) 递归就是在过程或函数里调用自身;　(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
　　3.穷举法
　　穷举法，或称为暴力破解法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码组合的范围。
　　4.贪婪算法
　　贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。　贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。　对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。　一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。
　　5.分治法
　　分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
　　分治法所能解决的问题一般具有以下几个特征：
　　(1) 该问题的规模缩小到一定的程度就可以容易地解决(2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。(3) 利用该问题分解出的子问题的解可以合并为该问题的解；(4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
　　6.动态规划法
　　动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。
　　动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。
　　7.迭代法
　　迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。
　　8.分枝界限法
　　分枝界限法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。　与贪心算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法效率更高。
算法的表示形式
　　描述算法的方法有多种，常用的有自然语言、结构化流程图、伪代码和PAD图等，其中最普遍的是流程图。

算法分类
　　算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法，厄米变形模型，随机森林算法。。
　　算法可以宏泛的分为三类：
　　有限的，确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。
　　有限的，非确定算法 这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。
　　无限的算法 是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。

应用举例
　　经典的算法有很多，如："欧几里德算法，割圆术，秦九韶算法 ，辗转相除法"。随着计算机的发展，算法在计算机方面已有广泛的发展及应用，如用随机森林算法，来进行头部姿势的估计，用遗传算算法来解决弹yao装载问题，信息加密算法在网络传输中的应用，并行算法在数据挖掘中的应用等。

算法经典专著
　　目前市面上有许多论述算法的书籍，其中最著名的便是《计算机程序设计艺术》（The Art Of Computer Programming) 以及《算法导论》（Introduction To Algorithms）。

算法的历史
　　“算法”即演算法的大陆中文名称出自《周髀算经》；而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi，因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为"algorism"，意思是阿拉伯数字的运算法则，在18世纪演变为"algorithm"。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为"well-defined procedure"缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要作用的。
　　求素数的埃拉托塞尼筛法和求方根的开方的方法公式（算法不等于公式，公式却是提供一种算法）
　　典型算法举例：
　　历史上有三大算法：
　　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。
　　例如，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中的任何一个。
　　开平方公式
　　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。