原地算法

原地算法【原地算法】在计算机科学中,一个原地算法(in-place algorithm)是一种使用小的,固定数量的额外之空间来转换资料的算法 。当算法执行时,输入的资料通常会被要输出的部份覆盖掉 。不是原地算法有时候称为非原地(not-in-place)或不得其所(out-of-place) 。
基本介绍中文名:原地算法
行业:计算机科学
简介一个算法有时候会不正当地被称为原地算法,只因为它用它的输出资料会覆盖掉它的输入资料 。事实上这并不足够(在快速排序案例中所展示的)或是它所必须的;输出资料的空间可能是固定的,或如果以输出为串流资料而言,也甚至是可能无法被数清楚的 。另一方面来看,有时候要决定一个算法是不是原地,而数它的输出空间可能是比较可行的,像是底下的第一个的 reverse 範例;如此使得它更难去严格地定义原地算法 。在理论上的套用像是log-space reduction,更是典型的总是忽略输出的空间(在这些状况,更重要的是输出为仅能写入) 。在计算上的複杂度在计算複杂性理论中,原地算法包含使用O(1)空间複杂度的所有算法,DSPACE(1)类型 。这个类型是非常有限的;它与正规语言1相等 。事实上,它甚至不包含上面所列的任何範例 。因为这个原因,我们也考虑在 L 的算法,这类型的问题需要O(log n)额外的空间,来成为原地 。虽然这个似乎与我们先前的定义矛盾,但是我们必须认为在抽象的世界,输入的资料可以是任意巨大的 。在一部真实的电脑,指标(pointer)仅需要一个小的固定数量空间,因为实体记忆体的数量是固定的,但是一般上一个大小为n的数列需要O(log n)位元来作为它的索引(index) 。结果是否意指快速排序是原地的?其实一点也不 — 技术上来说,它需要O(log2 n)空间,因为它的O(log n)堆叠框架(stack frames)每一个都含有一个固定数量的指标(每一个大小为O(log n)) 。辨别拥有 L 的原地算法拥有某些有趣的含意;举例来说,它意指存在一个(相当地複杂)原地算法,决定在一个无向图(undirected graph)中的任两个节点(nodes)之间是否存在一条路径(path),这是一个需要O(n)个额外的空间,使用典型的算法像是深度优先搜寻(depth-first search)(每个节点有个走访的位元)的问题 。有些问题像是决定一个图形是否为二分图(bipartite graph)或测试两个图形使否有相同数量的连结元件(connected component),接着针对这些问题产出原地算法 。参考SL有更多的资讯 。随意的角色在很多情况,藉由使用随机化算法(randomized algorithms),一个算法的空间需求可以被极度地裁减掉 。举个範例,我们希望知道一个有 n 个顶点(vertices)的图形中的两个顶点是否位于图中同一个连线元件(connected component) 。没有已知简单、决定性的(deterministic)、原地算法来决定这件事,但是如果我们简单地由一个顶点开始,且执行大约20n3步的随机走路(random walk),那我们会偶遇到其他顶点来提供它不是在同一个元件(component)中的机会是非常地高 。类似地,对于质数测试(primality test)有简单的随机化原地算法像是米勒-拉宾检验,也有简单原地随机化整数分解算法像是Pollard's rho 算法 。参考RL和BPL有对这个现象更多的讨论 。在函式的程式设计函式程式设计(functional programming)语言经常不鼓励或不支援会覆盖资料的原地算法,因为这是副作用的一种型态;反之,他们只允许建立新的资料 。然而,好的函式语言编译器(compiler)在当一个与以存在之非常相似的物件被建立时,都经常会辨识出来,然后旧的就会被丢弃掉,而且会最把这最佳化为一个简单的"引擎盖之下"转换 。基本上,有可能小心地建构原地算法而部会更动资料(除非资料已不会再被使用),但是在实际上这却很少见到 。参考纯函式数据结构(purely functional data structure) 。