Notes on the complexity of sorting in abstract machines |
| |
Authors: | Martti Penttonen Jyrki Katajainen |
| |
Institution: | (1) Department of Computer Science, University of Turku, SF-20500 Turku, Finland |
| |
Abstract: | The complexity of sorting with pointer machines and successor-predecessor random access machines is studied. The size of the problem is defined as the length of the problem string. A linear time algorithm is achieved for sorting by pointer machines. For successor-predecessor random access machines linear time is sufficient in a special case. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |