万维百科

算法

应对灯泡不亮的简单算法流程图

算法algorithm),在数学算学)和计算机科学之中,一个被定义好的、计算机可施行之指示的有限步骤或次序,常用于计算数据处理英语Data processing自动推理。作为一个有效方法英语Effective method,算法被用于计算函数,它包含了一系列定义清晰的指令,并可于有限的时间及空间内清楚的表述出来。

算法中的指令描述的是一个计算,当其运行英语Execution (computing)时能从一个初始状态和初始输入(可能为)开始,经过一系列有限而清晰定义的状态最终产生输出停止于一个终态。一个状态到另一个状态的转移不一定是确定的。包括随机化算法在内的一些算法,都包含了一些随机输入。

早在尝试解决希尔伯特提出的判定问题时,关于算法的一个不完全的概念已经初步定型,并在其后的正式化阶段中尝试定义“有效可计算性英语Effective calculability”或者“有效方法英语Effective method”。这些尝试包括库尔特·哥德尔雅克·埃尔布朗斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数阿隆佐·邱奇于1936年提出的λ演算,1936年埃米尔·莱昂·珀斯特英语Emil Leon PostFormulation 1艾伦·图灵1937年提出的图灵机。即使在当下,依然常有符合直觉的想法难以定义为形式化算法的情况。

历史

算法在中国古代文献中称为“术”,最早出现在《周髀算经》、《九章算术》。特别是《九章算术》,给出四则运算最大公约数、最小公倍数、开平方根、开立方根、求素数埃拉托斯特尼筛法,线性方程组求解的算法。三国时代的刘徽给出求圆周率的算法:刘徽割圆术

自唐代以来,历代更有许多专门论述“算法”的专著:

  • 唐代:《一位算法》 一卷,《算法》 一卷;
  • 宋代:《算法绪论》 一卷、《算法秘诀》 一卷;最著名的是杨辉的《杨辉算法》;
  • 元代:《丁巨算法》;
  • 明代:程大位算法统宗
  • 清代:《开平算法》、《算法一得》、《算法全书》。

而英文名称“algorithm”来自于9世纪波斯数学家花拉子米(比阿勒·霍瓦里松,波斯语:خوارزمی ‎,拉丁转写:al-Khwarizmi),因为比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为“algorism”,即“al-Khwarizmi”的音转,意思是“花拉子米”的运算法则,在18世纪演变为“algorithm”。

欧几里得算法被人们认为是史上第一个算法。

第一次编写程序是爱达·勒芙蕾丝Ada Byron)于1842年为巴贝奇分析机编写求解解伯努利微分方程程序,因此爱达·勒芙蕾丝被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇Charles Babbage)未能完成他的巴贝奇分析机,这个算法未能在巴贝奇分析机上执行。

因为“well-defined procedure”缺少数学上精确的定义,19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要的作用。

特征

以下是高德纳在他的著作《计算机程序设计艺术》里对算法的特征归纳:

MerkleTree1.JPG
  1. 输入:一个算法必须有零个或以上输入量。
  2. 输出:一个算法应有一个或以上输出量,输出量是算法计算的结果。
  3. 明确性:算法的描述必须无歧义,以保证算法的实际执行结果是精确地符合要求或期望,通常要求实际运行结果是确定的。
  4. 有限性:依据图灵的定义,一个算法是能够被任何图灵完备系统模拟的一串运算,而图灵机只有有限个状态、有限个输入符号和有限个转移函数(指令)。而一些定义更规定算法必须在有限个步骤内完成任务。
  5. 有效性:又称可行性。能够实现,算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

基本要素

算法的核心是创建问题抽象的模型和明确求解目标,之后可以根据具体的问题选择不同的模式和方法完成算法的设计。

常用设计模式

完全遍历法和不完全遍历法:在问题的解是有限离散解空间,且可以验证正确性和最优性时,最简单的算法就是把解空间的所有元素完全遍历一遍,逐个检测元素是否是我们要的解。这是最直接的算法,实现往往最简单。但是当解空间特别庞大时,这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。

分治法:把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。

动态规划法:当问题的整体最优解就是由局部最优解组成的时候,经常采用的一种方法。

