原地算法

✍ dations ◷ 2025-06-08 07:56:19 #算法

在计算机科学中,一个原地算法(in-place algorithm)基本上不需要额外辅助的数据结构,然而,允许少量额外的辅助变量来转换数据的算法。当算法运行时,输入的数据通常会被要输出的部分覆盖掉。不是原地算法有时候称为非原地(not-in-place)或不得其所(out-of-place)。

一个算法有时候会错误地被称为原地算法,只因为它用它的输出数据会覆盖掉它的输入数据。事实上这条件既不充分(在快速排序案例中所展示的)也非必要;输出数据的空间可能是固定的,或如果以输出为流数据而言,也甚至是可能无法被数清楚的。另一方面来看,有时候要决定一个算法是不是原地,而数它的输出空间可能是比较可行的,像是底下的第一个的reverse示例;如此使得它更难去严格地定义原地算法。在理论上的应用像是log-space reduction,更是典型的总是忽略输出的空间(在这些状况,更重要的是输出为)。


假设我们想要将拥有个项目的数组反过来。一个最简单作这件事的方式是这样:

 function reverse(a)     allocate b     for i from 0 to n         b = a     return b

不幸地,这样需要O()的空间来创建数组,且配置存储器通常是一件缓慢的运算。如果我们不再需要,我们可使用这个原地算法,用它自己反转的内容来覆盖掉:

 function reverse-in-place(a)     for i from 0 to floor(n/2)         swap(a, a)

在其他的例子,有数个排序算法会原地重新排放数组内容成为排序过的顺序,包含:

快速排序通常被描述为一个原地算法,但是事实上并不是。大部分的实现需要O(log )的空间来支持它的分治法(divide-and-conquer)递归。

大部分选择算法也是原地,虽然在找到最后结果的过程中,有某些相当地重新排列输入数组,但却是固定大小的结果。

在计算复杂性理论中,原地算法包含使用O(1)空间复杂度的所有算法,DSPACE(1)类型。这个类型是非常有限的,它与正则语言1相等。事实上,它甚至不包含上面所列的任何示例。

因为这个原因,我们也考虑在L的算法,这类型的问题需要O(log )额外的空间,来成为原地。虽然这个似乎与我们先前的定义矛盾,但是我们必须认为在抽象的世界,输入的数据可以是任意巨大的。在一部真实的电脑,指针(pointer)仅需要一个小的固定数量空间,因为物理内存的数量是固定的,但是一般上一个大小为的数列需要O(log )比特来作为它的索引(index)。

结果是否意指快速排序是原地的?其实一点也不—技术上来说,它需要O(log2 )空间,因为它的O(log )堆栈帧架(stack frames)每一个都含有一个固定数量的指针(每一个大小为O(log ))。

辨别拥有L的原地算法拥有某些有趣的含意;举例来说,它意指存在一个(相当地复杂)原地算法,决定在一个无向图(undirected graph)中的任两个节点(nodes)之间是否存在一条路径(path),这是一个需要O()个额外的空间,使用典型的算法像是深度优先搜索(depth-first search)(每个节点有个走访的比特)的问题。有些问题像是决定一个图形是否为二分图(bipartite graph)或测试两个图形使否有相同数量的连通分支,接着针对这些问题产出原地算法。参考SL有更多的信息。

在很多情况,借由使用随机化算法(randomized algorithms),一个算法的空间需求可以被极度地裁减掉。举个示例,我们希望知道一个有个顶点(vertices)的图形中的两个顶点是否位于图中同一个连接组件(connected component)。没有已知简单、决定性的(deterministic)、原地算法来决定这件事,但是如果我们简单地由一个顶点开始,且运行大约203步的随机走路(random walk),那我们会偶遇到其他顶点来提供它不是在同一个组件(component)中的机会是非常地高。类似地,对于质数测试(primality test)有简单的随机化原地算法像是米勒-拉宾检验,也有简单原地随机化整数分解算法像是Pollard's rho算法。参考RL和BPL有对这个现象更多的讨论。

