algorithm - 是否有任何算法是 O(n) 时间并且必须使用 O(n) 辅助空间？

Question

我注意到可以在线性时间内解决的问题可以调整为使用不超过 O(1) 的辅助空间。以路径图的加权独立集问题为例。如果只需要总重量，则需要 O(1) 空间。但是如果在解决方案中也要求集合，那么它使用 O(n) 空间，但是，使用的辅助空间仍然是 O(1)。其他允许线性时间算法的问题是最大子数组求和问题、将一维向量旋转 i 个位置、将 BST 转换为排序的双向链表等......

Answer 1

Z 算法、线性时间后缀数组生成、Burrows-Wheeler 变换等都需要 O(n) 辅助空间。

实际上，我认为即使是深度优先搜索、广度优先搜索等，在最坏的情况下也需要 O(n) 辅助空间（DFS 的链表，BFS 的单层树）。