|
|
解题方案的准确和完整的描述。是一个有穷的动作步骤序列,只有一个初始态,每个动作只有一个后继动作,一步一步地直到序列结束。是解题从开始到结束的动作全过程。 |
|
计算方法 |
|
你的算法最简单 |
|
算术的旧称。 清 昭槤 《啸亭杂录·戴学士》:“公善天文、算法,与 南怀仁 詰论, 怀仁 为之屈。” 清 马建忠 《拟设翻译书院议》:“又算法、几何、八綫、重学、热、光、声、电,与夫飞、潜、动、植、金、石之学,性理格致之书,皆择其尤要而可资讨论者,列为逐日课程。” |
|
计算的方法。《北史·高允传》:“ 允 所製诗赋咏颂箴论表讚誄……凡百餘篇,尤明算法,为《算术》三卷。” 清 袁枚 《随园诗话》卷一:“ 梅定九 先生以算法、《易》理受知 圣祖 。” 清 王应奎 《柳南随笔》卷二:“今人事事不如古人。而有二事却胜之,歷法之密也,算法之巧也。” |
|
算法是指完成一个任务准确而完整的描述。也就是说给定初始状态或输入数据,经过计算机程序的有限次运算,能够得出所要求或期望的终止状态或输出数据。
算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 |
|
“算法”的中文名称出自周髀算经;而英文名称 algorithm 来自于9世纪波斯数学家比阿勒·霍瓦里松的名字al-khwarizmi,因为比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为"algorism",意思是阿拉伯数字的运算法则,在18世纪演变为"algorithm"。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是ada byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序,因此ada byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(charles babbage)未能完成他的巴贝奇分析机,这个算法未能在巴贝奇分析机上执行。 因为"well-defined procedure"缺少数学上精确的定义,19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要的作用。 |
|
输入:一个算法必须有零个或多个输入量。
输出:一个算法应有一个或多个输出量,输出量是算法计算的结果。
确定性:算法的描述必须无歧义,以保证算法的执行结果是确定的。
有穷性:算法必须在有限步骤内实现。注:此处“有限”不同于数学概念的“有限”,天文数字般的有限对于实际问题并无意义。
有效性:又称可行性。能够实现,算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。 |
|
算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务,如计算职工的薪水或打印学生的成绩单。 一般地,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。 |
|
算法的时间复杂度
算法的时间复杂度是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模n 的函数f(n),算法的时间复杂度也因此记做
因此,问题的规模n 越大,算法执行的时间的增长率与f(n) 的增长率正相关,称作渐进时间复杂度(asymptotic time complexity)。
算法的空间复杂度
算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。
非确定性多项式时间(np)
算法的实现
算法不单单可以用计算机程序来实现,也可以在人工神经网络、电路或者机械设备上实现。
例子一
这是算法的一个简单的例子。
我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小,可以将下面的算法形象地称为“捡豆子”:
首先将第一颗豆子放入口袋中。
从第二颗豆子开始检查,直到最后一颗豆子。如果正在检查的豆子比口袋中的还大,则将它捡起放入口袋中,同时丢掉原先口袋中的豆子。
最后口袋中的豆子就是所有的豆子中最大的一颗。
下面是一个形式算法,用近似于编程语言的伪代码表示
给定:一个数列“list",以及数列的长度"length(list)"
largest = list
for counter = 2 to length(list):
if list[counter] > largest:
largest = list[counter]
print largest
符号说明:
= 用于表示赋值。即:右边的值被赋予给左边的变量。
list[counter]用于表示数列中的第counter项。例如:如果counter的值是5,那么list[counter]表示数列中的第5项。
<= 用于表示“小于或等于”。
例子二
求两个自然数的最大公约数 设两个变量 m 和 n
如果 m < n,则交换 m 和 n
m 被 n 除,得到余数 r
判断 r=0,正确则 n 即为“最大公约数”,否则下一步
将 n 赋值给 m,将 r 赋值给 n,重做第一步。
用“basic 代码”表示--
if m < n then swap m,n
do while r <> 0
r = m mod n
m = n
n = r
loop
print n
算法设计和分析的基本方法
分治法
动态规划
贪心法(亦作饕餮法)
算法的三种基本结构的定义
顺序结构:顺序结构是最简单、最常用的算法结构,语句与语句之间,框与框之间按从上到下的顺序进行。
选择结构:是先根据条件作出判断,再决定执行哪一种操作的算法结构,它必须包含判断框。当条件p成立(或称为真)时执行a,否则执行b,不可能两者同时执行,但a或b两个框中可以有一个是空的,即不执行任何操作.
循环结构:在一些算法中,经常会出现从某处开始,按照一定条件,反复执行某一处理步骤的情况,这就是循环结构,反复执行的处理步骤为循环体,它可以细分为两类:直到型循环结构、当型循环结构.
算法的分类
基本算法
枚举
搜索
深度优先搜索
广度优先搜索
启发式搜索
遗传算法
数据结构的算法
数论与代数算法
计算几何的算法
凸包算法
图论的算法
哈夫曼编码
树的遍历
最短路径算法
最小生成树算法
最小树形图
网络流算法
匹配算法
动态规划
其他
数值分析
加密算法
排序算法
检索算法
随机化算法
关于并行算法,请参阅并行计算一文。
参见
计算机科学课程列表 算法 algorithm
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法,后者是操作实现的算法。
一个算法应该具有以下五个重要的特征:
1、有穷性: 一个算法必须保证执行有限步之后结束;
2、确切性: 算法的每一步骤必须有确切的定义;
3、输入:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定除了初始条件;
4、输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;
5、可行性: 算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。
算法的设计要求
1)正确性(correctness)
有4个层次:
A.程序不含语法错误;
B.程序对几组输入数据能够得出满足规格要求的结果;
C.程序对精心选择的、典型的、苛刻的、带有刁难性的几组输入数据能够得出满足规格要求的结果;
D.程序对一切合法的输入数据都能产生满足规格要求的结果。
2)可读性(readability)
算法的第一目的是为了阅读和交流;
可读性有助于对算法的理解;
可读性有助于对算法的调试和修改。
3)高效率与低存储量
处理速度快;存储容量小
时间和空间是矛盾的、实际问题的求解往往是求得时间和空间的统一、折中。
算法的描述 算法的描述方式(常用的)
算法描述自然语言
流程图特定的表示算法的图形符号
伪语言包括程序设计语言的三大基本结构及自然语言的一种语言
类语言类似高级语言的语言,例如,类pascal、类c语言。
算法的评价算法评价的标准:时间复杂度和空间复杂度。
1)时间复杂度指在计算机上运行该算法所花费的时间。用“o(数量级)”来表示,称为“阶”。
常见的时间复杂度有: o(1)常数阶;o(logn)对数阶;o(n)线性阶;o(n^2)平方阶
2)空间复杂度指算法在计算机上运行所占用的存储空间。度量同时间复杂度。
时间复杂度举例
(a) x:=x+1 ;o(1)
(b) for i:=1 to n do
x:= x+1;o(n)
(c) for i:= 1 to n do
for j:= 1 to n do
x:= x+1; o(n^2)
“算法”一词最早来自公元 9世纪 波斯数学家比阿勒·霍瓦里松的一本影响深远的著作《代数对话录》。20世纪的 英国 数学家 图灵 提出了著名的图灵论点,并抽象出了一台机器,这台机器被我们称之为 图灵机 。图灵的思想对算法的发展起到了重要的作用。
算法是 计算机 处理信息的本质,因为 计算机程序 本质上是一个算法,告诉计算机确切的步骤来执行一个指定的任务,如计算职工的薪水或打印学生的成绩单。 一般地,当算法在处理信息时,数据会从输入设备读取,写入输出设备,可能保存起来以供以后使用。
这是算法的一个简单的例子。
我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小 可以将下面的算法形象地称为“捡豆子”:
首先将第一颗豆子(数列中的第一个数字)放入口袋中。
从第二颗豆子开始检查,直到最后一颗豆子。如果正在检查的豆子比口袋中的还大,则将它捡起放入口袋中,同时丢掉原先的豆子。 最后口袋中的豆子就是所有的豆子中最大的一颗。
下面是一个形式算法,用近似于 编程语言 的 伪代码 表示
给定:一个数列“list",以及数列的长度"length(list)" largest = list for counter = 2 to length(list): if list[counter] > largest: largest = list[counter] print largest
符号说明:
= 用于表示赋值。即:右边的值被赋予给左边的变量。
list[counter] 用于表示数列中的第 counter 项。例如:如果 counter 的值是5,那么 list[counter] 表示数列中的第5项。
<= 用于表示“小于或等于”。
算法的分类
(一)基本算法 :
1.枚举
2.搜索:
深度优先搜索
广度优先搜索
启发式搜索
遗传算法
(二)数据结构的算法
(三)数论与代数算法
(四)计算几何的算法:求凸包
(五)图论 算法:
1.哈夫曼编码
2.树的遍历
3.最短路径 算法
4.最小生成树 算法
5.最小树形图
6.网络流 算法
7.匹配算法
(六)动态规划
(七)其他:
1.数值分析
2.加密算法
3.排序 算法
4.检索算法
5.随机化算法 |
|
算法(Algorithm)是一系列解决问题的清晰指令,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列,并且这样的步骤和序列可以解决一类问题。
一个算法应该具有以下五个重要的特征:
1、有穷性: 一个算法必须保证执行有限步之后结束;
2、确切性: 算法的每一步骤必须有确切的定义;
3、输入:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定除了初始条件;
4、输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;
5、可行性: 算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。
计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》,可见算法在计算机科学界与计算机应用界的地位。 |
|
同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
时间复杂度
算法的时间复杂度是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模n 的函数f(n),算法的时间复杂度也因此记做
T(n)=Ο(f(n))
因此,问题的规模n 越大,算法执行的时间的增长率与f(n) 的增长率正相关,称作渐进时间复杂度(Asymptotic Time Complexity)。
空间复杂度
算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。
详见百度百科词条"算法复杂度" |
|
1.递推法
递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步,找出相邻几步的关系,从而达到目的,此方法称为递推法。
2.递归
递归指的是一个过程:函数不断引用自身,直到引用的对象已知
3.穷举搜索法
穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。
4.贪婪法
贪婪法是一种不追求最优解,只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯。
5.分治法
把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
6.动态规划法
动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础,被广泛应用于计算机科学和工程领域。
7.迭代法
迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题(一般是解方程或者方程组)的过程,为实现这一过程所使用的方法统称为迭代法。 |
|
算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法。
算法可以宏泛的分为三类:
有限的,确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务,但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。
有限的,非确定算法 这类算法在有限的时间内终止。然而,对于一个(或一些)给定的数值,算法的结果并不是唯一的或确定的。
无限的算法 是那些由于没有定义终止定义条件,或定义的条件无法由输入的数据满足而不终止运行的算法。通常,无限算法的产生是由于未能确定的定义终止条件。 |
|
经典的算法有很多,如:"欧几里德算法,割圆术,秦九韶算法"。 |
|
目前市面上有许多论述算法的书籍,其中最著名的便是《计算机程序设计艺术》(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世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要作用的。 |
|
suanfa
算法
algorithm
求解问题类的、机械的、统一的方法,它由有限多个步骤组成,对于问题类中的每个给定的具体问题,机械地执行这些步骤就可以得到问题的解答。算法的这种特性,使得计算不仅可以由人,而且可以由计算机来完成。用计算机解决问题的过程可以分成三个阶段:分析问题、设计算法和实现算法。
中国古代的筹算口决与珠算口决及其执行规则就是算法的雏形,这里,所解决的问题类是算术运算。古希腊数学家欧几里得在公元前3世纪就提出了一个算法,来寻求两个正整数的最大公约数,这就是有名的欧几里得算法,亦称辗转相除法。中国早已有“算术”、“算法”等词汇,但是它们的含义是指当时的全部数学知识和计算技能,与现代算法的含义不尽相同。英文algorithm(算法)一词也经历了一个演变过程,最初的拼法为algorism或algoritmi,原意为用阿拉伯数字进行计算的过程。这个词源于公元 9世纪波斯数字家阿尔·花拉子米的名字的最后一部分。
在古代,计算通常是指数值计算。现代计算已经远远地突破了数值计算的范围,包括大量的非数值计算,例如检索、表格处理、判断、决策、形式逻辑演绎等。
在20世纪以前,人们普遍地认为,所有的问题类都是有算法的。20世纪初,数字家们发现有的问题类是不存在算法的,遂开始进行能行性研究。在这一研究中,现代算法的概念逐步明确起来。30年代,数字家们提出了递归函数、图灵机等计算模型,并提出了丘奇-图灵论题(见可计算性理论),这才有可能把算法概念形式化。按照丘奇-图灵论题,任意一个算法都可以用一个图灵机来实现,反之,任意一个图灵机都表示一个算法。
按照上述理解,算法是由有限多个步骤组成的,它有下述两个基本特征:每个步骤都明确地规定要执行何种操作;每个步骤都可以被人或机器在有限的时间内完成。人们对于算法还有另一种不同的理解,它要求算法除了上述两个基本特征外,还要具有第三个基本特征:虽然有些步骤可能被反复执行多次,但是在执行有限多次之后,就一定能够得到问题的解答。也就是说,一个处处停机(即对任意输入都停机)的图灵机才表示一个算法,而每个算法都可以被一个处处停机的图灵机来实现。
(唐守文)
|
|
- n.: algorithm, arithmetic, basis, set of rules or procedures that must be followed in solving a problem
|
|
公式 计算程序 |
|
加权图 | 最短路径 | Floyd | 计算机 | 网络 | 加密 | IT | 物理 | 编程 | 学科 | 单源最短路径 | 百科大全 | 电子商务 | 网络安全 | 安全邮件 | 加密软件 | Rsa公匙 | 游戏 | 傅立叶 | 频谱 | 数学变换 | 技术 | 互联网 | 更多结果... |
|
|
|
|
五经算术 | 九章算术 | 孙子算经 | 海岛算经 | 缉古算经 | 周髀算经 | 九章算经 | |
|