欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
分析了组合两种算法所需的空间复杂度在何种情况下为原算法的空间复杂度之和的问题,即空间复杂度的保持问题。通过形式化oracle查询方式,证明了在后续oracle查询和前面所有的oracle回复都不相关,即非适应性查询情况下,算法组合将保持空间复杂性,但在适应性查询情况时不一定成立。
英文摘要：
This work considered the space complexity preserving problem, that was under which conditions the space comple-xity of composing two algorithms will be the sum of the space complexity of the two original algorithms. By formalizing the ways of oracle queries, this paper proved that the space complexity would preserve when oracle queries were non-adaptive, i.e., the oracle queries were independent of the past oracle answers, but space complexity would not preserve in the adaptive case.
同期刊论文项目
同项目期刊论文
期刊信息
位置：