函数渐进界的性质研究.pdfVIP

学兔兔 务l 訇 化 函数渐进界的性质研究 The property research of function gradully boundary 杨冀林 YANG Ji-lin (赤峰学院 计算机科学与技术系 ，赤峰 024000) 摘 要：在计算机算法设计和复杂性分析中，经常会利用函数渐进的界对一个算法的时间和空间复杂 度 进行分析 ，但却很 少有资料 对函数渐进界的性质进行 系统研究。本文给出函数渐进上界 、 下界 、紧致界的概念及几何解释 ，0，Q，o，0符号及其等价性 ，分类给出函数渐进界 的重要性 质并给予严格的数学证 明，这些性质在算法分析中有着重要应用 。 关键词：函数渐进的上界；下界；紧致界；0，Q，@，0符号及其等价性；重要性质 中国分类号 ：TP391 文献标识码 ：B 文章编号 ：11)1(下)-01 34(201009-01 83-04 Doi：10．3969／J．issn．1 009-01 34．2011．1(下)．62 1 1 函数渐进界的定义 不为零，则 n)=Q(g(，2))。渐进下界的几何解释如 定义 1：设 n)，g(n)是定义 在 自然数 集 N 上 图 2所 示 。 的两个非负实值函数，如果存在 自然数 和正常 数 c，使得 ≥ n。，都 有f(n)≤cg(n)，则称 g(n) ， 一 f 是f(n)的一个渐进上界，记作 ，z)：O(g(，1))。 ，， 、 根 据渐 进 上 界 与极 限 定 义 ，若lim 存 在且 — gtn) ～ ? ～ ．．． 一 有限，则 ，z)=O(g(n))。渐进上界的几何解释如图 l 1所示 。 广 cj n1 0 no n， ．．．．．．．．．． 图2 渐 近 下 界 的 几 何 解释 ～ - ．／ ff