贪心算法:常见的近似求解思路。当问题的整体最优解不是(或无法证明是)由局部最优解组成,且对解的最优性没有要求的时候,可以采用的一种方法。

线性规划法:见条目。

简并法:把一个问题通过逻辑或数学推理,简化成与之等价或者近似的、相对简单的模型,进而求解的方法。

常用实现方法

递归方法迭代方法

顺序计算、并行计算分布式计算:顺序计算就是把形式化算法用编程语言进行单线程序列化后执行。

确定性算法和非确定性算法

精确求解和近似求解

形式化算法

算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务,如计算职工的薪水或打印学生的成绩单。一般地,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。

复杂度

时间复杂度

算法的时间复杂度是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模的函数,算法的时间复杂度也因此记做

算法执行时间的增长率与的增长率正相关,称作渐近时间复杂度英语Asymptotic computational complexity,简称时间复杂度。

常见的时间复杂度有:常数阶,对数阶,线性阶,线性对数阶,平方阶,立方阶,...,次方阶,指数阶。随着问题规模的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。

非确定性多项式时间(NP)

实现

算法不单单可以用计算机程序来实现,也可以在人工神经网络电路或者机械设备上实现。

示例

求最大值算法

这是算法的一个简单的例子。

我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小,可以将下面的算法形象地称为“捡豆子”:

  1. 首先将第一颗豆子放入口袋中。
  2. 从第二颗豆子开始检查,如果正在检查的豆子比口袋中的还大,则将它捡起放入口袋中,同时丢掉原先口袋中的豆子。反之则继续下一颗豆子。直到最后一颗豆子。
  3. 最后口袋中的豆子就是所有的豆子中最大的一颗。

以上算法在中国大陆的教科书中通常被叫做“打擂法”或者“循环打擂”:在一个for循环中,每轮循环都有新的挑战者。若挑战者胜的话,挑战者做新擂主,否则擂主卫冕。for循环结束后输出最后的擂主。

下面是一个形式算法,用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;
}

求最大公约数算法

求两个自然数的最大公约数 设两个变量

  1. 如果,则交换
  2. 除以,得到余数
  3. 判断,正确则即为“最大公约数”,否则下一步
  4. 赋值给,将赋值给,重做第一步。

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;
}

分类

注释

  1. ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein; 殷建平等译. 第1章 算法在计算机中的作用. 算法导论 原书第3版. 北京: 机械工业出版社. 2013年1月: 3[5] [2017-11-14]. ISBN 978-7-111-40701-0 (中文).
  2. ^ "an algorithm is a procedure for computing a function(with respect to some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality",(Rogers 1987:1)
  3. ^ Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations"(Rogers 1987:2).
  4. ^ "Any classical mathematical algorithm, for example, can be described in a finite number of English words"(Rogers 1987:2).
  5. ^ "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins"(Knuth 1973:5)
  6. ^ "A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'"(Knuth 1973:5)
  7. ^ "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs"(Knuth 1973:5)
  8. ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices... carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2).
  9. ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices ... carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2).
  10. ^ Kleene(斯蒂芬·科尔·克莱尼)1943 in Davis 1965:274
  11. ^ Rosser(巴克利·罗瑟)1939 in Davis 1965:225
  12. ^ Moschovakis, Yiannis N. What is an algorithm?. Engquist, B.; Schmid, W. (编). Mathematics Unlimited—2001 and beyond. Springer. 2001: 919–936 (Part II).
  13. ^ Ada Lovelace honoured by Google doodle. The Guardian. 10 December 2012 [10 December 2012]. (原始内容存档于2018-12-25).
  14. ^ 2.4 赛场统分. 读书频道-IT技术图书-51CTO.COM. [2017-06-07]. (原始内容存档于2017-03-24).
  15. ^ 实验3-9:循环打擂. 湖南科技大学程序设计在线评测(Online Judge).[永久失效链接]
  16. ^ 高中,算法与程序设计,教案. 在点网.[永久失效链接]

参见

延伸阅读

维基文库中的相关文本:钦定古今图书集成·历象汇编·历法典·算法部》,出自蒋廷锡古今图书集成

外部链接


本页面最后更新于2021-08-30 08:13,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器