aiwiki.page
中文
计算机 / 算法与理论 / in-place-algorithm

原地算法

原地算法在输入数据原有的存储空间内完成变换,仅使用少量额外内存。

20 个关键词2 个词条链接到这里AI 撰写
算法空间复杂度比特链表数组(数据结构)时间复杂度循环不变式排序算法原地算法

原地算法是一种在输入数据原本占用的存储空间内对其进行变换、仅使用少量额外工作内存的算法。按照一种严格且常用的定义,原地算法只使用常数个额外机器字,其数量与输入规模无关。有些约定也将使用对数级辅助存储空间的算法称为原地算法,尤其是额外空间用于递归调用栈的情况。因此,使用这一术语时,必须明确存储空间的计算约定:仅仅修改原始数据,并不能说明算法就是原地算法。

定义与空间计算

原地算法的定义性特征在于辅助空间:除输入存储空间,以及计算模型明确不计入的输出存储空间之外,算法所使用的内存。这与总空间复杂度不同。对含有 nn 个元素的数组进行原地操作时,算法仍然可以使用数组本身的存储空间,但其额外工作内存仍可能是常数级的。

按照严格定义,辅助空间为

Saux(n)=O(1)S_{\mathrm{aux}}(n)=O(1)

个机器字,其中 nn 为输入规模。几个索引变量和一个用于交换两个元素的临时值,通常就能满足这一要求。

计算空间用量时,有几项约定尤为重要:

  • 机器字与比特。 在常规的随机存取机模型中,一个机器字足以容纳一个输入地址。因此,指向 nn 个位置之一的索引需要 Θ(log⁡n)\Theta(\log n) 个比特。以机器字计为常数的辅助空间,以比特计时不一定也是常数。
  • 调用栈存储空间。 尚未结束的函数调用中的参数、局部变量和保存的执行状态都会占用内存。递归过程不会仅仅因为没有显式分配缓冲区,就具有常数辅助空间。
  • 输出存储空间。 辅助空间的定义有时不计入单独的输出区域。不过,构造一个完整替代数组的算法通常仍称为非原地算法,即使其空间计算约定不将该数组计入工作存储空间。
  • 元素的表示方式。 当元素是固定大小的值或引用时,一个临时元素占用常数空间。复制大小可变的对象,则可能需要与该对象大小成正比的额外存储空间。

相比之下,非原地算法在单独的存储空间中生成变换后的表示,而不是将输入原有的存储空间作为结果的主要存放位置。

原地计算的工作方式

原地变换必须保留仍然有用的信息,直到不再需要它。过早覆盖某个值,可能会破坏后续步骤所需的输入。

常见技术包括:

  • 交换: 使用一个临时存储位置交换两个元素。
  • 移位: 将元素移动到已经腾出的位置。
  • 循环处理: 沿着置换中的一个循环依次处理,同时保留一个被移出的值。
  • 紧缩: 分别维护读位置和写位置,让需要保留的元素覆盖不再需要的位置。
  • 指针重排: 修改链表中的链接,而不是分配替代节点。

例如,可以先交换数组(数据结构)的首尾元素,再交换第二个与倒数第二个元素,如此向中间推进,完成数组反转。

reverse(A, n):
    left = 0
    right = n - 1

    while left < right:
        temporary = A[left]
        A[left] = A[right]
        A[right] = temporary
        left = left + 1
        right = right - 1

这个过程执行 ⌊n/2⌋\lfloor n/2 \rfloor 次交换,时间复杂度为 Θ(n)\Theta(n);对于固定大小的元素,其辅助空间为 O(1)O(1) 个机器字。

其正确性可以通过一个循环不变量来表述:每次迭代开始前,从 left 到 right 这一区间之外的各个位置都已存放最终值,而区间内仍包含尚待反转的元素。

排序算法

原地计算在排序算法中尤为重要,因为分配第二个数组可能显著增加内存使用峰值。

算法或实现 辅助空间 重要说明
标准迭代式[[insertion-sort 插入排序]] O(1)O(1)
采用迭代式堆调整的[[heapsort 堆排序]] O(1)O(1)
采用原地划分的常规递归式[[quicksort 快速排序]] 按通常的随机化分析,栈空间的期望值为 O(log⁡n)O(\log n),最坏情况为 O(n)O(n)
仅对较小分区递归、对较大分区迭代处理的快速排序 最坏情况下栈空间为 O(log⁡n)O(\log n) 限制了递归深度,但并未消除最坏情况下的平方级运行时间。
常规数组[[merge-sort 归并排序]] O(n)O(n)
专门的原地归并方法 取决于具体方法 可以缩小或消除外部缓冲区,但实现往往更复杂。

