CAJ | 학술논문

提出了一种反向Hash链遍历的时间、空间复杂度优化算法.采用堆栈操作实现了高效的反向Hash链遍历,并将Hash链遍历过程映射到了二叉树的后序遍历过程,利用二叉树性质对存储和计算性能进行了理论化分析和证明.分析证明结果表明,遍历对长为n的反向Hash链时,算法只需要存储「1bn」+1个节点值,并且进行不多于((「) 1b n」/2+1)n次Hash计算次数.相比同类其他算法,该算法并不要求链长为2的整数次方.通过对算法进行基于k叉树(k≥3)的扩展,进一步将存储空间降低到(「)logk[(k-1)n+1]」,但总计算次数提高到[(「)log[(k-1)n+1]」-1)k/2+1]n；通过在算法执行前先把Hash链平分为p段(P≥2),将总计算次数降低到([1b(n/p)]/2+1)n,但是所需的存储空间提高到([1b(n/p)]+1)p.
제출료일충반향Hash련편력적시간、공간복잡도우화산법.채용퇴잔조작실현료고효적반향Hash련편력,병장Hash련편력과정영사도료이차수적후서편력과정,이용이차수성질대존저화계산성능진행료이론화분석화증명.분석증명결과표명,편력대장위n적반향Hash련시,산법지수요존저「1bn」+1개절점치,병차진행불다우((「) 1b n」/2+1)n차Hash계산차수.상비동류기타산법,해산법병불요구련장위2적정수차방.통과대산법진행기우k차수(k≥3)적확전,진일보장존저공간강저도(「)logk[(k-1)n+1]」,단총계산차수제고도[(「)log[(k-1)n+1]」-1)k/2+1]n；통과재산법집행전선파Hash련평분위p단(P≥2),장총계산차수강저도([1b(n/p)]/2+1)n,단시소수적존저공간제고도([1b(n/p)]+1)p.