Prestazioni di un algoritmo Skip-List

1

Ecco un semplice codice per un elenco skip randomizzato:

Coin_Side flip()
{
    if ( random() % 2 == 0 )
        return HEADS;
    else
        return TAILS;
}

Nota: random () restituisce un numero intero che utilizza un modulo del modulo M = 2 ^ B. Quindi, qual è la prestazione prevista dell'algoritmo skip list?

Quindi abbiamo: (ax mod M) mod 2 = (ax mod 2 ^ B) mod 2 = (ax mod 2) mod 2 ^ B

Posso vedere che ((ax mod 2) == 0) sarà vero se ax è pari. Quindi, aggiungendo mod 2 ^ B, salteremo più valori nella skip-list. Avremmo solo i numeri pari che sono multipli di 2 ^ B. Quindi renderebbe l'algoritmo migliore o peggiore?

    
posta Nicolas 21.07.2013 - 17:20
fonte

0 risposte

Leggi altre domande sui tag