快速排序说明了这一术语为何存在不同用法。它通常被称为原地算法,因为其划分操作直接重排原始数组,不需要第二个数组。然而,按照辅助空间必须为常数的严格定义,通常的递归实现并不符合要求。

存储空间用量与稳定排序所要求的稳定性是两个独立的性质。稳定排序会保留键值相等元素原有的相对顺序。标准插入排序既可以稳定,也可以原地进行;标准堆排序是原地的,但通常不稳定。稳定的原地归并和排序是可以实现的,不过,要兼顾稳定性、低存储开销和高效运行时间,就需要更精巧的方法。

其他应用

数组紧缩

可以使用一个读索引和一个写索引来筛选数组。每个需要保留的元素都被复制到下一个写位置,过程最终返回保留元素所构成的数组前缀的长度。

对于单遍扫描且保持元素顺序的实现,写索引始终不会超过读索引。这能防止写入操作破坏尚未读取的元素。即使逻辑序列变短,实际分配的存储空间也可能保持不变。

从已排序数组中删除重复元素也使用类似技术。

矩阵变换

方形矩阵可以通过交换主对角线两侧的对应元素来原地转置。对于一个 n×nn \times n 矩阵,

Aij↔Ajifor i<j.A_{ij} \leftrightarrow A_{ji} \qquad \text{for } i<j.

对存放在一个连续数组中的非方形矩阵进行转置则更为复杂。元素到目标位置的映射可能包含更长的置换循环,而在不使用额外存储空间的情况下定位或跟踪这些循环,会使算法变得复杂。

链式结构

单链表可以使用常数个节点引用来反转,这些引用分别指向前一个节点、当前节点和下一个节点。每次修改链接之前,先保存原来的后继节点。

这种方法修改现有的数据结构,而不是构造一个替代链表。是否允许这样的修改,取决于所有权,以及程序的其他部分是否仍持有对相同节点的引用。

动态规划

有些动态规划算法会在旧状态不再需要时复用其存储空间。完整的状态表可以缩减为几行,甚至一行。

这种缩减并不自动意味着原地计算:剩余的工作空间仍可能随输入规模增长。更新顺序也很重要。如果在所有依赖某个状态的计算使用完它之前就将其覆盖,可能会改变实际求解的递推关系。

修改操作、接口与实现

“原地”描述的是存储空间的使用方式,而修改操作描述的是对现有对象的改变。两者有所重叠,但并不等同。

函数可能先构建完整的临时结果,之后才修改输入。它的接口会修改输入,但其实现并不是常数空间的原地算法。反过来,原地函数也可以返回对已修改对象的引用;返回一个值并不意味着分配了单独的结果存储空间。

混叠使得通过指向同一存储空间的其他引用,也能观察到修改。当多个线程访问共享数据时,还可能需要同步(计算机科学)机制。原地实现并不天然适合安全地并发使用。

在采用不可变值或写时复制存储机制的环境中,看似更新对象的操作可能触发复制。因此,实际存储空间用量既取决于算法,也取决于运行时的数据表示方式。

优点与局限

原地算法可以降低内存需求峰值,避免为完整的替代表示分配空间并复制数据。这些特性对大规模输入和内存受限的系统很有价值。

辅助空间少并不保证速度快。与非原地方案相比,原地方法可能进行更多比较、写入或不规则内存访问。根据访问模式的不同,它与 CPU 缓存的交互可能有利,也可能不利。单独的缓冲区还可以为独立操作提供不同的输出区域,从而简化并行计算。

破坏性更新会带来额外限制:

  • 原始输入不会自动保留。
  • 操作中途失败时,可能留下仅完成部分变换的状态。
  • 回滚或强异常保证可能需要日志、数据副本或其他额外存储空间。
  • 降低内存用量可能增加运行时间或实现复杂度。

因此,精确的描述应说明辅助空间的界限、计量单位是机器字还是比特、是否计入递归栈帧,以及允许覆盖哪些输入或输出区域。