《计算机应用研究》|Application Research of Computers

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

Formally deduce approach of algorithm and its time complexity synchronously

免费全文下载 (已被下载 次)  
获取PDF全文
作者 王昌晶,薛锦云
机构 1.中国科学院 软件研究所,北京 100080;2.江西师范大学 计算机信息与工程学院,南昌 330027
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2008)03-0681-02
DOI 10.3969/j.issn.1001-3695.2008.03.010
摘要 对在长期的算法研究中提出的PAR方法和PAR平台引入时间谓词加以扩展,不仅可以形式化推导出顺序查找和二分查找问题的算法程序,而且这两个问题关于时间复杂度的递归方程式也可同步且自然地推导得到。这为开发并验证高效率的算法开辟了一条新途径。
关键词 分划递推方法;形式化推导;时间复杂度;递归方程式
基金项目 国家自然科学基金资助项目(60273092)
国家“973”计划资助项目(2003CCA02800)
江西省2004年教学改革课题基金资助项目
江西师范大学2005年青年成长基金资助项目
本文URL http://www.arocmag.com/article/1001-3695(2008)03-0681-02.html
英文标题 Formally deduce approach of algorithm and its time complexity synchronously
作者英文名 WANG Chang-jing, XUE Jin-yun
机构英文名 1. Institute of Software, Chinese Academy of Sciences, Beijing 100080, China; 2. School of Computer Information & Engineering, Jiangxi Normal University, Nanchang 330027, China
英文摘要 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.
英文关键词 PAR(partitionandrecur)approach; formally deduce; time complexity; recursion equation
参考文献 查看稿件参考文献
 
收稿日期
修回日期
页码 681-682
中图分类号
文献标志码 A