Mar 16 Luglio, 00:08:15 - 2019

Autore Topic: Prestazioni operazioni union find  (Letto 252 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline davidepic91

  • Studente di Dottorato
  • ***
  • Post: 232
  • FeedBack: +6/-39
    • Mostra profilo
Prestazioni operazioni union find
« il: Gio 11 Aprile, 18:35:44 - 2013 »
Salve, avrei una domanda sulle prestazioni delle partizioni con operazioni find,union e makeset.
Per l'implementazione con lista, sulle slide, c'è scritto che il costo ammortizzato di ogni operazione è O(log n). E' corretto dire che makeSet(x)=O(1) , union(A,B)=O(n) e find(p)=O(1) ?

Offline heavenriver

  • Global Moderator
  • Direttore di Dipartimento
  • *****
  • Post: 1060
  • FeedBack: +103/-67
  • z = z² + c
    • Mostra profilo
    • Sito web (Curriculum Vitae)
Re:Prestazioni operazioni union find
« Risposta #1 il: Ven 12 Aprile, 09:03:50 - 2013 »
Il costo ammortizzato che io sappia è O(n) per n operazioni, quindi costante, ma nonostante tutto non penso sia corretto quel che hai scritto, perché la singola operazione può anche avere un costo più che costante. Il fatto che i costi ammortizzati non siano superiori a quelli dipende dalla struttura intrinseca del Set: se lo organizzi come albero e applichi le due euristiche di ottimizzazione indicate nelle slides (union by size/rank e path compression) l'idea è che per ogni nodo attraversato nella find il suo puntatore viene rediretto alla radice dell'albero, che potrebbe essere cambiata a seguito di diverse union. Ma il punto è proprio questo: quante union si sono effettuate prima di quella find? Non puoi saperlo, e così non puoi sapere, in ogni find, quanto dista il tuo nodo dalla radice. Se effettui delle find sufficientemente spesso da mantenere aggiornata la struttura del tuo albero, virtualmente i costi sono sempre costanti. Se invece effettui molte più union che find, ogni find attraverserà un certo numero di nodi prima di finire tutti i redirezionamenti delle radici, e quindi sarà asintoticamente lineare.
Spero che sia chiaro, se non lo è cerca di guardare le figure sulle slides, può sembrare una cosa stupida ma a me ha aiutato parecchio a capire :P