保持空间复杂性的算法组合

• 作者: 石竑松 秦志光
• 来源期刊: 计算机应用研究
• 关键词: 算法组合 空间复杂性 库克归约 预言机查询
• 年，卷（期）: 2010,（6）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2020-2023
• 分类号: TP301.5|TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2010.06.005

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	秦志光	电子科技大学计算机科学与工程学院	262	3157	26.0	46.0
2	石竑松	电子科技大学计算机科学与工程学院	6	7	1.0	2.0