|
|||||
|
|
A time-space tradeoff for sorting on non-oblivious machines |
|
| Authors: | Allan Borodin Michael J. Fischer David G. Kirkpatrick Nancy A. Lynch Martin Tompa |
| Affiliation: | Department of Computer Science, University of Toronto, Toronto, Ontario, M5S 1A7, Canada;Department of Computer Science, FR35, University of Washington, Seattle, Washington 98195, USA;Department of Computer Science, University of British Columbia, Vancouver, British Columbia V6T 1W5, Canada;School of Information and Computer Science, Georgia Institute of Technology, Atlanta, Georgia 30332, USA;Department of Computer Science, FR35, University of Washington, Seattle, Washington 98195, USA |
| Abstract: | A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n2. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |