算法(英語:algorithm),在数学(算学)和计算机科学之中,指一个被定义好的、计算机可施行其指示的有限步骤或次序,常用于计算、数据处理和自动推理。算法可以使用条件语句通过各种途径转移代码执行(称为自动决策),并推导出有效的推论(称为自动推理),最终实现自动化。
此條目需要編修,以確保文法、用詞、语气、格式、標點等使用恰当。 |
相反,启发式是一种解决问题的方法,可能没有完全指定,也可能不能保证正确或最优的结果,尤其是在没有明确定义的正确或最优结果的问题领域。例如,社交媒体推荐系统依赖于启发式,尽管在21世纪的流行媒体中被广泛称为算法,但由于问题的性质,它无法提供正确的结果。
早在尝试解决希尔伯特提出的判定问题时,算法的不完整概念已经初步定型;在其后的正式化阶段中人們尝试去定义“有效可计算性”或者“有效方法”。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数,阿隆佐·邱奇于1936年提出的λ演算,1936年埃米尔·莱昂·珀斯特的波斯特-图灵机和艾伦·图灵1937年提出的图灵机。即使在当下,依然常有符合直觉的想法难以定义为形式化算法的情况。
算法是有效方法,包含一系列定义清晰的指令,并可于有限的时间及空间内清楚的表述出来。算法中的指令描述的是一个计算,它执行時从一个初始状态和初始输入(可能为空)开始,经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。 一个状态到另一个状态的转移不一定是确定的。 包括随机化算法在内的一些算法,都包含了一些随机输入。
算法在中国古代文献中称为“术”,最早出现在《周髀算經》、《九章算术》。特别是《九章算术》,给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃氏篩,线性方程组求解的高斯消元法。三国時代的刘徽给出求圆周率的算法:刘徽割圆术。
自唐代以来,历代更有许多专门论述“算法”的专著:
而英文名稱「algorithm」来自于9世纪波斯数学家花拉子米(比阿勒·霍瓦里松,波斯語:خوارزمی ,拉丁轉寫:al-Khwarizmi),因為比阿勒·霍瓦里松在数学上提出了算法这个概念。「算法」原为「algorism」,即“al-Khwarizmi”的音转,意思是“花剌子模的”运算法则,在18世纪演变为「algorithm」。
欧几里得算法被人们认为是史上第一个算法。
第一次编写程序是愛達·勒芙蕾絲(Ada Byron)于1842年为巴贝奇分析机编写求解解伯努利微分方程的程序,因此愛達·勒芙蕾絲被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机,这个算法未能在巴贝奇分析机上执行。 因为「well-defined procedure」缺少数学上精确的定义,19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的电脑的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要的作用。
算法的核心是建立问题抽象的模型和明确求解目标,之后可以根据具体的问题选择不同的模式和方法完成算法的设计。
完全遍历法和不完全遍历法:在问题的解是有限离散解空间,且可以验证正确性和最优性时,最简单的算法就是把解空间的所有元素完全遍历一遍,逐个检测元素是否是我们要的解。这是最直接的算法,实现往往最简单。但是当解空间特别庞大时,这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。 分治法:把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。 动态规划法:当问题的整体最优解就是由局部最优解组成的时候,经常采用的一种方法。贪婪算法:常见的近似求解思路。当问题的整体最优解不是(或无法证明是)由局部最优解组成,且对解的最优性没有要求的时候,可以采用的一种方法。 线性规划法:见条目。 简并法:把一个问题通过逻辑或数学推理,简化成与之等价或者近似的、相对简单的模型,进而求解的方法。
递归方法与迭代方法 顺序计算、并行计算和分布式运算:顺序计算就是把形式化算法用程序设计语言进行单线程序列化后执行。 确定性算法和非确定性算法 精确求解和近似求解
算法是电脑处理信息的本质,因为计算机程序本质上是一个算法来告诉电脑确切的步骤来执行一个指定的任务,如计算职工的薪水或打印学生的成绩单。一般地,当算法在处理信息时,会从输入装置或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。
算法的时间复杂度是指算法需要消耗的时间资源。一般来说,电脑算法是问题规模 的函数解析失败 (语法错误): {\displaystyle f(n)} ,算法的时间复杂度也因此记做 :解析失败 (语法错误): {\displaystyle T(n)= \mathcal{O}(f(n))} 算法执行时间的增长率与解析失败 (语法错误): {\displaystyle f(n)} 的增长率正相关,称作渐近时间复杂度,简称时间复杂度。 常见的时间复杂度有:常数阶解析失败 (语法错误): {\displaystyle O(1)} ,对数阶解析失败 (语法错误): {\displaystyle O(\log n)} ,线性阶解析失败 (语法错误): {\displaystyle O(n)} ,线性对数阶解析失败 (语法错误): {\displaystyle O(n\log n)} ,平方阶解析失败 (语法错误): {\displaystyle O(n^2)} ,立方阶解析失败 (SVG(MathML可通过浏览器插件启用):从服务器“http://localhost:6011/zh.wikipedia.org/v1/”返回无效的响应(“Math extension cannot connect to Restbase.”):): {\displaystyle O(n^3)} ,…,< math> k 次方阶解析失败 (语法错误): {\displaystyle O(n^k)} ,指数阶解析失败 (语法错误): {\displaystyle O(2^n)} 。随着问题规模 的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。
这是算法的一个简单的例子。 我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数位看成是一颗豆子的大小,可以将下面的算法形象地称为「捡豆子」:
下面是一个形式算法,用ANSI C代码表示
int max(int *array, int size) { int mval = *array; int i; for (i = 1; i < size; i++) if (array[i] > mval) mval = array[i]; return mval; }
求两个自然数的最大公约数 设两个变量 和
用ANSI C代码表示
//交換2數 void swapi(int *x, int *y) { int tmp = *x; *x = *y; *y = tmp; } int gcd(int m, int n) { int r; do { if (m < n) swapi(&m, &n); r = m % n; m = n; n = r; } while (r); return m; }
利用if函式以及遞迴則能做出更為精簡的程式碼,更可省去交換的麻煩。(但是也因為遞迴呼叫,其空間複雜度提高)
int gcd(int a,int b) { if(a%b) return gcd(b,a%b); return b; }
分类算法有多种方法,每种方法都有自己的优点。
分类算法的一种方法是通过实现手段。
int gcd(int A, int B) { if (B == 0) return A; else if (A > B) return gcd(A-B,B); else return gcd(A,B-A); } |
从上面的流程图递归 C 实现欧几里得算法 |
对算法进行分类的另一种方法是通过它们的设计方法或范例。有一定数量的范例,每一个不同于其他。此外,这些类别中的每一个都包括许多不同类型的算法。一些常见的范例是:
对于最优化问题,有一个更具体的算法分类; 这类问题的算法可能属于上述一个或多个一般类别,也可能属于以下类别之一:
此章節尚無參考來源,內容或許無法查證。 (2023年6月1日) |
每个科学领域都有自己的问题,需要高效的算法。一个领域中的相关问题经常被一起研究。一些示例类是搜索算法、排序算法、合并算法、数值算法、图形算法、字符串算法、计算几何算法、组合算法、医学算法、机器学习、密码学、数据压缩算法和解析技术。
字段之间往往相互重叠,一个字段的算法进步可能会改进其他字段的算法,有时候这些字段完全不相关。例如,动态规划是为了优化工业中的资源消耗而发明的,但是现在被用于解决许多领域中的广泛问题。
此章節尚無參考來源,內容或許無法查證。 (2023年6月1日) |
算法可以根据它们需要完成的时间和它们的输入大小进行分类:
一些问题可能有多个不同复杂度的算法,而另一些问题可能没有算法或者没有已知的有效算法。还有从一些问题到其他问题的映射。由于这个原因,我们发现根据问题的最佳可能算法的复杂性,将问题本身分类比将算法分为等价类更为合适。
形容词“连续”用于“算法”一词时,可以表示:
查看维基词典中的词条「算法」。 |
This article uses material from the Wikipedia 中文 article 算法, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). 除非另有声明,本网站内容采用CC BY-SA 4.0授权。 Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki 中文 (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.