Algoritmi e Laboratorio a.a. 2006-07Lezioni

(1)

Università di Torino – Facoltà di Scienze MFN Corso di Studi in Informatica

Curriculum SR (Sistemi e Reti)

Algoritmi e Laboratorio a.a. 2006-07 Lezioni

prof. Elio Giovannetti

Parte 24 – Insiemi disgiunti (union-find)

Quest' opera è pubblicata sotto una Licenza Creative Commons Attribution-NonCommercial-ShareAlike 2.5.

Il problema union-find: descrizione informale.

Mantenere una collezione di insiemi disgiunti (sottoinsiemi di un insieme-universo E) sulla quale siano possibili le seguenti operazioni:

•union(A,B) : modifica gli insiemi A e B fondendoli in un unico insieme A∪∪∪∪B (i vecchi insiemi A e B vengono quindi persi);

•find(x): restituisce (una "rappresentazione", o "nome", del) l’insieme contenente l’elemento x;

•makeSet(x) : crea il nuovo insieme-singoletto{x}, avente x come unico elemento.

La struttura-dati è quindi un insieme (collezione) di insiemi (modificabili) di elementi di E.

Nota: Gli insiemi rimangono sempre disgiunti; quindi ad ogni istante ogni elemento appartiene a non più di un insieme.

Ricorda: Un insieme contenente un solo elemento viene detto singoletto.

(2)

28/02/2007 E. Giovannetti - AlgELab-06-07 - Lez.24 3

Union-find: una versione leggermente diversa.

Descrizione informale.

La struttura è una partizione di un insieme-universo in sottoinsiemi disgiunti, sulla quale sono definite le seguenti operazioni:

• UnionFind(Insieme U) : costruisce una partizione di U in

|U| sottoinsiemi-singoletti, uno per ciascun elemento di U (dove |U|è la cardinalità di U); cioè, usando la notazione insiemistica:

UnionFind({u₁, u₂, ..., u_n}) ={{u₁},{u₂}, ..., {u_n}}

nella programmazione a oggetti è un costruttore;

• union(A,B): come nella versione precedente;

• find(x): come nella versione precedente;

Union-find

Osserva:

