我注意到可以在线性时间内解决的问题可以调整为使用不超过O(1)辅助空间.对路径图采取加权独立集问题.如果仅需要总重量,则需要O(1)空间.但是如果在解决方案中也要求set,那么它使用O(n)空间,但是,使用的辅助空间仍然是O(1).允许线性时间算法的其他问题是最大子阵列求和问题,通过i位置旋转1D向量,将BST转换为已排序的双向链表等等...
The Z algorithm, linear-time suffix array generation, the Burrows-Wheeler Transform, etc. all need O(n) auxiliary space.
实际上,我认为即使是深度优先搜索,广度优先搜索等,在最坏的情况下也需要O(n)辅助空间(DFS的链表,BFS的单层树).