Complessità metodo shuffle di collections

di
xneo
il
3 risposte
X
xneo
Utente Attivo
Iscritto da
mar, 2013
Messaggi:
224

Complessità metodo shuffle di collections

Ciao a tutti, mi servirebbe sapere che complessità ha il metodo shuffle di collections,
O(N^2) oppure O(n)? dove con n intendo il numero di elementi da mischiare.
grazie

3 Risposte

  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6270

    Re: Complessità metodo shuffle di collections

    xneo ha scritto:

    ciao a tutti, mi servirebbe sapere che complessità ha il metodo shuffle di collections,
    O(N^2) oppure O(n)? dove con n intendo il numero di elementi da mischiare.
    grazie
    O(n), infatti fa solo una singola passata lineare. Nota che il List ricevuto può essere di tipo RandomAccess oppure no. Se è RandomAccess, non ci sono particolari problemi, altrimenti shuffle per questioni di performance copia prima gli elementi in un array, esegue lo shuffle sull'array e poi rimette gli elementi nel List sfruttando un ListIterator.

    Basta che guardi il per sincerartene.
  • X
    xneo
    Utente Attivo
    Iscritto da
    mar, 2013
    Messaggi:
    224

    Re: Complessità metodo shuffle di collections

    Ok, credi usi l'algoritmo Durstenfeld-Knuth?
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6270

    Re: Complessità metodo shuffle di collections

    xneo ha scritto:

    credi usi l'algoritmo Durstenfeld-Knuth?
    Non so cosa sia (se fosse quello) .....

    Il for di shuffle è banale: partendo dal fondo, per ogni indice x valido (nel range 0..len-1), scambia quell'elemento con un altro elemento preso casualmente tra quelli di indice inferiore/uguale, compreso pertanto l'elemento x stesso (quindi per caso potrebbe anche non spostare un elemento).
Devi accedere o registrarti per scrivere nel forum
3 risposte