标题：Complexity Research on B Algorithm
作者机构：[Han, Aili] Shandong Univ, Sch Informat Engn, Weihai 264209, Peoples R China.
会议名称：International Conference on Information Technology for Manufacturing Systems
会议日期：JAN 30-31, 2010
来源：INFORMATION TECHNOLOGY FOR MANUFACTURING SYSTEMS, PTS 1 AND 2
关键词：algorithm complexity; intelligent search; B algorithm
摘要：The time complexity of B algorithm, one of the intelligent search algorithms, is discussed. By anatomizing some instances, it is pointed out that the cost of calculating the value of heuristic function should be included in the range of time complexity analysis for B algorithm. And then, an algorithm of calculating the value of heuristic function is presented. By analyzing the cost of calculating the value of heuristic function, it is pointed out that the number of recursions in B algorithm is O(n!) in the worst case. Therefore, the time complexity of B algorithm is exponential instead of O(n(2)).