论文研究 保持空间复杂性的算法组合.pdf

分析了组合两种算法所需的空间复杂度在何种情况下为原算法的空间复杂度之和的问题，即空间复杂度的保持问题。通过形式化oracle查询方式，证明了在后续oracle查询和前面所有的oracle回复都不相关，即非适应性查询情况下，算法组合将保持空间复杂性，但在适应性查询情况时不一定成立。