• Articles • Previous Articles     Next Articles

Average-Case Analysis of Algorithms Using Kolmogorov Complexity

JIANG Tao; LI Ming; Paul M.B;   

  1. Vitanyi Department of Computing Science; University of California; Riverside; CA 92521; USA Dopartment of Computer Science; Santa Barbara; CA 95106; USA CWI and University of Amsterdam; Kruislaan 41;
  • Online:2000-09-10 Published:2000-09-10

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 sortin…

Key words: nonmonotonic consequence relation,conditional logic,rational monotony,injective PRC model,quasi-linear model;



[1] Knuth D E. The Art of Computer Programming. Vo1.3: Sorting and Searching, Addison-Wesley, 1973 (1st Edition), 1998 (2nd Edition).

[2] Tarjan R E. Sorting using networks of queues and stacks. Journal of the ACM, 1972, 19: 341-346.

[3] Jiang T, Li M, Vitanyi P. A lower bound on the average-case complexity of Shellsort. J. Assoc. Comp. Mach., to appear. Also in ICALP'99, July 11-15, 1999, Prague. ……….
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved