原地算法是什么?关于原地算法的详细介绍

创闻科学2020-11-17 12:21:48

在计算机科学中,原地算法是一个使用辅助的数据结构对输入进行转换的算法。但是,它允许有少量额外的存储空间来储存辅助变量。当算法运行时,输入通常会被输出覆盖。原地算法仅通过替换或交换元素来更新输入序列。不是原地算法有时候称为非原地(not-in-place)或者不得其所(out-of-place)

原地可以有稍微不同的含义。在其最严格的形式中,该算法只能有恒定数量的额外空间,计算包括函数调用和指针在内的所有内容。然而,这种形式非常受限,因为简单地对长度为n的数组进行索引需要0(logn)位。更广泛地说,原地算法不使用额外的空间来操作输入,但可能需要一个小而非恒定的额外空间来进行操作。通常,这个空间是0(log n),尽管有时 o(n) 也是允许的。注意当是否将索引长度作为所用空间的一部分计算在内是,空间复杂度有着不同的选择。通常,空间复杂度计算忽略了它们的长度,根据所需的索引或指针的数量给出。在本文中,我们指的是总空间复杂性(DSPACE),计算指针长度。因此,与忽略索引和指针长度的分析相比,这里的空间需求有一个额外的对数因子n

算法可以将输出计算为或不计算为其使用空间的一部分。因为原地算法通常用输出覆盖它们的输入,所以不需要额外的空间。当将输出写入只写存储器或流时,只考虑算法的工作空间可能更合适。在理论应用中,例如对数空间缩减更典型的是总是忽略输出空间(在这些情况下,更重要的是输出是write-only)。

例子

给定一个包含 n 个元素的数组a,假设我们需要一个数组,它以相反的顺序保存相同的元素并处理原始元素。一种看似简单的方法是创建一个大小相等的新数组,复制a里的元素,然后删除a

 function reverse(a[0..n - 1])
     allocate b[0..n - 1]     for i from 0 to n - 1
         b[n − 1 − i]:= a[i]     return b

不幸的是,这需要0(n) 额外空间用于同时存储置数组的ab。此外,分配和释放分配通常是缓慢的操作。因为我们不再需要a,我们可以使用原地算法,用它自己的反转来覆盖它,不管数组有多大,它只需要常量(2)的整数的辅助变量itmp

 function reverse_in_place(a[0..n-1])     for i from 0 to floor((n-2)/2)
         tmp:= a[i]
         a[i]:= a[n − 1 − i]
         a[n − 1 − i]:= tmp

另一个例子,许多排序算法使用原地算法将数组重新排列,包括: 冒泡排序, 梳子分类, 选择排序法, 插入排序, 堆排序,和 希尔排序。这些算法只需要几个指针,所以它们的空间复杂度是O(log n)

快速排序对要排序的数据进行原地操作。然而,快速排序需要O(log n) 堆栈空间指针以跟踪其分治法策略。因此,快速排序需要O(log n) 额外的空间。虽然这种非恒定空间在技术上使快速排序脱离了原地算法类别,但快速排序和其他算法只需要O(log n) 附加指针通常被认为是原地算法。

大多数选择算法也是原地的,尽管有一些在寻找最终的、大小不变的结果的过程中对输入数组进行了相当大的重新排列。

一些文本操作算法,例如Trim和反转可以通过原地完成。

在计算复杂性方面

在计算复杂性理论中,原地算法的严格定义包括所有具有O(1)空间复杂度的算法,类 DSPACE(1)。这门课非常有限;它等于正规语言. 事实上,它甚至不包括上面列出的任何例子。

我们通常在 L,需要操作的问题类别(日志 n)额外空间到位。这个类更符合实际定义,因为它允许大小为n的数字作为指针或索引。然而,由于快速排序的递归调用,这个扩展的定义仍然不包括快速排序。

用L识别原地算法有一些有趣的含义;例如,这意味着有一个(相当复杂的)原地算法来确定无向图, 需要操作的问题(n)使用典型算法的额外空间,例如深度优先搜索 (每个节点的访问位)。这反过来又产生了针对诸如确定图形是否双方的或者测试两个图表是否具有相同数量的连接组件。

随机性的作用

在许多情况下,通过使用随机化算法,一个算法的空间需求可以被极度地裁减掉。例如,我们希望知道一个有n个顶点(vertices)的图形中的两个顶点是否位于图中同一个连接组件。没有已知的简单的、确定的、原地的算法来确定这一点,但是如果我们简单地从一个顶点开始并执行随机游走大约20个n 步骤,如果它在同一个组件中,我们偶然发现另一个顶点的可能性非常高。类似地,也有简单的随机原地算法用于质数测试,例如米勒-拉宾素性检验,还有简单的原地随机化因子分解算法,例如波拉德ρ算法。

在函数式编程中

函数式编程语言经常不鼓励或不支持会覆盖数据的原地算法,因为这是一种副作用的类型;相反,它们只允许构建新数据。然而,好的函数式语言编译器通常会识别出一个与现有对象非常相似的对象是什么时候创建的,然后旧的对象被丢弃,并且会将它优化成一个简单的“幕后”变异。

注意,原则上可以仔细构建不修改数据的原地算法(除非数据不再被使用),但实际上很少这样做。