La complessità temporale dell'aggiornamento e della ricerca nell'elenco di accesso casuale binario

Question

La complessità temporale dell'aggiornamento e della ricerca nell'elenco di accesso casuale binario

#1 da (1 voti)

2

Sto cercando di superare uno degli esercizi di "Purely Functional Data Structures" di Okasaki, dove presenta un numero binario zeroless come struttura per l'elenco di accesso casuale e chiede di

9.6 Show that lookup and update on element i now run in O(log i) time.

"now" qui contrasta la rappresentazione zeroless con un semplice elenco di accessi randomizzati con albero binario, per il quale il tempo di ricerca e aggiornamento è stato stimato come O (log n) .

L'approccio in entrambi i casi è simile: manteniamo una lista di "cifre" Contro, con ogni cifra diversa da zero contenente un albero di dimensioni corrispondente al peso della cifra. L'elenco nel suo complesso è una rappresentazione binaria (o binario zeroless) del numero di elementi nell'elenco.

Ad esempio, un elenco di 6 elementi, [1, 2, 3, 4, 5, 6] (binario per 6 è 111, zeroless binario è 22) avrà l'aspetto di

[
  Zero,
  One(Node(Leaf(1), Leaf(2)),
  One(Node(Node(Leaf(3), Leaf(4)), Node(Leaf(5), Leaf(6))))
]

in binario o

[
  Two(Leaf(1), Leaf(2)),
  Two(Node(Leaf(3), Leaf(4)), Node(Leaf(5), Leaf(6))
]

nella rappresentazione binaria zeroless. Ora, lookup e update volte sono definite dal tempo che trascorri a localizzare l'albero con l'elemento i -th e dal tempo che passi a percorrere la struttura.

Quello che non capisco è perché loookup di i l'elemento in una lista di accesso casuale binaria richiede O (log n) piuttosto che O (log i) ? Abbiamo bisogno di localizzare l'albero che contiene l'elemento i - che è O (log i) , la navigazione all'interno dell'albero è limitata da O (log w) , dove w è la dimensione dell'albero, che è chiaramente inferiore a i * 2 .

Cosa mi manca?

functional-programming data-structures complexity

posta alf 11.09.2015 - 17:56

fonte

1 risposta

Leggi altre domande sui tag functional-programming data-structures complexity

Come posso rilevare un evento tattile in un sistema di blob-tracking computer-vision? Processo per il trasferimento di compiti TFS tra utenti?

score 1 · Answer 1

Bene, complimenti a @snowman per il consiglio di riscrivere la domanda in inglese semplice - ho trovato una risposta mentre lo facevo.

Il limite O (log n) deriva dal modo in cui funzionano i numeri binari: hanno zero. Ad esempio, un binario per 8 è 100 o, invertito, 001 . Quindi l'elenco di accesso casuale binario di 8 elementi (ad esempio [1, 2, 3, 4, 5, 6, 7, 8] ) avrà la seguente struttura:

[
  Zero,
  Zero,
  One(
    Node(
      Node(
        Node(Leaf(1), Leaf(2)),
        Node(Leaf(3), Leaf(4))
      ),
      Node(
        Node(Leaf(5), Leaf(6)),
        Node(Leaf(7), Leaf(8))
      )
    )
  )
]

Qui, è chiaro che ogni elemento richiederà esattamente 2 log n passi per arrivare (se non ti fidi di me su questo, gioca con n = 2 ^ k , ad es. 256, 1024, 65536 ...). Quindi la premessa che "Abbiamo bisogno di localizzare l'albero che contiene l'elemento ith - cioè O (log i) , la navigazione all'interno dell'albero è limitata da O (log w) , dove w è la dimensione dell'albero, che è chiaramente inferiore a i * 2 "era fondamentalmente sbagliato: la dimensione dell'albero non dipende dall'indice dell'elemento e la posizione dell'albero è dettata dai bit di n , non i .

Nei numeri zero, al contrario, abbiamo sempre almeno un albero di ogni dimensione possibile, quindi possiamo essere sicuri che l'albero si troverà effettivamente in O (log i) , e la dimensione non sarà superiore a 2i .