算法及其时间复杂度可同步形式化推导的方法  

Formally deduce approach of algorithm and its time complexity synchronously

作　　者：王昌晶[1] 薛锦云[1] 

机构地区：[1]中国科学院软件研究所

出　　处：《计算机应用研究》2008年第3期681-683,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(60273092);国家“973”计划资助项目(2003CCA02800);江西省2004年教学改革课题基金资助项目;江西师范大学2005年青年成长基金资助项目

摘　　要：对在长期的算法研究中提出的PAR方法和PAR平台引入时间谓词加以扩展,不仅可以形式化推导出顺序查找和二分查找问题的算法程序,而且这两个问题关于时间复杂度的递归方程式也可同步且自然地推导得到。这为开发并验证高效率的算法开辟了一条新途径。This paper extend the partition-and-recur（PAR） approach which presented in the long-term research of algorithms through importing time prediction. Then the PAR approach could formally deduce not only sequential search and binary search problem＇ s algorithms, but also their recursion equations about time complexity simultaneously and naturally. It pioneers a new avenue to develop and verify high efficiency algorithms.

关 键 词：分划递推方法 形式化推导 时间复杂度 递归方程式 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]