函数程序设计(functional programming)语言经常不鼓励或不支持会覆盖数据的原地算法,因为这是副作用的一种类型;反之,他们只允许创建新的数据。然而,好的函数语言编译器(compiler)在当一个与已存在之非常相似的对象被创建时,都经常会识别出来,然后旧的就会被丢弃掉,而且会最把这最优化为一个简单的"引擎盖之下"转换。

基本上,有可能小心地建构原地算法而不会更动数据(除非数据已不会再被使用),但是在实际上这却很少见到。参考纯函数数据结构(purely functional data structure)。

Maciej Liśkiewicz and Rüdiger Reischuk. The Complexity World below Logarithmic Space. , pp.64-78. 1994.

Omer Reingold. Undirected ST-connectivity in Log-Space. Electronic Colloquium on Computational Complexity. No. 94.

1. Liśkiewicz and Reischuk, pg.3, Theorem 2.

2. Reingold.

相关

  • 心血管绕道手术冠状动脉旁路移植(英语:Coronary artery bypass graft,常缩写为CABG)或心脏绕道手术,俗称冠脉搭桥或搭桥,即冠状动脉旁路移植术,是一项缓解心绞痛和减少冠心病死亡风险的手术。搭桥
  • 苯环芳香环是一类有机芳香化合物。芳香环拥有共轭的平面环体系,原子间成键并不是不连续的单双键交替,而是被离域π电子云覆盖。典型的芳香环化合物是苯和吲哚。简单的单环芳香化合
  • 富勒顿加州州立大学富勒顿分校(California State University, Fullerton,或称:CSUF、Cal State Fullerton或Fullerton State)是位于美国加利福尼亚州富勒顿的一所公立大学,隶属于加利福
  • 山茶花山茶(学名:Camellia japonica),又名山茶花,山茶属植物,属常绿灌木和小乔木。古名海石榴。有玉茗花、耐冬等别名,日语称作椿,在韩语中也被叫做冬柏花,在韩国海云台区冬柏岛就是以茶花
  • 正单链RNA病毒正单链RNA病毒(英语:positive-sense single-stranded RNA virus,又称(+)ssRNA virus、单股正链RNA病毒、单正链RNA病毒及阳性单链RNA病毒),其基因组为一条正单链RNA。网巢病毒目():
  • 邻乙氧苯甲酰胺邻乙氧苯甲酰胺(ethenzamide、2-ethoxybenzamide、乙水杨胺、乙柳酰胺、乙氧基苯酰胺)是一种常用的止痛与抗炎性药物,用于缓解发烧、头痛及其他轻微的疼痛。它也是许多普通感冒
  • 香菇属香菇属(学名:),是伞菌目小皮伞科的一属,于1909年由美国真菌学家富兰克林·萨姆纳·厄尔(英语:Franklin Sumner Earle)描述发表,其模式种为生长在新热带界的卷木菇(瑞典语:Lentinula bor
  • 四氢噻吩溴化亚金四氢噻吩溴化亚金(英语:Bromo(tetrahydrothiophene)gold(I))是金的配合物,和更常用的四氢噻吩氯化亚金类似,四氢噻吩基容易被其他较强的配基取代,形成线性的金溴错合物。此化合物
  • Rainbow Syndrome《Rainbow Syndrome》是韩国的女子组合Rainbow的第1枚正规韩语专辑。唱片公司为DSP Media。此曲与“A”、“Mach”,至今仍然是Rainbow在现场表演的必唱作品。
  • 短期自偿性贷款短期自偿性贷款主要是工商业流动资金贷款,包含订单贷款,应收帐款贷款,发票贷款,合约贷款及票据贴现贷款等。这种贷款一般期限较短,有确定的偿还来源的贷款,并以实际的票据作为抵押