计算机科学中,算法效率是算法的一种属性,算法效率与算法使用的计算资源量的大小有关。分析算法以确定其资源使用情况,即可根据不同资源的使用情况来衡量算法的效率。算法效率可以被认为类似于某个重复或持续过程的生产力大小。 为获得最大效率,一般希望能够尽量减少资源使用量。然而,时间复杂度和空间复杂度等不同的...
24 KB (3,314 words) - 04:54, 4 December 2022
该算法综合了最良優先搜索(英语:Best-first search)和Dijkstra算法的优点:在进行启发式搜索提高算法效率的同时,可以保证找到一条最优路径(需要评估函数满足单调性)。 在此算法中,如果以 g ( n ) {\displaystyle g(n)} 表示从起点到任意顶点 n {\displaystyle...
5 KB (709 words) - 11:55, 2 August 2023
在计算机科学中,算法分析(英語:Analysis of algorithm)是分析执行一个给定算法需要消耗的计算资源数量(例如计算时间,存储器使用等)的过程。算法的效率或复杂度在理论上表示为一个函数。其定义域是输入数据的长度(通常考虑任意大的输入,没有上界),值域通常是执行步骤数量(时间复杂度)或者...
14 KB (2,600 words) - 16:40, 25 December 2023
算法效率。 当一个字典串集合是已知的(例如一个计算机病毒库), 就可以以离线方式先将自动机求出并储存以供日后使用,在这种情况下,算法的时间复杂度为输入字符串长度和匹配数量之和。 UNIX系统中的一个命令fgrep就是以AC自动机算法作为基础实现的。 设一个字典中有如下单词:{a...
7 KB (825 words) - 17:01, 9 January 2024
然而SPFA在最坏情况的时间复杂度与 Bellman-Ford 算法相同,因此在非负边权的图中使用堆优化的Dijkstra 算法效率可能优于SPFA。 SPFA算法首先在1959年由Edward F. Moore(英语:Edward F. Moore)作为广度优先搜索的扩展发表,相同算法在1994年由段凡丁重新发现。 给定一个有向带权图...
7 KB (1,061 words) - 21:42, 17 August 2022
遗传算法(英語:Genetic Algorithm,GA)是计算数学中用于解决最佳化的搜索算法,是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择以及杂交等等。 遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题,一定数量的候选解(称为...
15 KB (2,482 words) - 08:50, 27 February 2022
cells的问题。 这个问题在计算上是NP困难的,不过存在高效的启发式算法。一般情况下,都使用效率比较高的启发式算法,它们能够快速收敛于一个局部最优解。这些算法通常类似于通过迭代优化方法处理高斯混合分布的最大期望算法(EM算法)。而且,它们都使用聚类中心来为数据建模;然而k-平均聚类倾向于在可比较...
26 KB (3,628 words) - 00:18, 20 February 2023
分治法這個名稱有時亦會用於將問題簡化為只有一個細問題的算法,例如用於在已排序的列中尋找其中一項的折半搜索算法(或是在數值分析中類似的勘根算法)。這些算法比一般的分治算法更能有效地執行。其中,假如算法使用尾部遞歸的話,便能轉換成簡單的迴圈。但在這廣義之下,所有使用遞歸或迴圈的算法均被視作「分治算法...
6 KB (976 words) - 10:18, 8 January 2022
启发式搜索 遗传算法 数据结构的算法 数论与代数算法 计算几何的算法 凸包算法 图论的算法 哈夫曼编码 树的遍历 最短路径算法 最小生成树算法 最小树形图 网络流算法 匹配算法 分團問題 动态规划 其他 数值分析 加密算法 排序算法 检索算法 随机化算法 关于并行算法,请参阅并行计算一文。 Thomas H...
32 KB (4,773 words) - 07:35, 5 May 2024
在计算机科学中,克努斯-莫里斯-普拉特字符串查找算法(英語:Knuth–Morris–Pratt algorithm,简称为KMP算法)可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置,此算法利用这一特性以避免重新检查先前配對的字符。 这个算法...
13 KB (1,559 words) - 03:27, 5 March 2024
鸽巢排序 (category 排序算法)
O(n)} (大O符號)且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法。但它只有在差值(或者可被映射在差值)很小的范围内的数值排序的情况下实用。 当涉及到多个不相等的元素,且将这些元素放在同一个「鸽巢」的时候,算法的效率会有所降低。为了简便和保持鸽巢排序在适应不同的情况,比如两个在同一个存储桶中结束的元素必然相等。...
3 KB (368 words) - 11:55, 8 January 2024
便可称为“线性加速比”(英語:linear speedup,又名“理想加速比”)。当某一并行算法的加速比为理想加速比时,若将处理器数量加倍,执行速度也会加倍,即如“理想”之意,有“优秀的可扩展性”。 由加速比衍生出的效率(英語:efficiency)则是量度性能的指标,并如下定义: E p = S p p...
3 KB (486 words) - 09:40, 6 July 2018
抽象数据类型(ADT) 敌手 (算法)(adversary) 算法(algorithm) BSTW算法(algorithm BSTW) FGK算法(algorithm FGK) 算法效率(algorithmic efficiency) 算法可解(algorithmically solvable) V算法(algorithm...
6 KB (735 words) - 17:51, 9 September 2018
次松弛操作,得到所有可能的最短路径。其优于戴克斯特拉算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达 O ( | V | | E | ) {\displaystyle O(|V||E|)} 。但算法可以进行若干种优化,提高了效率。 贝尔曼-福特算法与戴克斯特拉演算法类似,都以松弛操作为基础...
7 KB (1,066 words) - 01:23, 1 February 2024
一些基本的画家算法实现方法也可能效率很低,因为这将使得系统将可见多边形集合中的每个点都进行渲染,而没有考虑这些多变性在最终场景中可能被其它部分遮挡。这也就是说,对于细致的场景来说,画家算法可能会过度地消耗计算机资源。 人们有时候也使用逆向画家算法进行处理,这种算法...
3 KB (494 words) - 09:06, 20 February 2021
在计算机科学中,X算法可用来求解精确覆盖问题。此名称最早在高德纳的论文《舞蹈链》中出现,他认为此算法是“试错法中最显而易见”的。 就技术而言,X算法是一个深度优先的不确定性回溯算法。由于X算法是一个解决精确覆盖问题的简洁方法,高德纳希望通过该算法体现舞蹈链数据结构的高效性,他把使用后者的X算法称为DLX。 X算法...
14 KB (1,280 words) - 03:26, 5 March 2024
其所需的资源已经由前序指令准备就绪。托马苏洛算法则通过动态调度的方式,在不影响结果正确性的前提下,重新排列指令实际执行的顺序(乱序执行),提高时间利用效率。IBM System/360 Model 91处理器的浮点运算器中率先使用了这种算法。:92 该算法与之前同样用于实现指令流水线动态调度的计分板...
5 KB (764 words) - 08:49, 16 April 2021
求根算法的性能是數值分析的研究範疇。一种算法的效率可能大幅度取決於已知點的性質。例如,一部分算法都使用輸入函數的導數(此要求函數不但連續,而且可導),而其他算法則能用於任何一個連續函數。在一般情况下,數值算法不能保證找到一個函數的所有根,因此算法...
9 KB (1,474 words) - 12:21, 20 December 2023
的前几位数来进一步提高效率,不过效果并不明显。二进制版的算法还可以扩展到其它进制,效率最多可以提升五倍。 对于超过25,000位数的大数,有一种改进使算法复杂度降低至平方级以下,如Schönhage、Stehlé、Zimmermann等人提出的算法。这些算法利用2×2的矩阵(见上文)。这些亚平方级的算法复杂度通常是...
92 KB (16,045 words) - 13:03, 8 March 2024
爬山算法是一种局部择优的方法,采用启發式方法,是对深度优先搜索的一种改进,它利用反馈信息帮助生成解的决策。 爬山算法一般存在以下问题: 局部最大 高地:也称为平顶,搜索一旦到达高地,就无法确定搜索最佳方向,会产生随机走动,使得搜索效率降低。 山脊:搜索可能会在山脊的两面来回震荡,前进步伐很小。 解决方法:随机重启爬山算法...
663 bytes (83 words) - 14:12, 28 November 2023
算法。在绝大多数情况下,近似算法得到的近似值位于最优解到最优解乘以某个特定的值之间,这个特定的值被称作近似比。不过,也有一些算法得到的近似值是在最优解到最优解加某个特定的值之间。 近似算法的设计及分析过程中都包含一系列的数学证明,以保证其最差情况效率仍可接受。这点也是它与模拟退火等启发式算法...
5 KB (754 words) - 10:41, 30 May 2023
斯温森-王算法(英語:Swendsen–Wang algorithm)由物理学家罗伯特·斯温森(英语:Robert Swendsen)与王建生于1987年提出,是首个非局域的蒙特卡洛算法,用以解决临界点附近效率变低的临界慢化问题。 斯温森-王算法最初用于易辛模型与玻茨模型,后来被推广到其他模型之中。该算法...
2 KB (303 words) - 06:40, 25 March 2023
而使用秦九韶算法时,至多只需作n次加法和n次乘法,最多需要x占用的字节的n倍空间。 该算法看似简单,其最大的意义在于将求n次多项式的值转化为求n个一次多项式的值。在人工计算时,利用秦九韶算法和其中的系数表可以大幅简化运算;对于计算机程序算法而言,加法比乘法的计算效率要高很多,因此该算法仍有极大的意义,用于减少中央处理器运算时间。...
11 KB (2,210 words) - 16:59, 21 August 2022
戴克斯特拉算法(英語:Dijkstra's algorithm),又稱迪杰斯特拉算法、Dijkstra算法,是由荷兰计算机科学家艾茲赫尔·戴克斯特拉在1956年发现的算法,并于3年后在期刊上发表。戴克斯特拉算法使用类似廣度优先搜索的方法解决赋权图的单源最短路径问题。 该算法...
39 KB (4,743 words) - 09:47, 19 December 2023
乘法算法是计算两个数值相乘乘積的算法。为了提高运算效率,不同大小的数字适用不同的乘法算法。自十进制数字系统诞生以来,就已开始发展乘法算法。 网格法(英语:Grid method multiplication) (或盒式法)是一种用于给小学生进行乘法计算启蒙的简单乘法算法...
34 KB (4,341 words) - 16:06, 9 January 2024
银河式算法(Galactic Algorithm)不是某一种具体算法的名称,而是一类对于极大规模数据表现特别优异的复杂算法。这类算法在常规问题中往往无法展现出优势,甚至效率低于一般的解决方案,而当数据规模足够大时,效率将提升到不可思议的程度。这里的“足够大”实际上已经脱离了现实需求,以至于这类算法...
10 KB (1,333 words) - 06:25, 23 January 2023
{\displaystyle O(n\log n\log \log n)} 。 值得一提的是,卡拉楚巴算法是第一个比小学二次乘法算法渐进快速的算法。 卡拉楚巴算法主要是用于两个大数的乘法,极大提高了运算效率,相较于普通乘法降低了复杂度,并在其中运用了递归的思想。基本的原理和做法是将位数很多的两个大数 x...
7 KB (820 words) - 14:43, 8 July 2023
在计算机科学中,渐进最优一词用以评价算法的效率。如果已经证实一个问题需要使用Ω(f(n))的资源来解决,而某个算法用O(f(n))的资源来解决这个问题,则该算法就是渐进最优的。 渐进最优的例子包括数据结构动态数组,能够在常数时间内索引,但性能在多数机器上不如普通数组的索引。另外,在所有基于比较的排序算法中,归并排序和堆排序是渐进最优的。...
3 KB (497 words) - 07:02, 17 March 2024
在模式识别领域中,最近鄰居法(KNN算法,又譯K-近邻算法)是一种用于分类和回归的無母數統計方法,由美国统计学家伊芙琳·费克斯和小約瑟夫·霍奇斯于1951年首次提出,后来由托馬斯·寇弗(英语:Thomas M. Cover)扩展。在这两种情况下,输入包含特徵空間(英语:Feature Space)中的k个最接近的训练样本。...
15 KB (2,339 words) - 00:24, 8 January 2024
發式演算法處理許多實際問題時通常可以在合理時間內得到不錯的答案。 有一類的通用啟發式策略稱為元启发算法(metaheuristic),通常使用亂數搜尋技巧。他們可以應用在非常廣泛的問題上,但不能保證效率。 所謂的最短路径問題有很多種意思,在這裡啟發式指的是在一個搜尋樹的節點上定義的函数 h ( n )...
5 KB (827 words) - 15:13, 10 December 2022
Tarjan算法(以發現者Robert Tarjan命名)是一個在圖中尋找強連通分量的算法。雖然發表時間更早,它仍可以被視為Kosaraju算法的一個改進。它的效率跟Gabow算法(英语:Gabow's algorithm)差不多。 此算法以一個有向圖作為輸入,並按照所在的強連通分量給出其頂點集的一...
6 KB (957 words) - 05:34, 2 May 2023