From: Claudio Petasecca D. [email protected]
To: [email protected]
Sent: Thursday, 25 September, 2008 14:53:23
Subject: Re: [ruby-it] Il problema di Matteo all’RSCCon Ruby 1.9 (credo) possiamo sfruttare il metodo group_by, che e’
definito anche in Rails:
giovanni non vi ha dato la constraint più interessante: spazio costante.
L’array va modificato in place effettundo degli swap (con qualche var
ausiliaria), e in tempo lineare.
Io so la sua soluzione ma mi piacerebbe sapere se qualcuno ha idea del
limite di complessità raggiungibile.
per il caso con due partizioni è O(N) credo, dove N è la dimensione della
partizioni più grande, ma mi chiedo quale sia il caso generale.