• Nella prima versione: l'operazione makeSetpermette di creare, nel corso dell'esecuzione, nuovi insiemi-singoletti a partire da elementi di un dato tipo E (che costituisce quindi l'insieme-universo), aumentando così il numero totale degli elementi-base presenti nella struttura.

• Nella seconda versione: la struttura viene creata come un insieme di un numero fissato n di singoletti

{{u₁},{u₂}, ..., {u_n}}

• In entrambi i casi: insiemi contenenti più di un elemento possono venire costruiti solo tramite successive fusioni di insiemi preesistenti; si creano così insiemi sempre più grandi (con il limite della cardinalità di U, ovviamente).

• La differenza fra le due versioni, e fra esse e altre ancora un po' diverse, è inessenziale.

(3)

Union-find: verso una definizione più precisa.

• Che cosa si intende per "rappresentazione" o "nome"

di un insieme ?

• Così come in una partizione in classi di equivalenza si usa indicare una classe per mezzo di un suo elemento che funge da rappresentante, analogamente anche nella struttura union-find ogni insieme della partizione viene rappresentato da un suo elemento.

• Riformuliamo allora la definizione delle operazioni (vedi slides seguenti).

Union-find: una formulazione più precisa.

Una struttura union-find di elementi di tipo E è una struttura che rappresenta una collezione di insiemi disgiunti di elementi di tipo E, sulla quale sono definite le seguenti tre operazioni:

• makeSet(E e) crea un insieme costituito dal solo elemento e;

• E union(E e1, E e2)sostituisce i due insiemi rappresentati da e1ed e2con la loro unione – cioè fonde i due insiemi rappresentati da e1ed e2– e restituisce l'elemento rappresentante il nuovo insieme. Se e1 o e2non sono rappresentanti di insiemi, non viene effettuata alcuna operazione (e il risultato sarà ad esempio null);

• E find(E e)restituisce l'elemento rappresentante l'insieme che contiene l'elemento e.

(4)

Esempio

n = 6

L’elemento in grassetto è il rappresentante dell’insieme

Altro esempio

• elementi: società che hanno svolto un ruolo nella storia economica;

• insiemi o rappresentanti: società esistenti ad un certo istante;

Sip Stipel Teti Fiat Lancia AlfaRomeo Ferrari Innocenti union(Sip, Teti); union(Sip, Stipel); union(Lancia, Innocenti);

{Sip, Stipel, Teti}, {Fiat}, {Lancia, Innocenti}, {Ferrari}

makeSet(Telecom); union(Telecom, Sip);

union(Fiat, Lancia); union(Fiat, Ferrari);

{Telecom, Sip, Stipel, Teti}, {Fiat, Lancia, Innocenti, Ferrari}

eccetera.

(5)

Union-find: una definizione più generale.

È conveniente fare in modo che l'operazione di unione sia, per argomenti e1 ed e2 appartenenti alla partizione, sempre definita anche se e1 ed e2 non sono i rappresentanti dei rispettivi insiemi di appartenenza. Allora:

• makeSet(E e) crea un insieme costituito dal solo elemento e;

• E union(E e1, E e2)sostituisce i due insiemi contenenti e1ed e2con la loro unione – cioè fonde i due insiemi contenenti e1 ed e2– e restituisce l'elemento rappresentante il nuovo insieme.

• E find(E e)restituisce l'elemento rappresentante l'insieme che contiene l'elemento e.

Ulteriori precisazioni sulla struttura.

• Il rappresentante di un insieme può essere scelto in modi diversi; alcune versioni richiedono che il rappresentante dell'insieme union(e1, e2)coincida sempre con quello dell'insieme che conteneva e1, altre richiedono invece che esso coincida sempre con il rappresentante dell'insieme che conteneva e2.

• L'unico vincolo che deve essere comunque rispettato è che il rappresentante di un insieme sia sempre lo stesso per tutta la vita di quell'insieme, cioè finché esso non viene fuso con un altro insieme. Cioè:

se union(e1, e2)restituisce l'elemento e_u,

allora finché l'insieme rappresentato dae_u non viene fuso con un altro per effetto di una union

tutti i successivi find(e'), con e'appartenente all'insieme rappresentato da e_u, devono restituire e_u.

(6)

Il tipo astratto union-find in Java

In Java o C# il tipo astratto union-find può essere tradotto in una definizione di interfaccia:

interface UnionFind<E> { void makeSet(E e);

E find(E e);

E union(E e1, E e2);

}

Realizzazioni della struttura union-find

Come si può realizzare tale struttura in modo efficiente ? Gli insiemi presenti nella struttura, essendo dinamicamente modificabili, è conveniente che siano rappresentati da strutture dinamiche come liste o alberi.

Nelle applicazioni della union-find gli elementi di tipo E sono di solito oggetti l'accesso ai quali fa parte del programma utlizzatore; nel realizzare la union-find non si tiene pertanto conto del tempo eventualmente necessario per posizionarsi su un oggetto-elemento, ma solo di quello occorrente per risalire da esso al rappresentante dell'insieme che lo contiene, oppure per fondere tale insieme con un altro.

(7)

Accesso agli elementi dell'universo.

Se gli elementi dell'universo sono numeri naturali consecutivi da 0a n, possiamo rappresentarli semplicemente come indici di un arraydi dimensione n, e rappresentare all'interno dell'array le strutture concatenate: cioè un nodo contenente il valore j e che punta al nodo contenente il valore kviene rappresentato ponendo il valore knell'elemento di indice j.

In una realizzazione con elementi di un tipo generico E per accedere in tempo quasi costante agli elementi possiamo usare una hash-table nella quale memorizziamo i puntatori agli oggetti-elementi.

2

4 ...

0 1 2 3 4 5 6 ...

Ad esempio, la lista: 5 22 4

viene realizzata come:

Realizzazione di UnionFind in Java

public class UnionFindImpl<E>

implements UnionFind<E> {

private static class Node<E> { final E element;

campi contenenti i necessari riferimenti ad altri nodi, a seconda del genere di struttura concatenata (next, oppure parent, ecc.);

eventuali campi contenenti altre informazioni;

Node(...) costruttori opportuni }

private HashMap<E,Node<E>> elemMap = new ...

...

HashMap<K,E>è una classe fornita dalle API Java che realizza una hash-table contenenti elementi di tipo E, e in cui lo hash è effettuato su chiavi di tipo K (vedi documentazione)

(8)

Operazione makeSet e costruttori

L'operazione makeSet(E el) deve costruire il nodo contenente l'elemento ele inserirlo nella hash-table, facendo in modo che esso sia il rappresentante dell'insieme avente come unico elemento elstesso.

Fra i costruttori della classe UnionFindImplè utile introdurre un costruttore che prenda come argomento un array oppure un insieme di elementi di tipo E; ad esempio:

public UnionFindImpl(E[] elements) { for(E elem: elements) makeSet(elem);

}

public UnionFindImpl(Set<E> setOfElems) { for(E elem: setOfElems) makeSet(elem);

}

eccetera. (nota il nuovo costrutto for-each di Java 1.5)

Tentativo di realizzazione con liste concatenate

• Si può realizzare ogni insieme con una lista concatenata.

• Se si sceglie come rappresentante l'ultimo elemento, esso può essere raggiunto dalla find semplicemente percorrendo la lista attraverso i puntatori ai successivi elementi.

• Una volta raggiunti i puntatori all'ultimo elemento di una lista e al primo dell'altra, l'unione si effettua in un passo, concatenando le liste.

• Il puntatore al primo elemento, per poter essere raggiunto, dovrebbe essere tenuto nell'ultimo elemento, come campo ulteriore dei nodi, che dopo la fusione sarebbe inutilizzato !

(9)

Tentativo di realizzazione con liste concatenate

• Oppure dovrei usare liste doppiamente concatenate (cioè nodi con successore e predecessore), con un uguale spreco di spazio, e possibile maggior consumo di tempo.

Tentativo di realizzazione con liste concatenate:

complessità

• La complessità della find sarebbe quindi, nel caso peggiore, lineare nella lunghezza della lista più lunga possibile: O(n), dove n è il numero di elementi memorizzati nella UnionFind.

• La uniondi due elementi non rappresentanti richiederebbe l'esecuzione di due find e poi il passo di concatenazione, sarebbe quindi anch'essa di complessità O(n).

(10)

• Poiché, come abbiamo visto, un nodo deve contenere due puntatori, usiamoli sempre entrambi, ma ...

• Per rendere veloce lafind, e contemporaneamente poter accedere velocemente al primo della lista, si sceglie come rappresentante il primo della lista, e in ogni nodo si

mantiene, oltre al riferimento al successivo, un riferimento al primo; così la complessità dellafinddiventa O(1).

Realizzazione con liste concatenate: una QuickFind.

• Quando si concatenano due liste tramite la union, però, non solo bisogna percorrere la prima lista fino a posizionarsi sull'ultimo elemento, ma si devono anche aggiornare tutti i puntatori della seconda lista al primo elemento della prima.

(11)

Realizzazione con liste concatenate: una QuickFind.

• Quando si concatenano due liste tramite la union, però, non solo bisogna percorrere la prima lista fino a posizionarsi sull'ultimo elemento, ma si devono anche aggiornare tutti i puntatori della seconda lista al primo elemento della prima.

Realizzazione con liste concatenate (QuickFind):

una soluzione migliore

• Mantenendo per ogni lista un oggetto che contenga i puntatori al primo e all'ultimo, nella union non si deve più percorrere la prima lista, ma bisogna comunque aggiornare tutti i nodi della seconda lista. La complessità del caso peggiore della unionrimane quindi O(n).

(12)

QuickFind con liste: riassunto

Struttura più semplice

Struttura con puntatori al primo e all'ultimo.

In ogni caso la find è veloce, la union è lenta.

Realizzazione in Java (della versione più semplice)

public class UnionFind1<E> ... { private static class Node<E> {

final E element;

Node<E> next;

Node<E> first;

Node(E element) {

this.element = element;

next = null; first = this;

} } ...

public void makeSet(E e) {

elemMap.put(e,new Node<E>(e));

}

(13)

Una realizzazione in Java (continua)

public E find(E e) {

Node<E> node = elemMap.get(e);

return node==null ? null: node.first.element;

}

public E union(E e1, E e2) {

Node<E> node1 = elemMap.get(e1);

if(e1 == null || e2 == null) return null;

Node<E> first1 = node1.first;

Node<E> curr2 = node2.first;

if(first1 != curr2) {

concatena alla prima lista la seconda;

nella seconda lista aggiorna tutti i puntatori a first }

return node1.first.element;

}

Esercizi 1 e 2

• Si completi la definizione della classe UnionFind1.

• Si scriva la definizione di una nuova classe UnionFind2che realizzi la seconda versione della struttura, in cui per ogni lista vi è un oggetto che contiene i puntatori al primo e all'ultimo elemento:

public class UnionFind2<E> ... { private static class SetHeader<E> {

Node<E> first;

Node<E> last;

}

SetHeader<E> set;

Node<E> next;

Node(...) { // costruttore ...

}

private HashMap<E,Node<E>> elemMap= new HashMap<E,Node<E>>();

private ArrayList<Set<E>> sets= new ArrayList<SetHeader<E>>();

...

(14)

Verso una soluzione con unione veloce.

• Si mantiene come rappresentante l'ultimo elemento.

• L'unione viene realizzata, invece che concatenando le due liste, facendo puntare l'ultimo elemento della seconda lista all'ultimo elemento della prima; liste rappresentanti insiemi fusi diventano così liste aventi in comune l'ultimo elemento, che è il rappresentante dell'insieme.

L'unione fra rappresentanti avviene in tempo costante (O(1)).

La soluzione QuickUnion (continua)

Una sequenza di unioni può quindi produrre una struttura ramificata:

(15)

Liste o alberi ?

• La struttura che si crea con la soluzione illustrata nella slide precedente può essere vista, invece che come insieme di liste con parti finali comuni, come una foresta di alberi realizzati tramite puntatore al genitore. Basta ruotare il disegno di 90 gradi, ma la struttura in memoria è la stessa !

Alberi

Nota Bene: Non si tratta di alberi binari, né di alberi d-ari, bensì di alberi con un numero qualunque di figli, la cui realizzazione è in generale complessa.

In questo caso, invece, essa è semplice, poiché in tali alberi interessa solo poter risalire i rami da un nodo alla radice e non viceversa: è sufficiente quindi che ogni nodo tenga il riferimento al genitore (e non ai figli).

Osserva:

Nella visione ad alberi, l'unione di due alberi consiste nel far sì che la radice di uno diventi figlia della radice dell'altro.

(16)

Realizzazione in Java

Considerando la struttura come una foresta di alberi, rideno- miniamo parent (genitore) il campo next della classeNode.

...

private Node<E> findRoot(Node<E> node) {

while(node.parent != null) node = node.parent;

return node;

}

public E find(E e) {

Node<E> node = elemMap.get(e);

if(node == null) return null;

else return findRoot(node).element;

}

Realizzazione in Java (continua)

public E union(E e1, E e2) {

if(node1==null || node2==null) return null;

Node<E> root1 = findRoot(node1);

Node<E> root2 = findRoot(node2);

...

}

(17)

Nota implementativa

I due metodi unionefind richiamano entrambi il metodo findRoot, che è la vera procedura di find: il metodo di nome findestrae semplicemente dal nodo-radice il valore del dato;

il metodo uniontrova i due nodi-radice e poi ne rende uno figlio dell'altro.

La unionè infatti costituita, in senso astratto, da due operazioni difindseguite dalla vera e propria azione di unione delle due radici, la quale richiede solo un tempo costante.

Esercizio 3 (facile)

Si completi la definizione del metodo union, e più in generale si completi l'intera realizzazione (classe UnionFind3).

Riassunto complessità della soluzione

• find: O(n);

• unionfra rappresentanti: O(1);

• unionfra elementi generici: O(n);

Quest'ultima soluzione è quindi meno efficiente di quella precedente, soprattutto per quanto riguarda la find.

Essa può però essere migliorata: poiché la union e la find risalgono l'albero da un nodo fino alla radice, bisogna cercare di mantenere il più possibile piccola l'altezza degli alberi.

A tal fine sono possibili diverse strategie.

(18)

Miglioramento: unione per dimensione (union by size)

L'unione viene effettuata scegliendo sempre come radice del nuovo insieme quella dell'insieme di cardinalità maggiore;

cioè la radice dell'albero col minor numero di nodi diventa nuovo figlio della radice di quello più grande.

Vantaggio intuitivo: ad ogni unione, viene aumentata la profondità dei nodi nell'albero "più piccolo".

Union-find con unione per dimensione: analisi (1)

È banale dimostrare induttiv. che il livello di ogni nodo è al più logaritmico nel numero di nodi dell'albero cui appartiene:

• Il livello k di ogni elemento è inizialmente 0, in un albero T di cardinalità 1 (è il nodo creato dalla makeSet); si ha quindi banalmente |T| = 2^k (indicando con |T| la cardinalità di T).

• Il livello k di un nodo aumenta soltanto quando l'albero T in cui esso si trova viene fuso con un albero avente un numero di nodi maggiore.

• In tal caso il suo livello h aumenta di 1, mentre il numero di nodi del nuovo albero di appartenenza è almeno doppio di quello dell'albero precedente;

cioèk aumenta di 1, |T| raddoppia: k' = k+1, |T'| ≥ 2|T|.

• Se per ip. induttiva si ha |T| ≥ 2^k, allora |T'| ≥ 2|T| ≥ 2^k+1= 2^k'

(19)

Union-find con unione per dimensione: analisi (2) Nota sulla dimostrazione

La facile dimostrazione descritta nella slide precedente è una dimostrazione per induzione sul numero di operazioni effettuate su una struttura UnionFind.

Il caso base è infatti:

Subito dopo la creazione del nodo (makeset), quindi dopo 0 operazioni di union o find, la proprietà |T| ≥ 2^kè banalmente soddisfatta con |T| = 1 e k = 0.

Nel passo induttivo si assume che la proprietà valga per un certo nodo dopo un numero non specificato di operazioni, e si dimostra che essa continua a valere anche dopo l'esecuzione di una ulteriore operazione. Naturalmente se l'operazione è una find gli alberi non vengono modificati, e in tal caso quindi è ovvio che la proprietà continua a valere. L'unico caso non vuotamente banale è quello in cui il livello del nodo aumenta:

appunto il caso considerato nella slide precedente.

Union-find con unione per dimensione: analisi (3).

Quindi per ogni elemento elsi ha, ad ogni istante:

k_el≤log₂ |T_el|

dove k_el è il livello del nodo contenente el,

T_elè l'albero (cioè l'insieme) cui esso appartiene.

(Nota: una conseguenza è che anche l'altezza h^T di un albero Tè al più logaritmica nel numero dei nodi di T: h_T≤log₂ |T| ) Se n è il numero di elementi appartenenti all'universo della partizione, le complessità del caso peggiore sono pertanto:

• find: O(log n)

• union: O(log n)

• union fra

rappresentanti: O(1)

(20)

Unione per dimensione: realizzazione in Java

La realizzazione in Java è semplice: basta aggiungere nei nodi un campo che contenga la dimensione dell'albero di cui il nodo è radice, nell'unione tenerne conto e aggiornarlo poi con una semplice istruzione di somma quando l'albero viene unito con un albero più piccolo.

Node<E> parent;

int size;

... costruttore }

Esercizio 4 (facile)

Si completi la realizzazione in Java della classe UnionFind4 con unione per dimensione, e la si provi (per mezzo di un main in una classe di prova).

Si noti che, rispetto alla versione precedente UnionFind3, nella realizzazione delle operazioni occorre cambiare soltanto il metodo union; i metodi findRoot e findrestano invariati.

(21)

Miglioramento alternativo: unione per altezza

Strategia alternativa a quella dell'unione per dimensione, ma ad essa analoga e dagli effetti simili.

L'unione viene effettuata scegliendo sempre come radice del nuovo albero quella dell'albero di altezza maggiore; cioè la radice dell'albero meno alto diventa nuovo figlio della radice di quello più alto.

UnionFind con unione per altezza: analisi (1)

Si dimostra per induzione che l'altezza di ogni albero è al più logaritmica rispetto al numero dei nodi dell'albero:

h(T) ≤ log₂|T| cioè |T| ≥ 2^h(T) Base.

Se l'albero ha un solo nodo la proprietà vale banalmente.

Passo Induttivo.

Intuitivamente:

Quando si uniscono due alberi di altezze diverse, tali altezze non cambiano; in particolare, l'albero più alto non varia la propria altezza ma aumenta il proprio numero di nodi (quindi, se aveva almeno 2^hnodi prima, sicuramente li ha anche dopo);

Quando si uniscono due alberi della stessa altezza h, uno dei due aumenta la propria altezza di 1, ma acquista un numero di nodi almeno uguale (per ipotesi induttiva) a 2^h.

(22)

Dimostrazione dettagliata del passo.

Ip. Induttiva.La proprietà vale per i due alberi S e T:

|S| ≥ 2^h(S) |T| ≥ 2^h(T)

Tesi Induttiva. La proprietà vale dopo l'esecuzione di una operazione di unione: |S⋃⋃⋃⋃T| ≥ 2^h(S⋃^⋃⋃⋃T)

Dimostrazione.

caso 1:Se Thanno altezze diverse. Sia ad es. S il più alto, cioè h(S) > h(T); si ha allora h(S⋃⋃⋃⋃T) = h(S);

quindi |S⋃⋃⋃⋃T| = |S| + |T| > |S| = 2^h(S)= 2^h(S⋃^⋃⋃⋃T)

caso 2: S e T hanno la stessa altezza: h(S) = h(T) = h.

Allora h(S⋃⋃⋃⋃T) = h+1;

quindi|S⋃⋃⋃⋃T| = |S| + |T| > 2^h(S)+ 2^h(T)= 2·2^h= 2^h+1= 2^h(S⋃^⋃⋃⋃T)

UnionFind con unione per altezza: analisi (2)

Quindi per ogni elementoelsi ha ad ogni istante:

k_el≤h(T_el) ≤ log₂ |T_el|

con k_ellivello del nodo el, T_ell'albero di appartenenza (esattamente come nella union by size).

Le operazioni nella union-find con unione per rango hanno quindi le stesse complessità che nella union-find con unione per dimensione:

• find e union O(log n)

• union fra

rappresentanti: O(1) Ricorda:

nè il numero totale di elementi presenti nella partizione.

(23)

Realizzazione in Java

• Occorre introdurre nella classe Node un campo heightche tiene l'altezza dell'albero di cui il nodo è radice.

• Tale altezza sarà inizialmente 0, alla creazione del nodo.

• Essa viene poi incrementata di 1 solo quando il nodo diventa la radice di un nuovo albero ottenuto per unione di due alberi di uguale altezza:

height = h height = h height = h+1

Esempio

A height=2 B height=2

A

height=3 B height=2

height++

(24)

Esercizio 5

Si realizzi la classe UnionFind5con unione per altezza.

Si introduca nella classe un metodo ausiliario di debugging int livello(E e)che restituisca il livello del nodo contenente l'elemento e.

Si realizzi una classe utilizzatrice contenente un main che provi la UnionFind; eseguendo tale main si verifichi sperimen- talmente a quale livello si vengono a trovare i vari elementi.

Ulteriore miglioramento: compressione dei cammini.

La union-find con unione per dimensione o per altezza può essere migliorata facendo in modo che la finddurante la sua esecuzione tenda a diminuire l'altezza dell'albero, così da rendere più veloci le operazioni successive.

Varie tecniche possibili, consideriamone una:

• la find rende figli della radice tutti i nodi che incontra nel suo percorso di risalita dal nodo alla radice.

A

B C

B

A C

(25)

Realizzazione della find con compressione (1)

• iterativa: dopo aver trovato la radice, si ripercorre il cammino dal nodo alla radice aggiornando in ogni nodo del cammino il puntatore al genitore;

• ricorsiva: l'aggiornamento del genitore viene effettuato al ritorno dalla chiamata ricorsiva; in questo modo il cammino viene formalmente percorso una volta sola (in realtà una specie di "secondo percorso" è operata automaticamente dalla ricorsione, nella risalita con assegnamenti);

• nota bene: in entrambi i casi il numero di passi della find modificata è uguale a quello della find originale moltiplicato per un fattore costante: la complessità del caso peggiore è quindi la stessa (logaritmica).

• un caso peggiore può verificarsi per la find quando essa viene eseguita per la prima volta dopo una sequenza di

unioni che abbiano generato un albero della massima altezza possibile.

Realizzazione della find con compressione (2)

• Come abbiamo visto, la unionè costituita in senso astratto da due operazioni di find seguite dall'unione vera e propria.

• Introducendo la compressione nella find, la introduciamo quindi automaticamente anche nella union(se l'implementa- zione è corretta).

• A tal fine basta infatti che la compressione sia realizzata nel metodo findRoot(che è la vera procedura di find

invocata sia dal metodo findche dal metodo union).

• Rispetto alle implementazioni precedenti bisogna quindi modificare soltanto il metodo findRoot.

(26)

Compressione: realizzazione iterativa

• dopo aver trovato la radice, si ripercorre il cammino

dal nodo alla radice, aggiornando il puntatore a genitore di ogni nodo del cammino:

private Node<E> findRoot(Node<E> node) { Node<E> root = node;

while(root.parent != null) root = root.parent;

while(node.parent != null) {

Node<E> oldParent = node.parent;

node.parent = root;

node = oldParent;

}

return root;

}

Compressione: realizzazione ricorsiva

L'aggiornamento del genitore viene effettuato al ritorno dalla chiamata ricorsiva:

private Node<E> findRoot(Node<E> node) { if(node.parent == null) return node;

else {

node.parent = findRoot(node.parent);

return node.parent;

} }

Attenzione al significato dell'istruzione in rosso: si ricordi che in un'assegnazione si valuta/esegue prima la parte destra, e poi si deposita il risultato nella locazione a sinistra:

l'istruzione suddetta trova quindi la radice del vecchio genitore, e la fa diventare nuovo genitore; per la ricorsione, nel trovare la radice aggiorna anche tutti i nodi del cammino.

(27)

Union by size + path compression:

realizzazione tramite array

• L'universo degli elementi sia semplicemente l'insieme degli n interi da 0a n-1.

• La foresta è allora realizzabile come un semplice array, e ogni nodo è rappresentato da un indice dell'array.

• Il contenuto di ogni elemento dell'array rappresenta i due campi parent e size "in sovrapposizione"; cioè:

• se l'elemento dell'array rappresenta un nodo che non è la radice di un insieme, il suo contenuto è il genitore;

• se l'elemento dell'array rappresenta un nodo-radice, il suo contenuto è l'opposto della dimensione dell'albero (realizzazione possibile perché gli elementi dell'universo, essendo indici, sono numeri non negativi).

Esempio

La struttura union-find costituita da:

4 5

12 10

11 2

7 3

8

9 0

1 6

è rappresentata dall'array:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

13 14

1 -4 -8 2 5 2 1 3 -1 1 5 2 10 14 -2

(28)

Realizzazione Java

public class UnionFind {

private int[] parentOrNSize; // opposto del size public UnionFindInt(int n) {

parentOrNSize = new int[n];

for(int i = 0; i < n; i++) parentOrNSize[i] = -1;

}

public int find(int j) {

if(parentOrNSize[j] < 0) return j; //radice else {

parentOrNSize[j]= find(parentOrNSize[j]);

return parentOrNSize[j];

} }

Esercizio 6

• Si definisca una versione iterativa della find.

• Si completi la definizione della classe UnionFind di interi realizzata come array, e si definisca un main di prova.

(29)

Complessità ammortizzata

• Il vantaggio della compressione dei cammini si ha quando si effettua una sequenza di operazioni; esso non può quindi venire misurato dalla complessità della singola operazione.

• Bisogna prendere in considerazione una sequenza di m operazioni, calcolare il tempo di calcolo (nel caso peggiore) della computazione costituita dall'intera sequenza, e dividere poi il risultato per il numero m di operazioni.

• La complessità risultante è la complessità ammortizzata (del caso peggiore) della singola operazione.

• Esempio di costo ammortizzato in conti economici: il costo ammortizzato annuale di un'auto usata per N anni è dato dalla somma del costo di acquisto e del costo totale negli N anni di benzina, olio, riparazioni, ecc. , divisa per il numero di anni.

Complessità ammortizzata: definizione.

• Il tempo di calcolo impiegato da un algoritmo che realizzi un'operazione su una struttura-dati può dipendere, oltre che dalla dimensione n della struttura, dalle operazioni (dello stesso o di altro genere) effettuate prima.

• Ad esempio, una find con compressione su un nodo di livello h compie h passi; le successive find sui nodi "compressi" rag- giungono la radice in un passo solo.

• La complessità ammortizzata (del caso peggiore)

di un'operazione OP su una struttura di dimensione n è:

T(n) = T_worst(sequenza di m operazioni OP, n)/m

• Attenzione! Non confondere la complessità ammortizzata con la complessità del caso medio:

• caso medio: si fa la media(eventualmente pesata con una certa distribuzione di probabilità) su tutti i casi possibili;

• ammortizzata: si fa la media su una sequenza di operazioni

(30)

Union-find con unione per dimensione compressione dei cammini +

• Con la compressione dei cammini, numero dei nodi e altezza dei sottoalberi di un albero-insieme possono variare.

• La compressione non fa variare il numero dei nodi di un intero albero-insieme, finché ad esso non viene unito un altro albero.

• Union-find con unione per dimensione + compressione:

non è quindi necessario, nella compressione, aggiornare i campi size dei nodi coinvolti: infatti gli unici nodi che

dovrebbero cambiarlo sono alcuni nodi non-radici-di-insiemi, per i quali il size non ha più importanza.

Union-find con unione per altezza (rango) compressione dei cammini +

• La compressione può cambiare l'altezza anche di un intero albero-insieme. Aggiornare il campo heightsarebbe però, oltre che dispendioso, inutile: infatti pur in assenza di tale aggiornamento la complessità delle operazioni rimane, come abbiamo visto, O(log n) nel caso peggiore, mentre la

complessità ammortizzata diventa "quasi" O(1).

• Intuitivamente, ciò dipende dal fatto che la compressione può diminuire l'altezza ma contemporaneamente aumenta il numero dei figli della radice dell'albero.

• Il campo-altezza di ogni nodo A, non essendo aggiornato nella compressione, non è più in generale l'altezza effettiva dell'albero di radice A, ma solo un suo limite superiore. Ad esso conviene perciò dare un nome diverso: rango.

(si ha dunque rango(A) ≥ altezza dell'albero di radice A)

(31)

Analisi ammortizzata della union-find con unione per rango e compressione dei cammini.

• Poiché una unionè, dal punto di vista temporale, equivalente a due find, ci limitiamo a considerare una sequenza di m operazioni di find (di cui un numero imprecisato eseguite all'interno di union) su una struttura union-find contenente globalmente nelementi.

• Equivalentemente, possiamo considerare una sequenza di m operazioni di find e di noperazioni di makeSet a partire da una struttura union-find vuota.

• Calcoliamo il tempo T(m, n) impiegato nel caso peggiore per eseguire la sequenza di operazioni; dividendo poi per m avremo la complessità ammortizzata dell'operazione di find (o union), dividendo per m+n avremo quella dell'operazione generica (union, find o makeSet).

Analisi ammortizzata della union-find con unione per rango e compressione dei cammini.

Alcune definizioni matematiche necessarie per esprimere il risultato.

(32)

Una funzione un po'particolare: la "torre di due".

Altra notazione per la torre.

Per indicare la funzione torre(n)è usata anche la notazione

2⇈ ⇈ ⇈n ⇈

inventata da Knuth, visivamente abbastanza intuitiva.

Tale notazione è ovviamente più generale della precedente, poiché permette di definire la funzione in due variabili

x⇈ ⇈ ⇈n ⇈

.

(33)

La "torre di due": osservazioni

La funzione torre cresce con una rapidità "spaventosa", molto maggiore dell'esponenziale: il valore di torre(5), 2⁶⁵⁵³⁶, è infatti già un numero inconcepibile, privo di qualunque significato fisico:

2⁶⁵⁵³⁶> 2⁶⁰⁰⁰⁰= 2^10•6000= (10³)⁶⁰⁰⁰ = 10¹⁸⁰⁰⁰

= 1 seguito da 18000 zeri ...

Il numero stimato di particelle elementari dell'universo è 10⁸⁰ A tutti gli effetti pratici si può quindi considerare

torre(k) = ∞ per k ≥ 5

La funzione inversa di torre.

Consideriamo la funzione inversa di torre, cioè:

torre^-1(n) = k tale che torre(k) = n Ovviamente basta leggere al contrario la tabella di slide 47:

torre^-1(1) = 0 torre^-1(2) = 1 torre^-1(4) = 2 torre^-1(16) = 3

torre^-1(65536) = 4 ...

Estendiamo la definizione della funzione inversa in modo naturale su tutti gl'interi positivi. Chiamiamo log* nla funzione così definita.

(34)

La funzione log*

log* 1 = 0 log* 2 = 1 log* 3 = 2 log* 4 = 2 log* 5 = 3 log* 6 = 3 ...

log* 15 = 3 log* 16 = 3 log* 17 = 4 log* 18 = 4 ...

log* 65536 = 4 log* 65537 = 5 ...

La funzione log*

log* 1 = 0 log* 2 = 1 log* 3 = 2 log* 4 = 2 log* 5 = 3 log* 6 = 3 ...

log* 15 = 3 log* 16 = 3 log* 17 = 4 log* 18 = 4 ...

log* 65536 = 4 log* 65537 = 5 ...

(35)

Definizione della funzione log*

Poiché la funzione torretorretorre cresce spaventosamente in fretta, la torre sua inversa cresce "spaventosamente piano": per n > 65537 diventa di fatto costante, uguale a 5 per ogni n "sensato".

Analisi ammortizzata di union-find con compressione dei cammini: il risultato.

Si dimostra⁽¹⁾che il tempo di calcolo T(m, n) occorrente per eseguire moperazioni di find e n operazioni di makeSet(a partire da una struttura vuota) è:

T(m,n) = O((m+n)log* n)

La complessità ammortizzata di ognuna delle m+n operazioni è quindi O(log* n): ma essendo log* n a tutti gli effetti pratici una costante per n > 65537, si ha di fatto:

complessità ammortizzata di un'operazione = O(1) Cioè il tempo ammortizzato impiegato da ogni operazione non supera, in pratica, un (piccolo) valore costante.

(1) Dimostrazione difficile: vedi slides successive..

(36)

Soluzioni efficienti di tipo QuickUnion: riassunto.

• Ogni insieme è realizzato come un albero.

• La struttura-dati union-find è una foresta (cioè un insieme di alberi).

• Ogni elemento è inizialmente radice del proprio albero (costituito solo da se stesso).

• Nodi con riferimento solo al genitore, NON ai figli.

• L'identità di ogni insieme, cioè il suo rappresentante, è contenuta nella radice.

• union: fa diventare la radice di un insieme figlia della radice dell'altro: O(1) per rappresentanti;

• find: risale dall'elemento alla radice seguendo in ogni

successivo nodo il puntatore al genitore; O(n)nel caso peggiore, con nnumero totale dei nodi della struttura.

Soluzioni di tipo QuickUnion: riassunto (2)

• costo della find: lineare nell'altezza dell'albero; quindi nel caso peggiore O(n)con n numero totale degli elementi presenti nella struttura (la partizione è ridotta ad un unico albero, e l'albero è degenere) ;

per migliorare:

• mantenere gli alberi abbastanza "bilanciati";

• anzi, mantenere bassa l'altezza degli alberi

(ricorda che il numero di figli può essere grande quanto si vuole, quindi l'altezza non è limitata inferiormente da log n)

(37)

Soluzioni di tipo quick-union: riassunto (3)

soluzioni:

• in ogni radice si memorizza:

• la dimensione (numero di nodi) dell'albero (union by size);

oppure

• una delimitazione superiore dell'altezza (rango) dell'albero (union by rank);

• union: fa diventare la radice dell'albero più piccolo figlia della radice dell'albero più grande (union by size);

oppure

fa diventare la radice dell'albero di rango minore figlia della radice di rango maggiore (union by rank);

• find: risale dall'elemento alla radice, e fa diventare figli della radice tutti i nodi del cammino (path compression).

Soluzioni di tipo quick-union: riassunto (4)

• realizzazione con union-by-size o union-by-heightda sole:

la complessità delle operazioni di union e find è nel caso peggiore O(log n), dove n è il numero di elementi della struttura (o, equivalentemente, il numero di makeSet effettuate a partire da una struttura vuota);

• union-by-size o union-by-height + path compression:

la complessità delle operazioni di union e find per il caso peggiore è ancora O(log n), ma la complessità ammortizzata del caso peggiore è quasi-costante; cioè è O(1)fisicamente, benché non matematicamente;

• complessità ammortizzata: complessità di una sequenza di operazioni effettuate una dopo l'altra su di una stessa struttura, divisa per il numero di operazioni.

(38)

Dimostrazione della delimitazione T(m,n) = === O((m+n)log*n)

Descriviamo dapprima lo schema generale della dimostrazione, poi ne presentiamo lo svolgimento (abbastanza) dettagliato.

Si consideri dunque l'intera computazione costituita da una sequenza di m+n operazioni: m finded n makeSet(in un ordine qualsiasi).

Idea generale

• Il tempo di calcolo delle m operazioni di findè proporzionale al numero di passi di risalita da un nodo al suo genitore compiuti globalmente durante la computazione (invece del numero di archi percorsi, si potrebbe equivalentemente contare il numero di nodi visitati: il costo risultante sarebbe lo stesso, a meno di fattori costanti).

• Per contare tale numero, invece di contare separatamente il numero di passi eseguiti da ciascuna find, consideriamo contemporaneamente tutti i passi eseguiti durante la computazione, e li classifichiamo in due generi secondo un criterio ad hoc molto particolare; contiamo poi, per ognuno dei due generi, i passi di tal genere.

• Facciamo la somma dei due totali.

(39)

Più precisamente:

• Osserviamo che, in ogni albero della struttura, lungo ogni cammino da un nodo alla radice i ranghi dei nodi sono in ordine strettamente crescente; ogni singolo passo di find risale quindi sempre da un nodo di rango r ad un nodo di rango >>>> r.

• Ripartiamo l'insieme di tutti i possibili valori dei ranghi degli n nodi in h blocchi distinti, con h = log* n.

• Chiamiamo poi passo esterno un passo di risalita in cui il genitore sia una radice al top level (cioè sia il rappresentante di un insieme) oppure abbia un rango appartenente ad un blocco diverso da quello del figlio.

• Chiamiamo passo internoun passo di risalita che non sia esterno, cioè un passo da un figlio a un genitore nello stesso blocco, e in cui il genitore non sia una radice al top level.

Idea generale (fine).

• Un cammino da un nodo alla radice, essendo un cammino che percorre una sequenza di nodi di rango strettamente

crescente, può al più attraversare tutti i log* n blocchi, ed eseguire quindi log* n passi esterni. Per m operazioni di find il numero totale di passi esterni è quindi m log*n.

• Grazie alla compressione, il numero dei passi interni di ogni blocco non dipende dal numero mdelle find (e questo è il punto cruciale), ma è semplicemente uguale al numero totale n dei nodi. Ciò dipende dal fatto che un nodo, ogni volta che viene attraversato, assume poi un nuovo genitore di rango maggiore: quindi dopo un certo numero di attraversamenti di uno stesso nodo (compiute ovviamente da find diverse) l'arco da questo al genitore diventa un arco "inter-blocchi" e quindi poi non sarà più contato fra i passi interni. Il numero totale dei passi interni in tutti i blocchi è quindi n log* n.

(40)

Traccia dettagliata della dimostrazione: preliminari

Per comodità, chiamiamo nodi leaderi nodi che sono radici di alberi al top level, cioè che sono rappresentanti di insiemi.

Diciamo inoltre che un nodo viene promossoquando il suo rango viene incrementato di 1.

• Ogni nodo viene creato (da una makeSet) con rango 0;

• viene poi promosso ogni volta che una union "mette sotto di lui" (cioè fa puntare ad esso) un altro leader di rango uguale (che perde la leadership);

• dall'eventuale istante in cui il nodo cessa di essere un leader (quando una union lo "mette sotto" un altro leader), il suo rango non cambia più (perché non potrà ridiventare leader, e la compressione non modifica i ranghi).

.

Lemma 1

Ogni nodo della struttura ha rango strettamente maggiore del rango di ciascuno dei suoi figli.

Dimostrazione per induzione sul numero di operazioni effettuate, cioè sul numero degli "istanti" del calcolo.

Base:Nodo senza figli. Vacuamente vero.

Passo.

Ip. Induttiva:La proprietà vale per ogni nodo della struttura.

Tesi Ind.:Dopo un'altra operazione la proprietà vale ancora.

Dimostr. del passo.

Un nuovo arco genitore-figlio si può creare solo a causa di una union oppure di una compressione:

• union: se r è, prima dell'unione, il rango dei due leader coinvolti, dopo l'unione il genitore ha rango r+1e il nuovo figlio ha rango r;

• compressione: trasforma un discendente non immediato di A in un figlio di A; ma per ip. induttiva e per transitività

(41)

Lemma 1: Corollario.

Osserva che, in base al lemma 1:

seguendo il cammino da un nodo qualsiasi verso una radice, i ranghi dei nodi sono strettamente crescenti

(come nella struttura a heap usata per le code a priorità).

Lemmi 2 e 3

• Lemma 2. Ogni leader di rango rè radice di un albero contenente almeno 2^rnodi, perché:

• ciò era vero in assenza di compressione;

• d'altra parte la compressione non toglie nodi al leader (cioè all'albero di cui il leader è radice).

Si noti che invece questa proprietà non vale per un nodo che non sia più leader (perché la compressione gli può togliere dei nodi).

• Lemma 3. Per ogni rango r il numero di nodi distinti che nel corso della sequenza di operazioni possono trovarsi ad avere (anche solo per un certo tempo) rango r, è ≤ n/2^r, dove n è il numero totale di nodi creati.

Nota

Il lemma 3 giuoca un ruolo fondamentale nella dimostrazione.

(42)

Dimostrazione del Lemma 3 usando il Lemma 2

• In base al corollario del Lemma 1, due nodi dello stesso rango rnon possono essere l'uno il discendente dell'altro;

• quindi i due sottoalberi di cui essi sono radici devono essere disgiunti;

• quindi ad ogni istante vi possono essere al più n/2^rnodi di rango r;

• un sottoalbero di un nodo di rango rnon può mai diventare sottoalbero di un altro nodo di rango ≤r(per le proprietà dell'unione);

• poiché i nodi in tutto sono n, durante l'intera computazione non più di n/2^rnodi possono essere promossi al rango r.

Dimostrazione diretta del Lemma 3 (per induzione su r).

Base: r = 0.

Ovvio: un nodo assume rango 0 solo quando viene creato, ma vengono creati nnodi, quindi il numero di nodi di rango 0 è n; ma appunto n/2⁰= n.

Passo

Ipotesi Iduttiva :Non più di n/2^r-1nodi distinti si trovano ad avere (per un certo tempo) rango r-1.

Tesi Induttiva:Non più di n/2^rnodi distinti si trovano ad avere rango r.

Dimostrazione.

Un nodo può assumere rango rsolo quando, essendo un leader di rango r-1, viene unito (restando leader) con un altro leader di rango r-1.

Dopo l'unione il nodo promosso al rango rnon potrà più avere rango r-1, mentre l'altro, pur mantenendo rango r-1, non è più leader.

Ogni promozione al rango rconsuma quindi 2leader di rango r-1; quindi si possono avere al più M/2promozioni ad r, dove Mè il numero di nodi che, durante la sequenza di operazioni, possono assumere rangor-1.

Ma per ipotesi induttiva tale numero Mnon supera n/2^r-1.

Vi possono perciò essere al più (n/2^r-1)/2 = n/2^rpromozioni al rango r.

(43)

Ingrediente fondamentale della dimostrazione.

Partizioniamo i valori dei ranghi in insiemi disgiunti che chiamiamo blocchi, in modo che l'i-esimo bloccocontenga torre(i)valori; precisamente:

blocco₀= {0,1};

blocco₁ = {2};

blocco₂= {3,4};

blocco₃= {5,6, ..., 16}

blocco₄= {17, 18, ... ... ... , 65536}

...

Cioè: blocco_i= {r | k+1 ≤ r ≤ 2^k} dove 2^k= torre(i);

quindi l'indice idel blocco è log*di ogni rango del blocco:

cioè r ∈ blocco_i se e solo se i = log* r.

Blocchi di ranghi, blocchi di nodi.

• Consideriamo l'insieme dei nodi partizionato in blocchi corrispondenti ai blocchi dei rispettivi ranghi; cioè diciamo che un nodo appartiene al blocco b-esimose il suo rango appartiene al blocco di indice b.

• Useremo l'espressione abbreviata "il blocco b"intendendo

"il blocco di indice b" (di ranghi o di nodi, a seconda del contesto).

• Il blocco bcui appartiene il nodo X, indicato con bloc(X), è quindi: bloc(X) = log*(range(X))

• Ovviamente, si ha allora che il nodo X appartiene al blocco b se e solo se bloc(X) = b.

(44)

Schema dei calcoli effettuati nei prossimi lucidi.

Preliminari.

Classificazione dei passi di risalita della find.

• Passo interno: passo figlio-genitore all'interno di un blocco;

• ad ogni passo interno, un nodo acquista un genitore di rango maggiore;

• Passo esterno: passo figlio-genitore da un blocco ad un altro;

(definizioni più precise verranno date in seguito)

Numero di ranghi per blocco.

In base alla definizione di blocco, in un blocco bci sono non più di torre(b)ranghi distinti.

Schema dei calcoli effettuati nei prossimi lucidi

• Quanti sono i blocchi ? log* n

• Quanti sono i passi esternidi mfind? m log* n

• Quanti nodi ci sono in un blocco b? n/torre(b)

• Quanti ranghi ci sono in un blocco b? torre(b)

• Quanti passi interni per nodo in un blocco b? torre(b)

• perché sono tanti quanti i ranghi di cui può salire il genitore nel blocco

• Quanti passi interni possibili in ogni blocco b? n

• perché sono numNodi • numPassiPerNodo = (n/torre(b)) • torre(b)

• Quanti passi interni in tutto ci sono ? n log* n

• Quanti passi ci sono in tutto per mfind? (m+n) log* n

(45)

Quanti sono i blocchi ?

• In assenza di compressione sappiamo che l'altezza degli alberi è ≤log n; con la compressione lo stesso limite deve quindi valere per il rango;

• il massimo valore del rango quindi non supera log n;

• l'indice del blocco "più alto" sarà quindi b = log*(log n)

• ma si ha:

b = log*(log n) ⇒ torre(b) = log n ⇒ 2^torre(b)= n

⇒ torre(b+1) = n ⇒ b+1 = log*n ⇒ b = log*n – 1

• quindi vi sonolog* n blocchi:

blocco_o, blocco₁, ..., blocco_{log*n – 1}

Quanti nodi ci sono in un blocco ?

Abbiamo definito:

blocco_b= {r | k+1 ≤ r ≤ 2^k} dove 2^k= torre(b);

Per il Lemma 3, per ogni range rci sono al più n/2^rnodi che possono avere (almeno per un certo tempo) range r.

Il numero di nodi appartenenti al blocco (di indice) b è allora:

∑

∈

≤

bloccob

r 2r

n

∑

+

=

2k

1 k

r 2r

n

∑

−

=

k 2

1 i k

k

2i 1 2

n

=

≤

k

2 n

torre(b) n

poiché, per qualsiasi h:

1

h 1 i 2i

1

≤

∑

=

num_nodi(b)

(46)

Passi (archi) da un nodo al genitore: classificazione

• passo interno:un passo di risalita da un figlio a un genitore dello stesso blocco, e in cui il genitore non sia un leader;

• passo esterno:un passo non interno, cioè in cui il genitore sia un leader oppure sia di un blocco diverso da quello del figlio ( bloc(A) ≠≠≠≠ bloc(genitore di A))

Ovviamente il tempo totale di esecuzione della sequenza è dato dal numero totale di passi:

T = num_passi_interni + num_passi_esterni.

Quanti sono i passi esterni compiuti in totale ?

Quanti sono i passi esterni compiuti nel corso di tutta la sequenza di operazioni ?

• ognifindpercorre un cammino che, per il lemma 1, è una sequenza di nodi di rango strettamente crescente;

• ognifind, quindi, attraversa nel caso peggiore tutti i

blocchi fino ad un leader, compiendo così un numero di passi esterni uguale al numero dei blocchi;

• il numero totale di passi esterni compiuti durante tutta la sequenza di mfind è quindi:

num_passi_esterni ≤≤≤≤m∙num_di_blocchi cioè:

num_passi_esterni ≤≤≤≤m∙log* n

(47)

Passi interni

• Premessa: ogni volta che si esegue un passo di risalita da un nodo A al suo genitore gen(A), se A non è figlio di un leader gli viene poi assegnato un nuovo genitore di rango maggiore (il leader dell'albero in cui si trova), mentre il rango di A non cambia. Quindi:

• Ogni volta che viene eseguito un passo interno da A a gen(A), la differenza di rango fra A e quello del suo (ogni volta diverso) genitore aumenta.

• Pertanto, dopo un numero sufficientemente alto di passi interni da A al suo genitore, il nodo A si troverà ad avere un genitore appartenente a un blocco superiore al proprio, o un genitore leader: i successivi passi da Aa gen(A)non saranno quindi più passi interni, e sono quindi inclusi nel conto dei passi esterni.

Quanti sono i passi interni per ogni blocco ?

Dato un nodo X appartenente al blocco b, qual è

un limite superiore per il numero di passi interni X→→→→gen(X)?

• Evidentemente è il massimo numero di valori distinti di rango appartenenti al blocco.

• Ma il blocco di indice bè:

blocco_b= {r | k+1 ≤ r ≤ 2^k} dove 2^k= torre(b);

il numero di ranghi in esso contenuti è quindi ≤torre(b).

• Dunque per un nodo Xappartenente al blocco b si ha:

num_passi_nodo(X) ≤ torre(b)

Allora il numero di passi interni del blocco bè semplicemente:

num_passi_blocco(b) ≤ torre(b) ∙ num_nodi(b) cioè num_passi_blocco(b) ≤ torre(b) ∙ n/torre(b)

num_passi_blocco(b) ≤ n

(48)

Quanti sono i passi interni compiuti in totale ?

Quanti sono i passi interni compiuti nel corso di tutta la sequenza di operazioni ?

Poiché il numero di passi interni per blocco non dipende dal blocco ma è semplicemente n, si ha:

num_passi_interni ≤≤≤≤n∙num_di_blocchi cioè

num_passi_interni ≤ n log* n

Quanti sono i passi generici compiuti in totale ?

num_totale_passi ≤ m log* n + n log* n =(m+n) log* n quindi

T(m, n) = === O( (m+n) log* n)

Epilogo

• In realtà, la delimitazione (m+n) log* nnon è stretta, cioè non è T(m, n) =

Θ Θ Θ Θ

(m+n) log* n.

• Si è infatti dimostrato (nel 1984) che T(m, n)ammette una delimitazione superiore più bassa:

O(n + mαααα(m,n))

dove αααα(m,n)è la cosiddetta funzione di Ackermann inversa, che cresce ancor più lentamente di log* n;

per tutti gli m ed n fisicamente sensati si ha infatti:

αα

αα(m,n) ≤≤≤≤4 (contro log* n ≤≤≤≤ 5)

• Si conferma quindi che la complessità ammortizzata di una singola operazione si può considerare costante, cioè O(1).