Rangierkomplexität von permutationen |
| |
| Authors: | Dr Hanns -Jörg Stoß |
| |
| Affiliation: | (1) Universität Konstanz Fachbereich Mathematik, Jacob-Burckardt-Str., D-7750 Konstanz, Bundesrepublik Deutschland |
| |
| Abstract: | Summary We define a measure of complexity for
(the group of permutations ofn elements). We thus obtain non trivial lower bounds for the number of Turing steps necessary for applaying a permutation 
to a tape withn entries. Transposing annxn matrix, for example, stored linearly needs at leastCn
2 Ign steps. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
