Average-Case Analysis of Algorithms UsingKolmogorov Complexity

作     者：姜涛 李明 等 JIANG Tao;LI Ming;Paul M.B.Vitányi

作者机构：DepartmentofComputingScienceUniversityofCaliforniaRiversideCA92521USA DepartmentofComputerScienceUniersityofCaliforniaSantaBarbaraCA93106USA 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2000年第15卷第5期

页      面：402-408页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：CITO, (OGP0046506) ESPRIT Working Group Natural Sciences and Engineering Research Council of Canada, NSERC, (OGP0046613) European Commission, EC 

主　　题：Kolmogorov complexity algorithm average-case analysis sorting 

摘      要：Analyzing the average-case complexity of algorithms is a very practical but very difficult problem in computer science. In the past few years I we have demonstrated that Kolmogorov complexity is an important tool for analyzing the average-case complexity of algorithms. We have developed the incompressibility method. In this paper, several simple examples are used to further demonstrate the power and simplicity of such method. We prove bounds on the average-case number of stacks (queues) required for sorting sequential or parallel Queuesort or Stacksort.