首页 >
算法
✍ dations ◷ 2025-06-28 09:46:27 #算法
算法(algorithm),在数学(算学)和计算机科学之中,为任何一系列良定义的具体计算步骤,常用于计算、数据处理(英语:Data processing)和自动推理。作为一个有效方法(英语:Effective method),算法被用于计算函数,它包含了一系列定义清晰的指令,并可于有限的时间及空间内清楚的表述出来。算法中的指令描述的是一个计算,当其运行(英语:Execution (computing))时能从一个初始状态和初始输入(可能为空)开始,经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。包括随机化算法在内的一些算法,都包含了一些随机输入。早在尝试解决希尔伯特提出的判定问题时,关于算法的一个不完全的概念已经初步定型,并在其后的正式化阶段中尝试定义“有效可计算性(英语:Effective calculability)”或者“有效方法(英语:Effective method)”。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数,阿隆佐·邱奇于1936年提出的λ演算,1936年埃米尔·莱昂·珀斯特(英语:Emil Leon Post)的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当下,依然常有符合直觉的想法难以定义为形式化算法的情况。算法在中国古代文献中称为“术”,最早出现在《周髀算经》、《九章算术》。特别是《九章算术》,给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法,线性方程组求解的算法。三国时代的刘徽给出求圆周率的算法:刘徽割圆术。自唐代以来,历代更有许多专门论述“算法”的专著:而英文名称“algorithm”来自于9世纪波斯数学家花拉子米(比阿勒·霍瓦里松,波斯语:خوارزمی ,拉丁转写:al-Khwarizmi),因为比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为“algorism”,即“al-Khwarizmi”的音转,意思是“花拉子米”的运算法则,在18世纪演变为“algorithm”。欧几里得算法被人们认为是史上第一个算法。第一次编写程序是爱达·勒芙蕾丝(Ada Byron)于1842年为巴贝奇分析机编写求解解伯努利微分方程的程序,因此爱达·勒芙蕾丝被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机,这个算法未能在巴贝奇分析机上执行。因为“well-defined procedure”缺少数学上精确的定义,19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要的作用。以下是高德纳在他的著作《计算机程序设计艺术》里对算法的特征归纳:算法的核心是创建问题抽象的模型和明确求解目标,之后可以根据具体的问题选择不同的模式和方法完成算法的设计。完全遍历法和不完全遍历法:在问题的解是有限离散解空间,且可以验证正确性和最优性时,最简单的算法就是把解空间的所有元素完全遍历一遍,逐个检测元素是否是我们要的解。这是最直接的算法,实现往往最简单。但是当解空间特别庞大时,这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。分治法:把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。动态规划法:当问题的整体最优解就是由局部最优解组成的时候,经常采用的一种方法。贪心算法:常见的近似求解思路。当问题的整体最优解不是(或无法证明是)由局部最优解组成,且对解的最优性没有要求的时候,可以采用的一种方法。线性规划法:见条目。简并法:把一个问题通过逻辑或数学推理,简化成与之等价或者近似的、相对简单的模型,进而求解的方法。递归方法与迭代方法顺序计算、并行计算和分布式计算:顺序计算就是把形式化算法用编程语言进行单线程序列化后执行。确定性算法和非确定性算法精确求解和近似求解算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务,如计算职工的薪水或打印学生的成绩单。一般地,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。算法的时间复杂度是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模
n
{displaystyle n}
的函数
f
(
n
)
{displaystyle f(n)}
,算法的时间复杂度也因此记做算法执行时间的增长率与
f
(
n
)
{displaystyle f(n)}
的增长率正相关,称作渐近时间复杂度(英语:Asymptotic computational complexity),简称时间复杂度。常见的时间复杂度有:常数阶
O
(
1
)
{displaystyle O(1)}
,对数阶
O
(
log
n
)
{displaystyle O(log n)}
,线性阶
O
(
n
)
{displaystyle O(n)}
,线性对数阶
O
(
n
log
n
)
{displaystyle O(nlog n)}
,平方阶
O
(
n
2
)
{displaystyle O(n^{2})}
,立方阶
O
(
n
3
)
{displaystyle O(n^{3})}
,...,
k
{displaystyle k}
次方阶
O
(
n
k
)
{displaystyle O(n^{k})}
,指数阶
O
(
2
n
)
{displaystyle O(2^{n})}
。随着问题规模
n
{displaystyle n}
的不断增大,上述时间复杂度不断增大,算法的执行效率越低。算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。算法不单单可以用计算机程序来实现,也可以在人工神经网络、电路或者机械设备上实现。这是算法的一个简单的例子。我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小,可以将下面的算法形象地称为“捡豆子”:以上算法在中国大陆的教科书中通常被叫做“打擂法”或者“循环打擂”:在一个for循环中,每轮循环都有新的挑战者。若挑战者胜的话,挑战者做新擂主,否则擂主卫冕。for循环结束后输出最后的擂主。下面是一个形式算法,用ANSI C代码表示求两个自然数的最大公约数
设两个变量
M
{displaystyle M}
和
N
{displaystyle N}用ANSI C代码表示利用if函数以及递归则能做出更为精简的代码,更可省去交换的麻烦。(但是也因为递归调用,其空间复杂度提高)
相关
- 叶绿体叶绿体(英语:chloroplast)是绿色植物和藻类等真核自养生物细胞中专业化亚单元的细胞器。其主要作用是进行光合作用,其中含有的光合色素叶绿素从太阳光捕获能量,并将其存储在能量
- MCV平均红细胞体积(mean corpuscular volume、mean cell volume,简称MCV)是指人体单个红细胞的平均体积,通常是间接计算得到。平均红细胞体积 =
- 粮食安全粮食安全指的是能够稳定地让所有人取得足够食物的状态。联合国政府间气候变化专业委员会曾于2014年3月31日在日本横滨召开会议时发表了一份报告,报告中指出:“气候变迁正冲击
- 生物性危害第四级生物性危害(英文:Biological hazard, Biohazard),又称为“生物危害”,指的是会对人类及动物有危害的生物或生物性物质。这些物质包括但不限于动物、植物、微生物、病毒及含有病原
- 库欣综合征库兴氏综合征(法语:Le syndrome de Cushing; 英语:Cushing's syndrome)亦称库欣氏综合征、柯兴氏综合征、皮质醇增多症,其中包括库欣氏病(Cushing's disease,专指由原发性脑下腺瘤
- At4f14 5d10 6s2 6p52, 8, 18, 32, 18, 7蒸气压主条目:砹的同位素砹(Astatine,台湾译作砈,旧讹作“鈪”、“銰”)是一种具有极高放射性的化学元素,符号为At,原子序为85。地球上所有的
- 呼气流量峰值峰值呼气流量(英文:peak expiratory flow,PEF),也称峰值呼气流量测定(英文:peak expiratory flow rate, PEFR)是一个人的最大呼气速度,用峰值流量计测量,一个用于监测一个人呼吸空气能
- 新台币新台币,是中华民国现行的法定货币,于1949年6月15日起发行流通,当时定位为限定台湾使用的区域货币,目前则在整个中华民国有效统治区域(台澎金马)均可流通使用。原始发行机构为台湾
- 狭br /带br /纪狭带纪(Stenian,符号MP3)是地质时代中的一个纪,开始于同位素年龄1200±0百万年(Ma),结束于1000±0Ma。狭带纪期间的叠层岩达到高峰,真核藻类继续发展。狭带纪属于前寒武纪元古宙中
- 西澳大利亚州西澳大利亚州(英语:Western Australia,缩写:WA),简称西澳,是澳大利亚联邦的一个州,位于澳大利亚西部,今划分为142个地方政府区域,幅员广达2,525,500平方公里,占全国总面积1/3,是面积最广