摘要
计算时间下界的传统的方法是直接从算法的ＡＤＴ高度来分析或借助于问题的变换来分 析．本文提出估计算法计算时间下界的一条新思路，借助于问题的嵌入来分析计算时间下界．由此 可获得一些传统方法不易得到的结果．
Lower bound question is of general concern in the field or design and analysis of algorithm, it is obtained by direct analysics or by reduction, In this paper we present a new idea to analyse lower bound and obtain several good results.
出处
《福州大学学报（自然科学版）》
CAS
CSCD
1991年第2期19-26,共8页
Journal of Fuzhou University(Natural Science Edition)
关键词
算法可解问题
计算复杂性
计算时间
computational complexity
lower bound
asymptoticly optimal algorthm
computational geometry
