The Number of Steps in the Robinson-Schensted Algorithm |
| |
| Authors: | D Romik |
| |
| Institution: | (1) Department of Mathematics, The Weizmann Institute of Science, Israel |
| |
| Abstract: | Suppose that a permutation σ ∈ S
n
is chosen at random (n is large) and the Robinson-Schensted algorithm is applied to compute the associated Young diagram. Then for almost all permutations the number of bumping operations performed by the algorithm is about (128/27π2)n
3/2, and the number of comparison operations is about (64/27π2)n
3/2 log2
n.__________Translated from Funktsional’nyi Analiz i Ego Prilozheniya, Vol. 39, No. 2, pp. 82–86, 2005Original Russian Text Copyright © by D. Romik |
| |
| Keywords: | Robinson-Schensted algorithm analysis of algorithms Young tableaux Plancherel measure |
| 本文献已被 SpringerLink 等数据库收录！ |
|
