Strutture Dati e Algoritmi: Appunti Della Lezione Per
Strutture Dati e Algoritmi: Appunti Della Lezione Per
Scuola di Informatica
Università di Birmingham
Birmingham, Regno Unito
c
Scuola di Informatica, Università di Birmingham, Regno Unito, 2017
1
Contenuti
1 Introduzione 5
1.1 Sito web del modulo, libri di testo e risorse web . . . . . . . . . 5 . . . . .
1.2 Algoritmi in contrapposizione ai programmi . . . . . . . . . . . . . . .6 . . . . .
1.3 Domande fondamentali sugli algoritmi . . . . . . . . . . . . . . . . 6. . . . .
1.4 Strutture dati, tipi di dati astratti, pattern di design . . . . . . . . 7 . . . . .
1.5 Panoramica 8
4 Ricerca 21
4.1 Requisiti per la ricerca . . . . . . . . . . . . . . . . . . . 21
. . . . . .
4.2 Specificazione del problema di ricerca 22
4.3 Un algoritmo semplice: Ricerca Lineare . . . . . . . . . . . . . . 22. . . . . .
4.4 Un algoritmo più efficiente: Ricerca Binaria . . . . . . . . . . . . . . . . . .
23
5 Efficienza e Complessità 25
5.1 Complessità temporale versus complessità spaziale 25
5.2 Complessità peggiore rispetto a quella media . . . . . . . . . . . . . . . . 25. . . . . .
5.3 Misure concrete per le prestazioni . . . . . . . . . . . . . . . 26. . . . .
5.4 Notazione Big-O per la classe di complessità . . . . . . . . . . . . . 26. . . . . .
5.5 Definizione formale delle classi di complessità . . . . . . . . . . . . .29 . . . . . .
6Alberi 31
6.1 Specifica generale degli alberi. 31
6.2 Quad-tree . . . . . . . . . . . . . . . . . . . . . . . . . 32. . . . . .
6.3 Alberi binari . . . . . . . . . . . . . . . . . . . . . . . 33
. . . . . .
2
6.4 Operazioni primitive sugli alberi binari . . . . . . . . . . . . . . 34
. . . . . .
6.5 L'altezza di un albero binario . . . . . . . . . . . . . . . . 36 . . . . . .
6.6 La dimensione di un albero binario . . . . . . . . . . . . . . . . 37. . . . . .
6.7 Implementazione degli alberi . . . . . . . . . . . . . . . . . . . 37. . . . . .
6.8 Algoritmi ricorsivi 38
9 Ordinamento 63
9.1 Il problema dell'ordinamento . . . . . . . . . . . . . . . . .
.63 .. . . . .
9.2 Strategie di ordinamento comuni 64
9.3 Quante comparazioni devono esserci? 64
9.4 Ordinamento a bolle . . . . . . . . . . . . . . . . . . . . . . 66. . . . . .
9.5 Ordinamento Insertione . . . . . . . . . . . . . . . . . . . . . . 67. . . . . .
9.6 Ordinamento Selezione 69
9.7 Confronto di O(n2 ) algoritmi di ordinamento . . . . . ................ 70
9.8 Stabilità degli algoritmi di ordinamento . . . . . . . . . . . . . . . . .71 . . . . . .
9.9 Treesort . . . . . . . . . . . . . . . . . . . . . . . . . . . 71. . . . . .
9.10 Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
9.11 Algoritmi di divisione e conquista . . . . . . . . . . . . . . . . . . . . . . . . . . 74
9.12 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
9.13 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
9.14 Riepilogo degli algoritmi di ordinamento basati su confronto . . . . . . . . . . . . . . . . 81
3
9.15 Ordinamenti non basati sul confronto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
9.16 Ordinamenti Bin, Secchio, Radice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
10 Tabelle Hash 85
10.1 Archiviazione dei dati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
10.2 Il tipo di dato astratto Tabella . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
10.3 Implementazioni della struttura dati a tabella . . . . . . . . . . . . . . . . . . . 87
10.4 Tabelle Hash 87
10.5 Probabilità di collisione e fattori di carico per tabelle hash . . . . . . . . . . . . . . 88
10.6 Una semplice tabella hash in funzione . . . . . . . . . . . . . . . . . . . . . . . . . 89
10.7 Strategie per affrontare le collisioni . . . . . . . . . . . . . . . . . . . . . . . 90
10.8 Probing Lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
10.9 Doppia Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
10.10 Scegliere buone funzioni hash . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
10.11 Complessità delle tabelle hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
11 Grafici 98
11.1 Terminologia dei grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
11.2 Implementazione dei grafici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
11.3 Relazioni tra grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
11.4 Pianarità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
11.5 Traversate – visitare sistematicamente tutti i vertici . . . . . . . . . . . . . . . . . . 104
11.6 Percorsi più brevi – Algoritmo di Dijkstra . . . . . . . . . . . . . . . . . . . . . . . 105
11.7 Percorsi più brevi – algoritmo di Floyd . . . . . . . . . . . . . . . . . . . . . . . . 111
11.8 Alberi di copertura minima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
11.9 Venditori itineranti e routing dei veicoli . . . . . . . . . . . . . . . . . . . . . 117
12 Epilogo 118
4
Capitolo 1
Introduzione
In questo modulo ci concentreremo sulla progettazione degli algoritmi. Vedremo come dipendono
sul design di strutture dati adatte e su come alcune strutture e algoritmi siano più
più efficienti degli altri per lo stesso compito. Ci concentreremo su alcuni compiti di base, come la memorizzazione.
ing, ordinare e cercare dati, che sono alla base di gran parte dell'informatica, ma le tecniche
sarà applicabile in modo molto più generale.
Inizieremo studiando alcune strutture dati chiave, come array, liste, code, pile.
e alberi, e poi passare ad esplorare il loro utilizzo in una serie di diverse ricerche e ordinamenti
algoritmi. Questo ci porterà a considerare approcci per lo stoccaggio efficiente dei dati in
tabelle hash. Alla fine, esamineremo le rappresentazioni basate su grafi e tratteremo i tipi di algoritmo
ritmi necessari per lavorare in modo efficiente con loro. In tutto, esamineremo il computazionale
l'efficienza degli algoritmi che sviluppiamo e ottenere intuizioni sui pro e contro di
varie potenziali approcci per ciascun compito.
Non ci limiteremo a implementare le varie strutture dati e algoritmi.
in particolare linguaggi di programmazione per computer (ad es., Java, C, OCaml), ma specificarli in
pseudocodice semplice che può essere facilmente implementato in qualsiasi linguaggio appropriato.
[Link]
e contiene il syllabus ufficiale, il piano completo delle lezioni, un registro di ciò che è stato trattato in
le lezioni finora, tutti gli esercizi di valutazione continua distribuiti finora, collegamenti a fonti affidabili
risorse web altrove, e molte altre informazioni utili sul modulo.
Devi davvero completare il materiale di queste note con un libro di testo o altre fonti.
di informazioni. Le lezioni mireranno ad aiutarti a comprendere queste note e a colmare le lacune
in loro, ma è improbabile che sia sufficiente, perché spesso sarà necessario vedere più di uno
spiegazione di qualcosa prima di poterlo comprendere appieno.
Sono suggeriti alcuni buoni libri di testo nel sito web del modulo, compresi tre che sono gratuiti.
ma non c'è un libro singolo migliore che si adatti a tutti. È una buona idea andare alla principale
biblioteca e biblioteca scolastica e sfogliare gli scaffali di libri su strutture dati e algoritmi.
Se ti piace qualcuno di essi, scarica, prendi in prestito o acquista una copia per te, ma assicurati che
La maggior parte degli argomenti nella lista dei contenuti sopra è coperta.
5
L'argomento di questo modulo è un tema classico, quindi non è necessario utilizzare un libro pubblicato.
di recente. Libri pubblicati 10 o 20 anni fa sono ancora buoni, e continuano a esserci nuovi buoni libri.
pubblicato ogni anno. Il motivo è che questo modulo copre materiale fondamentale importante
che viene insegnato in tutti i corsi di laurea in informatica. Al giorno d'oggi c'è anche molta
molte informazioni utili da trovare su internet, inclusi completi scaricabili gratuitamente
books. The module web-site includes links to the most reliable online resources.
2. Verifica.
3. Analisi delle prestazioni.
6
I dettagli di questi tre aspetti saranno di solito piuttosto dipendenti dal problema.
Le specifiche dovrebbero formalizzare i dettagli cruciali del problema che l'algoritmo sta
cercando di risolvere. A volte ciò si baserà su una particolare rappresentazione dell'associato
I dati, a volte, saranno presentati in modo più astratto. Tipicamente, dovrà specificare come
the inputs and outputs of the algorithm are related, though there is no general requirement
che la specifica sia completa o non ambigua.
Per problemi semplici, è spesso facile vedere che un particolare algoritmo funzionerà sempre,
cioè, che soddisfa le sue specifiche. Tuttavia, per specifiche più complicate e/o
Algoritmi, il fatto che un algoritmo soddisfi la sua specifica potrebbe non essere affatto ovvio.
In questo caso, dobbiamo spendere un po' di sforzo per verificare se l'algoritmo è davvero corretto.
In generale, testare su pochi input particolari può essere sufficiente per dimostrare che l'algoritmo è
errato. Tuttavia, poiché il numero di potenziali input diversi per la maggior parte degli algoritmi è
infinito in teoria, e enorme nella pratica, è necessaria più di una semplice prova su casi particolari
per essere certi che l'algoritmo soddisfi la sua specifica. Abbiamo bisogno di dimostrazioni di correttezza. Anche se
discuteremo delle prove in questo modulo e idee utili e pertinenti come gli invarianti, lo faremo di solito
fai solo così in modo piuttosto informale (anche se ovviamente cercheremo di essere rigorosi).
Il motivo è che vogliamo concentrarci sulle strutture dati e sugli algoritmi. Formale
Le tecniche di verifica sono complesse e saranno insegnate nei moduli successivi.
Infine, l'efficienza o le prestazioni di un algoritmo si riferiscono alle risorse richieste
da esso, come la velocità con cui verrà eseguito, o quanto spazio di memoria del computer utilizzerà. Questo
di solito dipende dalla dimensione dell'istanza del problema, dalla scelta della rappresentazione dei dati e dai dettagli
dell'algoritmo. Infatti, questo è ciò che normalmente guida lo sviluppo di nuove strutture dati
e algoritmi. Studieremo le idee generali riguardanti l'efficienza nel Capitolo 5, e poi
applicali per il resto del modulo.
7
struttura per algoritmi, lasciando i dettagli da aggiungere secondo le esigenze per problemi particolari.
Questi possono accelerare lo sviluppo di algoritmi fornendo algoritmi collaudati e familiari.
strutture che possono essere applicate in modo semplice a nuovi problemi. Vedremo un numero di
modelli di design familiari in questo modulo.
1.5 Overview
Questo modulo tratterà le principali strutture dati e algoritmi fondamentali utilizzati in
informatica e riunire una vasta gamma di argomenti trattati in altri moduli in un
quadro coerente. Le strutture dei dati saranno formulate per rappresentare vari tipi di informazione.
in modo tale che possa essere convenientemente ed efficientemente manipolato dagli algoritmi
sviluppiamo. In tutto questo, i ricorrenti problemi pratici della specificazione degli algoritmi, verifica
e l'analisi delle prestazioni sarà discussa.
Inizieremo esaminando alcune strutture dati di base ampiamente utilizzate (cioè array.
liste collegate, pile e code), e i vantaggi e svantaggi associati
tipi di dati astratti. Poi consideriamo il problema onnipresente della ricerca e come questo
porta alle idee generali di efficienza computazionale e complessità. Questo lascerà
noi con gli strumenti necessari per studiare tre strutture dati particolarmente importanti: alberi (in
particolari, alberi di ricerca binaria e alberi heap), tabelle hash e grafi. Impareremo come
sviluppare e analizzare algoritmi sempre più efficienti per manipolare e svolgere utili
operazioni su quelle strutture e analizzare in dettaglio lo sviluppo di processi efficienti per i dati
memorizzazione, ordinamento, ricerca e analisi. L'idea è che una volta che le idee e gli esempi di base
coperti in questo modulo sono compresi, affrontando problemi più complessi in futuro
dovrebbe essere semplice.
8
Capitolo 2
2.1 Arrays
In informatica, il modo ovvio di memorizzare una collezione ordinata di elementi è come un array.
Gli elementi dell'array sono tipicamente memorizzati in una sequenza di posizioni di memoria del computer, ma per discutere
Abbiamo bisogno di un modo conveniente per scriverli su carta. Possiamo semplicemente scrivere gli articoli.
[in ordine, separati da virgole e racchiusi tra parentesi quadre. Così,]
[1,4,17,3,90,79,4,6,81]
a= [1,4,17,3,90,79,4,6,81]
Questo array ha 9 elementi, e quindi diciamo che la sua dimensione è 9. Nella vita quotidiana, di solito iniziamo
contando da 1. Quando lavoriamo con gli array in informatica, tuttavia, più spesso
(anche se non sempre) partono da 0. Quindi, per il nostro array, le sue posizioni sono 0,1,2,...,7,8. Il
elemento nell'8thla posizione è 81, e usiamo la notazione a[8] per denotare questo elemento. Più
In generale, per qualsiasi intero che denota una posizione, scriviamo a[i] per denotare l'elemento in ith
La posizione. Questa posizione è chiamata indice (e il plurale è indici). Poi, nell'alto
esempio, a[0] = 1, a[1] = 4, a[2] = 17, e così via.
È importante notare a questo punto che il simbolo = è piuttosto sovraccarico. In matematica,
sta per uguaglianza. Nella maggior parte dei linguaggi di programmazione moderni, = denota assegnazione, mentre
l'uguaglianza è espressa da ==. Useremo tipicamente = nel suo significato matematico, a meno che non
è scritto come parte di codice o pseudocodice.
Diciamo che gli elementi individuali a[i] nell'array a vengono accessi utilizzando il loro indice i, e
si può muoversi in modo sequenziale attraverso l'array incrementando o decrementando quell'indice,
o saltare direttamente a un elemento particolare dato il suo valore di indice. Gli algoritmi che elaborano i dati
memorizzati come array di solito dovranno visitare sistematicamente tutti gli elementi nell'array, e
applica le operazioni appropriate su di essi.
9
2.2 Cicli e Iterazione
L'approccio standard nella maggior parte dei linguaggi di programmazione per ripetere un processo un certo
numero di volte, come spostarsi sequenzialmente attraverso un array per eseguire le stesse operazioni
su ogni elemento, implica un ciclo. In pseudocodice, questo assumerebbe tipicamente la forma generale
Per i = 1,...,N,
fai qualcosa
e nelle lingue di programmazione come C e Java questo verrebbe scritto come il ciclo for
INIZIALIZZAZIONE
se (non CONDIZIONE) vai a CICLO FINITO
INIZIO CICLO
PROCESSO RIPETUTO
AGGIORNARE
se ( CONDIZIONE ) vai all'INIZIO DEL CICLO
CICLO FINITO
In this module, we will regularly make use of this basic loop structure when operating on
dati memorizzati in array, ma è importante ricordare che diversi linguaggi di programmazione
utilizzare sintassi diverse, e ci sono numerose variazioni che controllano la condizione per terminare
la ripetizione in diversi punti.
2.3 Invarianti
Un'invariante, come suggerisce il nome, è una condizione che non cambia durante l'esecuzione di
un dato programma o algoritmo. Può essere una semplice disuguaglianza, come “i <20”, o qualcosa
più astratto, come "gli elementi nell'array sono ordinati". Le invarianti sono importanti per i dati
strutture e algoritmi perché consentono prove di correttezza e verifica.
In particolare, un'invariante di ciclo è una condizione che è vera all'inizio e alla fine di ogni
iterazione del ciclo dato. Considera l'esempio semplice standard di una procedura che trova
il minimo dei numeri memorizzati in un array a:
10
minimo(int n, float a[n]) {
float min = a[0];
// min è l'elemento minimo in a[0],...,a[0]
for(int i = 1 ; i != n ; i++) {
// min è l'elemento minimo in a[0],...,a[i-1]
se (a[i] < min) min = a[i];
}
// min è l'elemento minimo in a[0],...,a[i-1], e i==n
ritorna min;
}
All'inizio di ogni iterazione, e alla fine di qualsiasi iterazione precedente, l'invariante "minequals"
il valore minimo nell'a[0], ..., a[i−1]” è vero - inizia a essere vero, e il processo ripetuto
e aggiornare chiaramente mantiene la sua verità. Quindi, quando il ciclo termina con "i==n", noi
sappiamo che "minequals il valore minimo dell'elemento ina[0], ..., a[n−1]" e quindi possiamo essere certi che
min può essere restituito come il valore minimo richiesto. Questo è una sorta di prova per induzione:
l'invariante è vera all'inizio del ciclo ed è preservata da ciascuna iterazione del ciclo,
pertanto deve essere vero alla fine del ciclo.
Come abbiamo notato in precedenza, le dimostrazioni formali di correttezza sono al di là dell'ambito di questo modulo.
ma identificare invarianze di ciclo adeguate e le loro implicazioni per la correttezza dell'algoritmo mentre noi
affrontare questo modulo sarà sicuramente un esercizio utile. Vedremo anche come gli invarianti
(a volte chiamate asserzioni induttive) possono essere utilizzate per formulare prove di correttezza simili
riguardo alle proprietà delle strutture dati che sono definite in modo induttivo.
11
Capitolo 3
Rappresentazione grafica
Le liste non vuote possono essere rappresentate da due cellule, in ciascuna delle quali la prima cella contiene un
puntatore a un elemento della lista e la seconda cella contiene un puntatore a o alla lista vuota o
un'altra cella a due. Possiamo rappresentare un puntatore alla lista vuota tramite una barra diagonale o una croce attraverso
la cella. Ad esempio, l'elenco [3,1,4,2,5] può essere rappresentato come:
- - - -
? ? ? ? ?
3 1 4 2 5
Tipo di dato astratto "Lista"
A un livello astratto, una lista può essere costruita dai due costruttori:
12
•MakeList(elemento,list), che mette un elemento in cima a una lista esistente.
Utilizzando questi, il nostro ultimo elenco di esempio può essere costruito come
FaiElenco(3,FaiElenco(1,FaiElenco(4,FaiElenco(2,FaiElenco(5,VuotoElenco)))))
•primo(elenco), e
•rest(lista).
I selettori funzioneranno solo per elenchi non vuoti (e daranno un errore o un'eccezione sull'elenco vuoto
elenco), quindi abbiamo bisogno di una condizione che ci dica se un dato elenco è vuoto:
•èVuota(lista)
Questo dovrà essere usato per controllare ogni elenco prima di passarli a un selettore.
Chiamiamo lista tutto ciò che può essere costruito dai costruttori EmptyList e
MakeList, so that with the selectorsfirstandrestand the conditionisEmpty, the following
le relazioni sono automaticamente soddisfatte (cioè vere):
•isEmpty(ListaVuota)
•non è vuota(FaiLista(x,l)) (per qualsiasi x e l)
•first(MakeList(x,l)) =x
•rest(MakeList(x,l)) =l
Oltre a costruire e recuperare i componenti delle liste, si potrebbe anche desiderare di
cambiare le liste in modo distruttivo. Questo sarebbe fatto da quelli che vengono chiamati mutatori, i quali modificano o ...
•sostituisciPrimo(x,l)
sostituisciRest(r,l)
Ad esempio, con l = [3,1,4,2,5], applicando replaceFirst(9,l) cambia l in [9,1,4,2,5].
e poi applicando replaceRest([6,2,3,4],l) lo cambia in [9,6,2,3,4].
Vedremo che i concetti di costruttori, selettori e condizioni sono comuni a
praticamente tutti i tipi di dati astratti. In tutto questo modulo, stiamo formulando i nostri dati
rappresentazioni e algoritmi in termini di definizioni appropriate di essi.
13
Rappresentazione XML
Per comunicare strutture di dati tra computer diversi e possibilmente diversi
linguaggi di programmazione, XML (Lingua di Marcatura Estensibile) è diventato un quasi-standard.
L'elenco sopra potrebbe essere rappresentato in XML come:
<ol>
<li>3</li>
<li>1</li>
<li>4</li>
<li>2</li>
<li>5</li>
</ol>
Tuttavia, ci sono di solito molti modi diversi per rappresentare lo stesso oggetto in XML. Per
ad esempio, una rappresentazione orientata alle celle dell'elenco sopra sarebbe:
<cell>
<first>3</first>
<rest>
<cell>
<first>1</first>
<rest>
<cell>
<first>4</first>
<rest>
<cell>
<first>2</first>
<rest>
<first>5</first>
ElencoVuoto
</rest>
</cell>
</rest>
</cell>
</rest>
</cell>
</rest>
</cell>
Anche se questo sembra complicato per una semplice lista, non lo è, è solo un po' lungo. L'XML è flessibile.
sufficiente per rappresentare e comunicare strutture molto complicate in modo uniforme.
important primitive data structure. In some other languages, it is more natural to implement
14
le liste come array. Tuttavia, ciò può essere problematico, poiché le liste non sono concettualmente limitate
in dimensione, e per questo motivo le implementazioni basate su array con array di dimensioni fisse possono solo
approssimare il concetto generale. Per molte applicazioni, questo non è un problema perché un
il numero massimo di membri della lista può essere determinato a priori (ad esempio, il numero massimo di
il numero di studenti in questo modulo è limitato dal numero di studenti nella nostra Università). Più generale
le implementazioni degli scopi seguono un approccio basato su puntatori, che è vicino al diagrammatico
rappresentazione fornita sopra. Non approfondiremo i dettagli di tutte le possibili implementazioni
di elenchi qui, ma tali informazioni sono facilmente disponibili nei manuali standard.
3.2 Ricorsione
Abbiamo visto in precedenza come l'iterazione basata sui cicli for fosse un modo naturale per elaborare collezioni di
gli elementi memorizzati negli array. Quando gli elementi sono memorizzati come liste collegate, non c'è un indice per ogni elemento,
ultimo(l) {
se ( èVuoto(l) )
errore('Errore: lista vuota in ultimo')
altrimenti se ( èVuoto(resto(l)) )
ritorna primo(l)
altro
restituisci l'ultimo(rest(l))
}
Il tempo di esecuzione di questo dipende dalla lunghezza della lista ed è proporzionale a quella lunghezza.
sincelastis viene chiamato tanto spesso quanto ci sono elementi nella lista. Diciamo che la procedura
ha una complessità temporale lineare, cioè, se la lunghezza dell'elenco aumenta di un certo fattore, il
il tempo di esecuzione aumenta dello stesso fattore. Rispetto alla complessità del tempo costante
quale accesso all'ultimo elemento di un array ha, questo è piuttosto brutto. Non significa, tuttavia,
che le liste sono inferiori agli array in generale, significa solo che le liste non sono il tipo di dato ideale
struttura quando un programma deve accedere molto spesso all'ultimo elemento di un lungo elenco.
Un'altra procedura utile ci consente di aggiungere una lista l2 a un'altra lista l1. Ancora, questo
deve essere fatto un elemento alla volta, e questo può essere realizzato ripetutamente prendendo il
primo elemento rimanente di l1 e aggiungendolo all'inizio del restante aggiunto a l2:
append(l1,l2) {
se (èVuoto(l1))
ritorna l2
else
torna FaiLista(primo(l1), aggiungi(resto(l1), l2))
}
The time complexity of this procedure is proportional to the length of the first list,l1, since
dobbiamo chiamare appendas spesso quante sono le elementi in l1.
15
3.3 Stack
Gli stack sono, a un livello astratto, equivalenti alle liste collegate. Sono la struttura dati ideale
per modellare una strategia First-In-Last-Out (FILO) o Last-In-First-Out (LIFO) nella ricerca.
Rappresentazione Grafica
La loro relazione con le liste collegate significa che la loro rappresentazione grafica può essere la stessa, ma
bisogna fare attenzione all'ordine degli oggetti. Ad esempio, lo stack creato inserendo
i numeri [3,1,4,2,5] in quest'ordine sarebbero rappresentati come:
- - - -
? ? ? ? ?
5 2 4 1 3
Tipo di dato astratto “Stack”
Nonostante la loro relazione con le liste collegate, il loro uso diverso significa gli operatori primitivi per
gli stack sono di solito chiamati con nomi diversi. I due costruttori sono:
•èVuoto(stack)
Abbiamo relazioni automaticamente vere equivalenti a quelle che avevamo per le liste:
•isEmpty(PilaVuota)
•non è vuoto(push(x,s)) (per qualsiasi x e s)
•top(push(x,s)) =x
•pop(push(x,s)) =s
In sintesi, abbiamo le corrispondenze dirette:
costruttori selettori condizione
Elenco ListaVuota FaiElenco primo riposo èVuoto
Pila EmptyStack spingere cima pop èVuoto
Quindi, gli stack e le liste collegate sono la stessa cosa, a parte i nomi diversi che vengono usati.
per i loro costruttori e selettori.
16
Implementazione degli Stack
Ci sono due modi diversi in cui possiamo pensare di implementare le pile. Fino ad ora abbiamo implicato
un approccio a funzionalità. Cioè, push non cambia lo stack originale, ma crea un nuovo
pila fuori dalla pila originale e un nuovo elemento. Cioè, ci sono almeno due pile
intorno, l'originale e quello appena creato. Questa visione funzionale è piuttosto comoda.
Se applichiamo top a uno stack particolare, otterremo sempre lo stesso elemento. Tuttavia, da un
dal punto di vista pratico, potremmo non voler creare molti nuovi stack in un programma, a causa di
le ovvie implicazioni nella gestione della memoria. Invece, potrebbe essere meglio pensare a un singolo
stack which is destructively changed, so that after applyingpushthe original stack no longer
esiste, ma è stato cambiato in un nuovo stack con un elemento extra. Questo è concettualmente
più difficile, poiché ora applicare top a uno stack dato potrebbe dare risposte diverse, a seconda
sulla modifica dello stato del sistema. Tuttavia, finché manteniamo questa differenza in
la mente, ignorare tali dettagli implementativi non dovrebbe causare alcun problema.
3.4 Code
Una coda è una struttura dati utilizzata per modellare una strategia First-In-First-Out (FIFO). Concettualmente,
aggiungiamo alla fine di una coda e togliamo elementi dalla sua parte anteriore.
Rappresentazione Grafica
Una coda può essere rappresentata graficamente in modo simile a una lista o a uno stack, ma con un
un ulteriore cella con due elementi in cui il primo elemento punta all'inizio della lista di tutti gli elementi
nella coda, e il secondo elemento punta all'ultimo elemento della lista. Ad esempio, se
inseriamo gli elementi [3,1,4,2] in una coda inizialmente vuota, otteniamo:
? ?
- - -
? ? ? ?
3 1 4 2
Questo accordo significa che prendere il primo elemento della coda, o aggiungere un elemento per
la parte posteriore della coda, possono entrambi essere eseguiti in modo efficiente. In particolare, possono entrambi essere eseguiti con
sforzo costante, cioè indipendentemente dalla lunghezza della coda.
17
? ?
- - - -
? ? ? ? ?
3 1 4 2 5
I due selettori sono gli stessi delle pile:
•èVuota(coda)
Nei capitoli successivi vedremo esempi pratici di come operano le code e gli stack con
effetto diverso.
Rappresentazione Grafica
Le liste doppiamente collegate non vuote possono essere rappresentate da tre celle, in cui la prima cella contiene un
puntatore a un'altra cella di tre o alla lista vuota, la seconda cella contiene un puntatore alla lista
l'elemento e la terza cella contiene un puntatore a un'altra cella a tre elementi o alla lista vuota. Ancora,
rappresentiamo l'elenco vuoto con una barra diagonale o una croce attraverso la cella appropriata. Ad esempio,
[3,1,4,2,5] sarebbe rappresentato come lista doppia collegata come:
- - - -
? ? ? ? ?
3 1 4 2 5
Tipo di Dato Astratto “Lista Doppiamente Collegata”
A un livello astratto, una lista doppiamente collegata può essere costruita dai tre costruttori:
18
•MakeListLeft(elemento, lista), che prende un elemento e una lista doppiamente collegata e
restituisce una nuova lista doppiamente concatenata con l'elemento aggiunto a sinistra dell'originale
lista doppiamente collegata.
È chiaro che è possibile costruire una determinata lista doppiamente collegata in più di un modo.
Ad esempio, la lista doppiamente collegata rappresentata sopra può essere costruita da uno dei seguenti modi:
CreaListaSinistra(3,CreaListaSinistra(1,CreaListaSinistra(4,CreaListaSinistra(2,
MakeListLeft(5,EmptyList)))))
FaiListaSinistra(3,FaiListaSinistra(1,FaiListaDestra(5,FaiListaDestra(2,
MakeListLeft(4,EmptyList)))))
•firstLeft(lista),
•restLeft(elenco),
•firstRight(lista), e
•restRight(lista).
Quindi, poiché i selettori funzionano solo per elenchi non vuoti, abbiamo anche bisogno di una condizione che restituisca
se una lista è vuota:
•èVuoto(lista)
Questo porta a relazioni automaticamente vere come:
•èVuoto(ListaVuota)
•non èVuoto(FaiListaSinistra(x,l)) (per qualsiasi x e l)
•firstLeft(FaiListaSinistra(x,l)) = x
•restLeft(MakeListLeft(x,l)) =l
•firstRight(FaiListaDestra(x,l)) =x
•restRight(MakeListRight(x,l)) =l
lista collegata in cui l'elemento più a sinistra punta all'elemento più a destra e viceversa.
Questo è utile quando potremmo aver bisogno di muoverci in modo efficiente attraverso un'intera lista di elementi, ma potremmo
non partire da uno dei due estremi particolari.
19
3.6 Vantaggio dei Tipi di Dati Astratti
È chiaro che l'implementazione del tipo di dato astratto lista collegata ha lo svantaggio
che alcune procedure utili potrebbero non essere direttamente accessibili. Ad esempio, lo standard
il tipo di dati astratto di una lista non offre una procedura efficiente last(l) per dare l'ultimo
elemento nella lista, mentre sarebbe banale trovare l'ultimo elemento di un array di un noto
numero di elementi. Si potrebbe modificare il tipo di dati della lista collegata mantenendo un puntatore
fino all'ultimo elemento, come abbiamo fatto per il tipo di dati coda, ma non avremmo comunque un modo semplice
per accedere agli elementi intermedi. Le procedure whilelast(l) e getItem(i,l) possono essere facilmente
implementati utilizzando i costruttori primitivi, i selettori e le condizioni, è probabile che siano
meno efficiente rispetto all'utilizzo di alcuni aspetti dell'implementazione sottostante.
Quello svantaggio porta a una domanda ovvia: Perché dovremmo voler usare dati astratti?
tipi quando spesso portano a algoritmi meno efficienti? Aho, Hopcroft e Ullman (1983)
fornire una risposta chiara nel loro libro:
All'inizio, potrebbe sembrare noioso scrivere procedure per governare tutti gli accessi al
strutture sottostanti. Tuttavia, se ci disciplineremo a scrivere programmi in
termini delle operazioni per manipolare tipi di dati astratti piuttosto che fare
l'uso di dettagli di implementazione particolari, quindi possiamo modificare i programmi di più
prontamente riprogrammando le operazioni piuttosto che cercare in tutti i programmi per
luoghi in cui abbiamo effettuato accessi alle strutture dati sottostanti. Questo
La flessibilità può essere particolarmente importante in grandi sforzi software, e il lettore
non si dovrebbe giudicare il concetto in base ai necessariamente piccoli esempi presenti in questo libro.
Questo vantaggio diventerà più chiaro quando studieremo tipi di dati astratti più complessi e
algoritmi nei capitoli successivi.
20
Capitolo 4
Cercando
Come abbiamo già notato, gli array sono uno dei modi più semplici per rappresentare col-
lezioni di numeri (o stringhe, o qualunque cosa), quindi useremo questo per memorizzare le informazioni per
essere cercato. Più tardi esamineremo strutture dati più complesse che potrebbero rendere la memorizzazione e
ricerca più efficiente.
Supponiamo, ad esempio, che l'insieme degli interi che desideriamo cercare sia {1,4,17,3,90,79,4,6,81}.
Possiamo scriverli in un array
a= [1,4,17,3,90,79,4,6,81]
Se chiediamo dove si trova 17 in questo array, la risposta è 2, l'indice di quell'elemento. Se chiediamo dove si trova 91
è, la risposta è nessun luogo. È utile poter rappresentare nessun luogo con un numero che è
non utilizzato come possibile indice. Poiché iniziamo il conteggio del nostro indice da 0, qualsiasi numero negativo
faremo. Seguiremo la convenzione di usare il numero -1 per rappresentare il nulla. Altro
(forse è possibile adottare convenzioni migliori, ma ci attaccheremo a questa qui.
21
4.2 Specifica del problema di ricerca
Possiamo ora formulare una specifica del nostro problema di ricerca utilizzando quella struttura dati:
La prima clausola dice che se x non appare nell'array a, allora i dovrebbe essere -1, e il
il secondo dice che se si verifica allora dovrebbe esserci una posizione in cui si verifica. Se c'è
più di una posizione in cui si verifica, allora questa specifica ti consente di restituire qualsiasi di
loro – per esempio, questo sarebbe il caso se fossi [17,13,17] e x fosse 17. Quindi, il
La specifica è ambigua. Pertanto, diversi algoritmi con comportamenti diversi possono soddisfare
la stessa specifica – ad esempio, un algoritmo può restituire la posizione più piccola a
quale si verifica, e un altro può restituire il più grande. Non c'è nulla di sbagliato nell'ambiguo
specifiche. Infatti, nella pratica, si verificano abbastanza spesso.
Al alcuni aspetti, come l'ellissi “. . .”, sono potenzialmente ambigui, ma noi, come esseri umani,
sappiamo esattamente cosa si intende, quindi non dobbiamo preoccuparci di loro. In un programma
linguaggi come CorJava, si scriverebbe qualcosa di più preciso come:
22
in realtà non c'è, perché si sta tentando di accedere a una posizione non esistente. A seconda
sulla particolare lingua, sistema operativo e macchina che stai utilizzando, l'effetto reale di
questo errore sarà diverso. Ad esempio, in esecuzione sotto Unix, potresti ottenere un'esecuzione
aborted followed by the message “segmentation fault”, or you may be given the wrong answer
come output. In Java, riceverai sempre un messaggio di errore.
// Questo presuppone che ci venga dato un array ordinato a di dimensione n e una chiave x.
// Usa interi sinistro e destro (inizialmente impostati a 0 e n-1) e medio.
Finché sinistra è minore di destra,
imposta mid alla parte intera di (sinistra+desta)/2 e
se x è maggiore di a[mid],
then imposta sinistra a mid+1,
altrimenti imposta a medio.
Se a[left] è uguale a x,
quindi termina restituendo sinistra,
altrimenti termina restituendo -1.
e corrisponderebbe a un segmento di codice CorJava come:
/* DATA */
int a = [1,3,4,4,6,17,79,81,90];
int n = 9;
int x = 79;
/* PROGRAM */
int sinistra = 0, destra = n-1, centrale;
mentre ( sinistra < destra ) {
mid = ( sinistra + destra ) / 2;
se ( x > a[mid] ) sinistra = mid+1;
altrimenti destra = metà;
}
se ( a[left] == x ) restituisce left;
altrimenti restituisci -1;
23
Questo algoritmo funziona dividendo ripetutamente l'array in due segmenti, uno che va da sinistra.
tomid, e l'altro va da mid + 1 a right, dove mid è la posizione a metà strada da
lefttoright, and where, initially,leftandrightare the leftmost and rightmost positions of
l'array. Poiché l'array è ordinato, è facile vedere quale dei vari segmenti di ogni coppia
l'elemento cercato è in, e la ricerca può quindi essere limitata a quel segmento. Inoltre,
perché la dimensione del sotto-array che va da locationslefttoright è dimezzata ad ogni iterazione
del ciclo while, abbiamo solo bisogno di log2npassi nel caso medio o peggiore. Per vedere che questo
il comportamento runtime è un grande miglioramento, in pratica, rispetto all'algoritmo di ricerca lineare precedente,
nota che il registro21000000
è approssimativamente 20, quindi per un array di dimensione 1000000 solo 20
nel caso peggiore dell'algoritmo di ricerca binaria, sono necessarie iterazioni, mentre 1000000 sono
necessario nel caso peggiore dell'algoritmo di ricerca lineare.
Con l'algoritmo di ricerca binaria, non è così ovvio che ci siamo presi cura adeguata.
della condizione al contorno nel ciclo while. Inoltre, a rigor di termini, questo algoritmo non è
corretto perché non funziona per l'array vuoto (che ha dimensione zero), ma questo può essere facilmente
essere fissato. A parte questo, è corretto? Cerca di convincere te stesso che sia così, e poi prova a
explain your argument-for-correctness to a colleague. Having done that, try towrite down
alcuni argomenti convincenti, forse uno che coinvolge un'invariante di ciclo e uno che non lo fa.
La maggior parte degli sviluppatori di algoritmi si ferma alla prima fase, ma l'esperienza dimostra che è solo quando
cerchiamo di scrivere argomenti apparentemente convincenti che in realtà troviamo tutti i sottili
errori. Inoltre, non è insolito finire con un algoritmo migliore/più chiaro dopo che è stato
è stato modificato per rendere più facile discutere la sua correttezza.
Vale la pena considerare se le versioni a lista collegata dei nostri due algoritmi funzionerebbero, o
offrire vantaggi. È piuttosto chiaro che potremmo eseguire una ricerca lineare attraverso un collegamento
elenca essenzialmente nello stesso modo di un array, con il puntatore rilevante restituito piuttosto
rispetto a un indice. Convertire la ricerca binaria in una forma di lista collegata è problematico, perché ci
non c'è un modo efficiente per dividere una lista collegata in due segmenti. Sembra che il nostro array-based
l'approccio è il migliore che possiamo fare con le strutture dati che abbiamo studiato finora. Tuttavia, noi
vedremo più tardi come strutture di dati più complesse (alberi) possano essere utilizzate per formulare in modo efficiente
algoritmi di ricerca ricorsiva.
Nota che non abbiamo ancora preso in considerazione quanto sforzo sarà necessario per ordinare
l'array in modo che l'algoritmo di ricerca binaria possa funzionare su di esso. Finché non lo sappiamo, non possiamo
assicurati che l'utilizzo dell'algoritmo di ricerca binaria sia davvero più efficiente nel complesso rispetto all'utilizzo di
linear search algorithm on the original unsorted array. That may also depend on further
dettagli, come quante volte dobbiamo effettuare una ricerca sul set di oggetti - solo
una volta, o quante volte. Torneremo su queste questioni più tardi. Prima dobbiamo considerare
in maggiore dettaglio su come confrontare l'efficienza degli algoritmi in modo affidabile.
24
Capitolo 5
Efficienza e Complessità
Abbiamo già notato che, nello sviluppare algoritmi, è importante considerare come
efficaci sono, così possiamo fare scelte informate su quali siano i migliori da usare in particolare
circostanze. Quindi, prima di passare a studiare strutture dati sempre più complesse e
algoritmi, iniziamo a guardare più nel dettaglio come misurare e descrivere la loro efficienza.
Quando si crea software per applicazioni serie, c'è di solito la necessità di valutare quanto velocemente
an algorithm or program can complete the given tasks. For example, if you are programming
un sistema di prenotazione voli, non sarà considerato accettabile se l'agente di viaggio e il cliente
deve aspettare mezz'ora affinché una transazione si completi. Deve certamente essere assicurato
che il tempo di attesa è ragionevole per la dimensione del problema e di norma un'esecuzione più rapida
is better. We talk about thetime complexityof the algorithm as an indicator of how the
il tempo di esecuzione dipende dalle dimensioni della struttura dati.
Un'altra considerazione importante per l'efficienza è quanta memoria utilizzerà un dato programma.
richiedere per un compito particolare, anche se con i computer moderni questo tende a essere meno un problema
rispetto a prima. Qui parliamo della complessità spaziale come requisito di memoria.
dipende dalle dimensioni della struttura dei dati.
Per un compito specifico, ci sono spesso algoritmi che scambiano tempo per spazio, e viceversa.
Ad esempio, vedremo che, come dispositivo di archiviazione dati, le tabelle hash hanno un tempo molto buono
complessità a scapito dell'uso di più memoria rispetto a quanto necessario da altri algoritmi. È
solitamente spetta al progettista dell'algoritmo/programma decidere come meglio bilanciare il compromesso per
l'applicazione che stanno progettando.
Un'altra cosa che deve essere decisa quando si fanno considerazioni di efficienza è se sia
la prestazione del caso medio di un algoritmo/programma che è importante, o se è
è più importante garantire che anche nel peggiore dei casi le prestazioni obbediscano a determinate regole.
Per molte applicazioni, il caso medio è più importante, perché risparmiare tempo complessivamente è
di solito più importante che garantire un buon comportamento nel peggior caso. Tuttavia, per
problemi critici per il tempo, come tenere traccia degli aerei in determinati settori dello spazio aereo, è
potrebbe essere totalmente inaccettabile per il software impiegare troppo tempo se si verifica il peggior scenario.
25
Ancora una volta, gli algoritmi/programmi spesso fanno un compromesso tra l'efficienza del caso medio e l'efficienza
del caso peggiore. Ad esempio, l'algoritmo più efficiente in media potrebbe avere una par-
particolarmente cattiva efficienza nel peggiore dei casi. Vedremo esempi particolari di questo quando considereremo
algoritmi efficienti per ordinare e cercare.
26
della funzione di complessità con dimensione del problema, e quindi qualcosa sulle prestazioni di
l'algoritmo su un gran numero di elementi.
Se un algoritmo è tale che possiamo considerare tutti i passaggi ugualmente costosi, allora di solito il
La complessità dell'algoritmo è semplicemente determinata dal numero di cicli e da quanto spesso.
il contenuto di quei cicli viene eseguito. Il motivo di ciò è che aggiungere una costante
il numero di istruzioni che non cambia con la dimensione del problema non ha un significato significativo
effetto sulla complessità complessiva per grandi problemi.
There is a standard notation, called theBig-O notation, for expressing the fact that
fattori costanti e altri dettagli insignificanti vengono ignorati. Ad esempio, abbiamo visto che
la procedura last(l) su una lista l aveva una complessità temporale che dipendeva linearmente dalla dimensione n
della lista, quindi potremmo dire che la complessità temporale di quell'algoritmo è O(n). In modo simile,
la ricerca lineare è O(n). Tuttavia, per la ricerca binaria, la complessità temporale è O(log2n).
Prima di definire le classi di complessità in modo più formale, vale la pena cercare di ottenere
alcune intuizioni su cosa significano realmente. A tal fine, è utile scegliere uno
funzione come rappresentante di ciascuna delle classi che desideriamo considerare. Ricorda che siamo
considerando funzioni che mappano i numeri naturali (la dimensione del problema) all'insieme dei non-
numeri reali negativi+ , quindi le classi corrisponderanno a funzioni matematiche comuni
come poteri e logaritmi. Considereremo in seguito a quale grado un rappresentante può
essere considerato 'tipico' per la sua categoria.
Le classi di complessità più comuni (in ordine crescente) sono le seguenti:
27
Alcuni di questi numeri sono così grandi che è piuttosto difficile immaginare quanto a lungo un
l'intervallo di tempo che descrivono. Pertanto, la seguente tabella fornisce intervalli di tempo piuttosto che istruzioni
conteggi, basati sull'assunzione che abbiamo un computer in grado di operare a una velocità di 1
MIP, dove un MIP = un milione di istruzioni al secondo:
È chiaro che, man mano che le dimensioni dei problemi diventano davvero grandi, ci possono essere enormi differenze
nel tempo necessario per eseguire algoritmi di diverse classi di complessità. Per algoritmi
con complessità esponenziale, O(2n ), anche problemi di dimensioni modeste hanno tempi di esecuzione che sono
maggiore dell'età dell'universo (circa 1,4×1010e i computer attuali raramente funzionano
ininterrotto per più di qualche anno. Ecco perché le classi di complessità sono così importanti –
ci dicono quanto sia probabile che sia fattibile eseguire un programma con un numero particolarmente grande
di elementi di dati. Tipicamente, le persone non si preoccupano molto della complessità per dimensioni inferiori a 10, o
forse 20, ma i numeri sopra rendono chiaro perché valga la pena pensare alla complessità
classi in cui si tratta di applicazioni più grandi.
Un altro modo utile di pensare alle classi di crescita implica considerare come il calcolo
il tempo varierà se la dimensione del problema raddoppia. La seguente tabella mostra cosa succede per il
varie classi di complessità:
Questo tipo di informazione può essere molto utile nella pratica. Possiamo testare il nostro programma su un problema.
che è metà, un quarto o un ottavo della dimensione intera, e avere una buona idea di quanto tempo abbiamo
dovrà aspettare che il problema delle dimensioni complete finisca. Inoltre, quella stima non sarà influenzata
da qualsiasi fattore costante trascurato nel calcolo della classe di crescita, o dalla velocità del particolare
computer su cui è in esecuzione.
Il grafico seguente rappresenta alcune delle funzioni delle classi di complessità dalla tabella. Nota
anche se queste funzioni sono definite solo sui numeri naturali, sono tracciate come se
erano definiti per tutti i numeri reali, perché ciò rende più facile assorbire l'informazione
presentato.
28
100
2n
90 n2
80
n log n
70
60
n
50
40
30
20
10
log n
0
10 20 30 40 50 60 70 80 90 100
È chiaro da questi grafici perché i termini di crescita non principali possano essere ignorati in sicurezza quando
complessità degli algoritmi di calcolo.
Definizione. Una funzione g appartiene alla classe di complessità O(f) se esiste un numero n0∈N
e una costante c > 0 tale che per ogni n ≥ n0 , abbiamo che g(n)≤c∗f(n). Diciamo che il
functiongis ‘eventually smaller’ than the functionc∗f.
Non è del tutto ovvio cosa ciò implichi. Innanzitutto, non dobbiamo sapere esattamente quando
diventa più piccolo di c ∗f. Siamo interessati solo all'esistenza di n0così che,
da allora, gis è più piccolo di c ∗f. In secondo luogo, desideriamo considerare l'efficienza di un
algoritmo indipendentemente dalla velocità del computer che lo eseguirà. Questo è
perché il wifi è moltiplicato per una costante c. L'idea è che quando misuriamo il tempo del
passaggi di un particolare algoritmo, non siamo sicuri di quanto tempo ciascuno di essi richieda. Per definizione,
g ∈O(f) significa che alla fine (vale a dire oltre il punto n0 ), la crescita di g sarà
al massimo quanto la crescita di c∗f. Questa definizione rende anche chiaro che costante
i fattori non cambiano la classe di crescita (o classe O) di una funzione. Quindi C(n) = n2è in
la stessa classe di crescita come C(n) = 1/1000000∗n2orC(n) = 1000000∗n2 . Quindi possiamo scrivere
O(n2 ) =O(1000000∗n2 ) =O(1/1000000∗n2 ). Di solito, tuttavia, scegliamo il più semplice
rappresentativo, come abbiamo fatto nelle tabelle sopra. In questo caso è O(n2 ).
29
Le varie classi che abbiamo menzionato sopra sono correlate come segue:
Consideriamo solo la classe di crescita principale, quindi quando aggiungiamo funzioni di crescita diverse
le classi, la loro somma sarà sempre nella classe di crescita più grande. Questo ci permette di semplificare i termini.
Ad esempio, la classe di crescita di C(n) = 500000log2n + 4 n 2+0.3n+100 può essere determinato come
segue. Il sommando con la classe di crescita più grande è 4n2diciamo che questo è il ‘principale
sottoterm
fattori, quindi questa funzione è nella classe O(n2 ).
Quando diciamo che un algoritmo 'appartiene' a una classe O(f), intendiamo che è al massimo
crescita rapida. Abbiamo visto che la 'ricerca lineare' (dove si cerca in una collezione
di elementi di dati che sono non ordinati) ha complessità lineare, ossia è nella classe di crescita O(n). Questo
vale sia per il caso medio che per il caso peggiore. Le operazioni necessarie sono confronti
dell'elemento che stiamo cercando con tutti gli elementi che appaiono nella raccolta di dati. In
nel peggiore dei casi, dobbiamo controllare tutte le voci fino a trovare quella giusta, il che significa che facciamo
inconfronti. In media, tuttavia, dovremo controllare solo n/2 voci finché non raggiungiamo il
corretto, lasciandoci con n/2 operazioni. Entrambe quelle funzioni, C(n) = n e C(n) = n/2
appartengono alla stessa classe di complessità, ovvero O(n). Tuttavia, sarebbe altrettanto corretto.
say that the algorithm belongs toO(n2 ), poiché quella classe contiene tuttoO(n). Ma questo sarebbe
meno informativo, e non diremmo che un algoritmo ha complessità quadratica se noi
sappi che, in effetti, è lineare. A volte è difficile essere certi di quale sia la complessità esatta
è (come nel caso del famoso problema NP = P), nel qual caso si potrebbe dire che un
l'algoritmo è 'al massimo', diciamo, quadratico.
La questione dell'efficienza e della classe di complessità, e del loro calcolo, sarà un tema ricorrente
caratteristica in tutti i capitoli a venire. Vedremo che concentrarsi solo sui com-
la classe di complessità, piuttosto che trovare funzioni di complessità esatte, può rendere l'intero processo di
considerando l'efficienza molto più facile. Nella maggior parte dei casi, possiamo determinare la complessità temporale per
un semplice conteggio dei cicli e delle altezze degli alberi. Tuttavia, vedremo anche almeno un caso
dove ciò porta a una sovrastima e è necessaria una computazione più esatta.
30
Capitolo 6
Alberi
In informatica, un albero è una struttura dati molto generale e potente che somiglia a un
albero reale. È composto da un insieme ordinato di nodi collegati in un grafo connesso, in cui ciascuno
un nodo ha al massimo un nodo genitore e zero o più nodi figli con un ordine specifico.
3 11
1 6 9 14
7 10 12 15
Più formalmente, un albero può essere definito come l'albero vuoto, o come un nodo con un elenco di successori.
alberi. I nodi sono di solito, anche se non sempre, etichettati con un elemento di dato (come un numero o
cerca chiave). Ci riferiremo all'etichetta di un nodo come al suo valore. Nei nostri esempi, in generale faremo
usa nodi etichettati da interi, ma si potrebbero facilmente scegliere qualcos'altro, ad esempio stringhe
di personaggi.
Per parlare in modo rigoroso degli alberi, è conveniente avere un po' di terminologia: Ci
deve sempre esserci un nodo 'di alto livello' unico noto come theroot. Nella Figura 6.1, questo è il nodo
etichettato con 8. È importante notare che, nell'informatica, gli alberi sono normalmente visualizzati
capovolto, con la radice che forma il livello superiore. Quindi, dato un nodo, ogni nodo nel successivo
il livello 'inferiore', che è collegato al nodo dato tramite un ramo, è un figlio di quel nodo. In
31
La figura 6.1, i figli del nodo 8 sono i nodi 3 e 11. Viceversa, il nodo (ci sono al massimo
uno) connesso al nodo dato (tramite un arco) al livello superiore, è il suo genitore. Ad esempio,
node 11 is the parent of node 9 (and of node 14 as well). Nodes that have the same parent
sono conosciuti come fratelli - i fratelli sono, per definizione, sempre allo stesso livello.
Se un nodo è il figlio di un figlio di... di un altro nodo, allora diciamo che il primo nodo
è un discendente del secondo nodo. Al contrario, il secondo nodo è un antenato del primo
nodo. I nodi che non hanno figli sono conosciuti come foglie (ad es., i nodi etichettati
con 1, 7, 10, 12 e 15 nella Figura 6.1).
Apathis a sequence of connected edges from one node to another. Trees have the property
che per ogni nodo c'è un percorso unico che lo collega con la radice. Infatti, questo è un altro
definizione possibile di un albero. La profondità o livello di un nodo è data dalla lunghezza di questo percorso.
Quindi la radice ha livello 0, i suoi figli hanno livello 1, e così via. La lunghezza massima di un
un percorso in un albero è chiamato anche l'altezza dell'albero. Un percorso di lunghezza massima va sempre
dalla radice a una foglia. La dimensione di un albero è data dal numero di nodi che contiene. Noi
si assumerà normalmente che ogni albero sia finito, anche se generalmente questo non deve essere il caso.
L'albero nella Figura 6.1 ha un'altezza di 3 e una dimensione di 11. Un albero costituito solo da un nodo ha
altezza 0 e dimensione 1. L'albero vuoto ha ovviamente dimensione 0 ed è definito (convenientemente, anche se
in qualche modo artificialmente) avere un'altezza di -1.
Come la maggior parte delle strutture dati, abbiamo bisogno di un insieme di operatori primitivi (costruttori, selettori
e condizioni) per costruire e manipolare gli alberi. I dettagli di ciò dipendono dal tipo
e lo scopo dell'albero. Ora esamineremo alcuni tipi di albero particolarmente utili.
(Regola 2) un nodo radice senza valore e quattro figli dell'albero quad: lu, ll, ru e rl.
•baseQT(valore), che restituisce un albero quad con un nodo singolo e valore di etichetta.
•makeQT(luqt, ruqt, llqt, rlqt), che costruisce un quadtree da quattro quadri costitutivi.
arbore, llqt, ruqt, rlqt.
32
Poi, per estrarre i componenti da un quad-tree, abbiamo quattro selettori:
•lu(qt), che restituisce il quadrante superiore sinistro dell'albero quad.
0 10
50 60 70
110 120
80
20
100 90
40 30
Possiamo quindi creare algoritmi utilizzando gli operatori per eseguire manipolazioni utili di
rappresentazione. Ad esempio, potremmo ruotare un'immagine di 180 gradi◦ usando:
ruota(qt) {
se ( èValore(qt) )
restituire qt
altrimenti restituisci makeQT( ruota(rl(qt)), ruota(ll(qt)),
ru(qt) ruotare(), lu(qt) ruotare()
}
o potremmo calcolare valori medi mediando ricorsivamente i sotto-alberi costituenti.
Esistono numerose variazioni di questa idea generale, come i quadtree colorati che memorizzano
triplette di valori che rappresentano colori piuttosto che scale di grigio, e quad-tree di bordo che memorizzano
linee e consentire che le curve siano rappresentate con precisione arbitraria.
33
Definizione. Un albero binario è o
Ancora una volta, la Regola 1 è il "caso base" e la Regola 2 è il "passo di induzione". Questa definizione può
appaiono circolari, ma in realtà non lo sono, perché i sottoalberi sono sempre più semplici di
quello originale, e alla fine ci ritroviamo con un albero vuoto.
Puoi immaginare che la collezione (infinita) di alberi (finiti) venga creata in una sequenza di
giorni. Il giorno 0 è quando "decolli" applicando la Regola 1 per ottenere l'albero vuoto. Su
nei giorni successivi, puoi utilizzare tutti gli alberi che hai creato nei giorni precedenti per costruire
nuovi alberi usando la Regola 2. Quindi, ad esempio, nel giorno 1 puoi creare esattamente alberi che hanno
una radice con un valore, ma senza figli (cioè sia il sottoalbero sinistro che quello destro sono l'albero vuoto,
creato al giorno 0). Al giorno 2 puoi utilizzare un nuovo nodo con valore, con l'albero vuoto e/o
l'albero a un nodo, per creare più alberi. Pertanto, gli alberi binari sono gli oggetti creati da
le due regole sopra in un numero finito di passaggi. L'altezza di un albero, definita sopra, è il numero
di giorni ci vuole per crearlo utilizzando le due regole sopra, dove assumiamo che solo una regola sia
usato al giorno, come abbiamo appena discusso. (Esercizio: calcola la sequenza di passi necessari per
crea l'albero nella Figura 6.1 e quindi prova che è in effetti un albero binario.
•CreaAlbero(v,l,r), che costruisce un albero binario da un nodo radice con etichetta v e due
alberi binari costitutivi
una condizione per testare se un albero è vuoto:
che crea un albero costituito da un singolo nodo con etichetta v, che è la radice e l'unico
foglia dell'albero allo stesso tempo. Quindi, l'albero nella Figura 6.1 può essere costruito come:
34
t = FaiAlbero(8, FaiAlbero(3,Foglia(1),FaiAlbero(6,VascaVuota,Foglia(7))),
CreaAlbero(11,CreaAlbero(9,VuotoAlbero,Foglia(10)),CreaAlbero(14,Foglia(12),Foglia(15))))
che è molto più semplice della costruzione che utilizza gli operatori primitivi:
t = CreaAlbero(8, CreaAlbero(3, CreaAlbero(1, AlberoVuoto, AlberoVuoto),
FaiAlbero(6,AlberoVuoto,FaiAlbero(7,AlberoVuoto,AlberoVuoto)))
CreaAlbero(11,CreaAlbero(9,VuotoAlbero,CreaAlbero(10,VuotoAlbero,VuotoAlbero)),
FaiAlbero(14, FaiAlbero(12, AlberoVuoto, AlberoVuoto),
MakeTree(15,EmptyTree,EmptyTree))))
Si noti che i selettori possono operare solo su alberi non vuoti. Ad esempio, per l'albero
definito sopra abbiamo
radice(sinistra(sinistra(t))) = 1,
ma l'espressione
radice(sinistra(sinistra(sinistra(t))))
non ha senso perché
sinistra(sinistra(sinistra(t))) = AlberoVuoto
e l'albero vuoto non ha una radice. In un linguaggio come Java, questo sarebbe tipicamente
sollevare un'eccezione. In un linguaggio come C, questo causerebbe un comportamento imprevedibile,
ma se sei fortunato, verrà prodotto un core dump e il programma verrà interrotto con
nessun ulteriore danno. Quando scriviamo algoritmi, dobbiamo controllare gli argomenti del selettore utilizzando
isEmpty(t) prima di consentirne l'uso.
Le seguenti equazioni dovrebbero essere ovvie dalle definizioni degli operatori primitivi:
radice(FaiAlbero(v,l,r)) = v
sinistra(MakeTree(v,l,r)) = l
destra(MakeTree(v,l,r)) = r
isEmpty(EmptyTree) = vero
isEmpty(MakeTree(v,l,r)) = falso
Il seguente ha senso solo sotto l'assunzione che t sia un albero non vuoto:
CreaAlbero(radice(t),sinistra(t),destra(t)) = t
Dice semplicemente che se separiamo un albero non vuoto e utilizziamo i pezzi per costruire un nuovo albero,
poi otteniamo un albero identico.
Vale la pena sottolineare che le specifiche sopra riportate per gli alberi quad e gli alberi binari sono
ulteriori esempi di tipi di dati astratti: Tipi di dati per i quali esibiamo i costruttori
e distruttori e descrivere il loro comportamento (utilizzando equazioni come definite sopra per le liste,
stack, code, quad-tree e alberi binari), ma per i quali nascondiamo esplicitamente l'implementazione-
I dettagli computazionali. Il tipo di dato concreto utilizzato in un'implementazione è chiamato struttura dati.
Ad esempio, le strutture dati abituali utilizzate per implementare i tipi di dati lista e albero sono
registri e puntatori - ma sono possibili altre implementazioni.
Il vantaggio importante dei tipi di dati astratti è che possiamo sviluppare algoritmi senza
dover preoccuparsi dei dettagli della rappresentazione dei dati o dell'implementazione.
Certo, tutto sarà alla fine rappresentato come sequenze di bit in un computer, ma
Chiaramente non vogliamo generalmente dover pensare in termini così elementari.
35
6.5 L'altezza di un albero binario
Gli alberi binari non hanno una relazione semplice tra la loro dimensione e altezza. Il massimo
l'altezza di un albero binario con nnodi è (n−1), che si verifica quando tutti i nodi non foglia hanno
esattamente un bambino, formando qualcosa che assomiglia a una catena. D'altra parte, supponiamo che noi
havennodes and want to build from them a binary tree with minimal height. We can achieve
questo ‘riempiendo’ ogni livello successivo a turno, partendo dalla radice. Non importa dove
posizioniamo i nodi all'ultimo livello (inferiore) dell'albero, finché non iniziamo ad aggiungere a
il livello successivo prima che il livello precedente sia pieno. La terminologia varia, ma diremo che tale
gli alberi sono perfettamente bilanciati o bilanciati in altezza, e vedremo più tardi perché sono ottimali per
molti dei nostri scopi. Fondamentalmente, se fatto in modo appropriato, molte operazioni importanti basate sugli alberi
(come la ricerca) compie tanti passi quanti l'altezza dell'albero, quindi minimizzando l'altezza
minimizza il tempo necessario per eseguire quelle operazioni.
Possiamo facilmente determinare il numero massimo di nodi che possono adattarsi a un albero binario di
a una certa altezza. Chiamando questa funzione di dimensione(h), otteniamo:
h s(h)
0 1
1 3
2 7
3 15
Infatti, sembra abbastanza ovvio che s(h) = 1 + 2 + 4 + · · · + 2h= 2h+1-1. Questa ipotesi
può essere dimostrato per induzione usando la definizione di un albero binario come segue:
(a) Il caso base si applica all'albero vuoto che ha altezza=-1, il che è coerente
con (−1) = 2−1+1-1 = 20-1 = 1-1 = 0 nodi in memoria.
(b) Quindi, per il passo di induzione, un albero di altezza + 1 ha un nodo radice più due sottoalberi di
altezza. Secondo l'ipotesi di induzione, ogni sottoberce può memorizzare(h) = 2h+1-1 nodi,
Quindi il numero totale di nodi che possono stare in un albero di altezza + 1 è 1 + 2×(2h+1-1) =
1 + 2h+2-2 = 2(h+1)+1−1 =s(h+ 1). Ne consegue che se s(h) è corretto per il vuoto
albero, che è stato dimostrato essere nel caso base sopra, allora è corretto per tutti h.
Un ovvio problema potenziale con qualsiasi prova per induzione come questa, tuttavia, è la necessità di
identificare un'ipotesi di induzione da cui partire, e questo non è sempre facile.
Un altro modo di procedere qui sarebbe semplicemente sommare le serie (h) = 1 + 2 + 4 + · · · + 2h
algebricamente per ottenere la risposta. A volte, tuttavia, la serie pertinente è troppo complicata
per sommare facilmente. Un'alternativa è cercare di identificare due espressioni diverse per s(h + 1) come un
funzione ofs(h), e risolvili per s(h). Qui, dal momento che il livello di un albero ha chiaramente 2hnodi,
possiamo aggiungere esplicitamente il 2h+1nodi dell'ultimo livello dell'albero di altezza + 1 da fornire
s(h+ 1) = 1 + 2s(h)
s(h) = 2h+1-1
36
quale è la risposta richiesta. Da questo possiamo ottenere un'espressione per h
h= log2(s+ 1)−1≈log2s
nlog2n
2 1
32 5
1,024 10
1.048.576 20
Vedremo più tardi come possiamo utilizzare gli alberi binari per contenere i dati in modo che qualsiasi ricerca abbia
al massimo tanti passi quanto l'altezza dell'albero. Pertanto, per gli alberi perfettamente bilanciati, noi
può ridurre notevolmente il tempo di ricerca come dimostra la tabella. Tuttavia, non è sempre
facile creare alberi perfettamente bilanciati, come vedremo anche più tardi.
dimensione(t) {
se ( èVuoto(t) )
ritorna 0
altrimenti restituisci (1 + dimensione(sinistra(t)) + dimensione(destra(t)))
}
Questo processa ricorsivamente l'intero albero, e sappiamo che terminerà perché gli alberi
essere elaborati diventano più piccoli con ogni chiamata e alla fine raggiungeranno un albero vuoto che
restituisce un valore semplice.
37
degli alberi permette quindi agli algoritmi ricorsivi su alberi di operare in modo efficiente semplicemente passando il
puntatore al nodo radice rilevante, piuttosto che dover passare copie complete dell'intero albero.
How data structures and pointers are implemented in different programming languages will
variano, ovviamente, ma l'idea generale è la stessa.
Un albero binario può essere implementato come un record dati per ogni nodo che consiste semplicemente in
valore del nodo e due riferimenti ai nodi figli. PoiMakeTreesemplicemente crea un nuovo dato
registro di quel modulo, e root, left e right semplicemente leggono i contenuti pertinenti di
record. L'assenza di un nodo figlio può essere semplicemente rappresentata da un puntatore nullo.
funzione(int n, albero t) {
// condizione di terminazione e ritorno
.
// dettagli della procedura
.
return function(n-1, t2)
}
38
quindi possiamo fare qualcosa di volte, oppure cercare il elemento, ecc. L'esempio classico è il
funzione fattoriale ricorsiva:
fattoriale(int n) {
se ( n == 0 ) restituisci 1
ritorna n*fattoriale(n-1)
}
Un altro esempio, con due condizioni di terminazione o casi base, è un'implementazione diretta.
della definizione ricorsiva dei numeri di Fibonacci (vedi Appendice A.5):
F(int n) {
se ( n == 0 ) ritorna 0
se ( n == 1 ) ritorna 1
ritorna F(n-1) + F(n-2)
}
anche se questo è un algoritmo estremamente inefficiente per calcolare questi numeri. Esercizio: Mostrare
che la complessità temporale di questo algoritmo è O(2n ), e che esiste un modo diretto
iterative algorithm that has onlyO(n) time complexity. Is it possible to create anO(n)
algoritmo ricorsivo per calcolare questi numeri?
Nella maggior parte dei casi, tuttavia, non dovremo preoccuparci dei contatori, perché i dati pertinenti
structure has a natural end point condition, such asisEmpty(x), that will bring the recursion
a una fine.
39
Capitolo 7
Ora esaminiamo gli Alberi di Ricerca Binaria, che sono un particolare tipo di albero binario che forniscono
un modo efficiente di memorizzare dati che consente di trovare articoli particolari il più rapidamente possibile.
Poi consideriamo ulteriori elaborazioni di questi alberi, ovvero gli alberi AVL e gli alberi B, che
operare in modo più efficiente a scapito della necessità di algoritmi più sofisticati.
Se gli oggetti da cercare sono contrassegnati da chiavi comparabili, si possono ordinare e memorizzare
them in such a way that they aresortedalready. Being ‘sorted’ may mean different things
per chiavi diverse, e quale chiave scegliere è una decisione di design importante.
Nei nostri esempi, le chiavi di ricerca saranno, per semplicità, generalmente numeri interi (così
come numeri di identificazione dello studente), ma altre scelte si verificano in pratica. Ad esempio, il comparabile
le chiavi potrebbero essere parole. In quel caso, la comparabilità si riferisce solitamente all'ordine alfabetico. Se
parole di wanda, scriviamo per significare che precedono in ordine alfabetico. Se
w=letto e t=cielo allora la relazione w<t tiene, ma questo non è il caso se w=letto e
t=abaco. Un esempio classico di una collezione da cercare è un dizionario. Ogni voce di
il dizionario è una coppia composta da una parola e una definizione. La definizione è una sequenza di
parole e simboli di punteggiatura. La chiave di ricerca, in questo esempio, è la parola (a cui un
la definizione è allegata nell'entry del dizionario). Quindi, in modo astratto, un dizionario è una sequenza di
40
voci, dove una voce è una coppia costituita da una parola e la sua definizione. Questo è ciò che conta
dal punto di vista degli algoritmi di ricerca che considereremo. In seguito, noi
dovrà concentrarsi sulle chiavi di ricerca, ma dovrebbe sempre tenere a mente che di solito c'è di solito un
dati di inserimento più sostanziali ad esso associati.
Nota l'uso della parola "astratto" qui. Ciò che intendiamo è che astraiamo o rimuoviamo
qualsiasi dettaglio che è irrilevante dal punto di vista degli algoritmi. Ad esempio, un
il dizionario di solito viene in forma di libro, che è una sequenza di pagine - ma per noi,
La distribuzione delle voci del dizionario nelle pagine è una caratteristica accidentale del dizionario. Tutto
ciò che conta per noi è che il dizionario è una sequenza di voci. Quindi "astrazione" significa
eliminare i dettagli irrilevanti. Per i nostri scopi, solo la chiave di ricerca è importante, quindi noi
ignoreremo il fatto che le voci della collezione saranno tipicamente oggetti più complessi
(come nell'esempio di un dizionario o di una rubrica telefonica).
Nota che dovremmo sempre utilizzare la struttura dati per contenere gli elementi che esegue
il migliore per l'applicazione tipica. Non c'è una risposta facile su quale sia la scelta migliore - il
Devono essere esaminate circostanze particolari e deve essere presa una decisione basata su quelle.
Tuttavia, per molte applicazioni, il tipo di alberi binari che abbiamo studiato nell'ultimo capitolo sono
particolarmente utile qui.
Definizione. Un albero di ricerca binaria è un albero binario che è vuoto oppure soddisfa le seguenti
conditions:
Tutti i valori presenti nel sottoalbero sinistro sono più piccoli di quello della radice.
Tutti i valori che si trovano nel sottoalbero destro sono maggiori di quelli della radice.
Gli alberi di sinistra e di destra sono a loro volta alberi di ricerca binaria.
Quindi questo è solo un particolare tipo di albero binario, con valori dei nodi che sono le chiavi di ricerca.
significa che possiamo ereditare molti degli operatori e degli algoritmi che abbiamo definito per binari generali
alberi. In particolare, gli operatori primitivi MakeTree(v,l,r), root(t), left(t), right(t) e
isEmpty(t) sono gli stessi – dobbiamo solo mantenere l'ordinamento del valore del nodo aggiuntivo.
•Se l'albero dato è vuoto, allora basta assegnare il nuovo valore alla radice e lasciare il
sottoalberi sinistro e destro vuoti.
41
Se l'albero dato è non vuoto, allora inserisci un nodo con valore v come segue:
Se v è minore del valore della radice: inserisci v nel sottoalbero sinistro.
Se v è maggiore del valore della radice: inserisci v nel sotto-albero destro.
Se ifvis è uguale al valore della radice: segnalare un'ipotesi violata.
Pertanto, utilizzando gli operatori primitivi degli alberi binari, abbiamo la procedura:
inserisci(v, bst) {
se ( èVuoto(bst) )
restituisci CreaAlbero(v, AlberoVuoto, AlberoVuoto)
altrimenti se ( v < radice(bst) )
ritorna CreaAlbero(radice(bst), inserisci(v, sinistra(bst)), destra(bst))
else if ( v > root(bst) )
ritorna FaiAlbero(radice(bst), sinistra(bst), inserisci(v, destra(bst)))
altrimenti errore('Errore: assunzione violata nella procedura di inserimento.')
}
che inserisce un nodo con valore in un albero di ricerca binario esistente. Si noti che il nodo
aggiunto è sempre una foglia. L'albero risultante è ancora una volta un albero di ricerca binario.
provato rigorosamente attraverso un argomento induttivo.
Si noti che questa procedura crea un nuovo albero da un dato albero e un nuovo valore.
con il nuovo valore inserito nella posizione giusta. L'albero originale non viene modificato, esso
viene semplicemente ispezionato. Tuttavia, quando l'albero rappresenta un grande database, sarebbe chiaramente
è più efficiente modificare l'albero dato piuttosto che costruire un intero nuovo albero. Questo può
può essere fatto facilmente usando puntatori, in modo simile a come impostiamo le liste collegate. Per il momento,
tuttavia, non ci preoccuperemo di tali dettagli implementativi.
Gli algoritmi possono essere espressi in molti modi. Ecco una descrizione concisa a parole di
algoritmo di ricerca che abbiamo appena delineato:
Nota che una tale descrizione di un algoritmo racchiude sia i passaggi che devono essere svolti
fuori e il motivo per cui questo fornisce una soluzione corretta al problema. Questo modo di descrivere
Gli algoritmi sono molto comuni quando non intendiamo eseguirli su un computer.
42
Quando vogliamo eseguirli, dobbiamo fornire una specifica più precisa, e dovremmo
scrivere normalmente l'algoritmo in pseudocodice, come la seguente procedura ricorsiva:
isIn(valore v, albero t) {
se ( èVuoto(t) )
restituire falso
elseif ( v == radice(t) )
restituisce vero
altrimenti se ( v < radice(t) )
restituisce isIn(v, left(t))
altrimenti
restituire èIn(v, destra(t))
}
Ogni ricorsione restringe la ricerca o al sottoalbero sinistro o a quello destro, a seconda dei casi, riducendo
l'altezza dell'albero di ricerca di uno, quindi l'algoritmo è garantito a terminare eventualmente.
In questo caso, la ricorsione può essere facilmente trasformata in un ciclo while:
isIn(valore v, albero t) {
mentre (non è vuota(t) e (v != radice(t)))
se (v < radice(t) )
t = sinistra(t)
altro
t = a destra(t)
restituisci ( non èVuoto(t) )
}
Qui, ogni iterazione del ciclo while limita la ricerca o al sottoalbero sinistro o a quello destro poiché
appropriato. L'unico modo per uscire dal ciclo è quello di aver trovato il valore richiesto, o solo
avere un albero vuoto rimanente, quindi la procedura deve solo restituire se il finale
l'albero è vuoto.
In pratica, spesso vogliamo avere più di un semplice ritorno vero/falso. Ad esempio,
se stiamo cercando un numero di identificazione studente, di solito vogliamo un puntatore al record completo per quello
studente, non solo una conferma che esistono. In quel caso, potremmo memorizzare un puntatore al record
associato alla chiave di ricerca (ID) in ciascun nodo dell'albero e restituisce il puntatore al record o un null
un puntatore, piuttosto che un semplice vero o falso, quando un elemento viene trovato o meno. Chiaramente,
le strutture ad albero di base di cui abbiamo discusso possono essere elaborate in molti modi diversi
come questo per formare qualunque struttura dati sia più appropriata per il problema in questione, ma,
Come già accennato, possiamo astrarre tali dettagli per gli scopi attuali.
43
compito facile. Il problema è che ci sono molti modi per costruire lo stesso albero di ricerca binaria
per inserimenti successivi.
Come abbiamo visto sopra, gli alberi perfettamente bilanciati raggiungono un'altezza minima per un determinato numero
dei nodi, e si scopre che più un albero è bilanciato, più modi ci sono per costruirlo
Questo è dimostrato nella figura sottostante:
3 2
2
1 3
1
L'unico modo per ottenere l'albero sul lato sinistro è inserire 3, 2, 1 nell'emporio vuoto.
albero in quest'ordine. L'albero a destra, tuttavia, può essere raggiunto in due modi: Inserendo in
l'ordine 2, 1, 3 oppure nell'ordine 2, 3, 1. Idealmente, ovviamente, si utilizzerebbero solo bene bilanciati
alberi per mantenere l'altezza minima, ma non devono essere perfettamente bilanciati per funzionare
migliore degli alberi di ricerca binaria senza restrizioni.
Eseguire calcoli esatti dell'altezza degli alberi non è semplice, quindi non lo faremo.
qui. Tuttavia, se assumiamo che tutti i possibili ordini in cui un insieme di nodi potrebbe essere
se inseriti in un albero di ricerca binario sono ugualmente probabili, allora l'altezza media di un albero di ricerca binario
l'albero si rivela essere O(log2n). Ne consegue che il numero medio di confronti necessari per
cercare un albero di ricerca binario è O(log2 n), che è la stessa complessità che abbiamo trovato per binario
ricerca di un array ordinato. Tuttavia, l'inserimento di un nuovo nodo in un albero di ricerca binario dipende anche
sull'altezza dell'albero e richiede O(log2 n) passi, che è meglio della complessità O(n) di
inserire un elemento nel punto appropriato di un array ordinato.
Interessantemente, l'altezza media di un albero di ricerca binario è decisamente migliore rispetto alla
altezza media di un albero binario generale costituito dagli stessi nodi che non sono stati
integrato in un albero di ricerca binario. L'altezza media di un albero binario generale è in realtà O(n). √
Il motivo di ciò è che c'è una proporzione relativamente grande di alberi binari alti che sono
non alberi di ricerca binaria validi.
Se solo uno dei sottoalberi del nodo non è vuoto, 'sposta in alto' il sottoalbero rimanente.
•Se il nodo ha due sottoalberi non vuoti, trova il nodo 'più a sinistra' che si verifica a destra
sotto-albero (questo è il più piccolo elemento nel sotto-albero destro). Usa questo nodo per sovrascrivere il
44
quello da eliminare. Sostituisci il nodo più a sinistra con il suo sottoalbero destro, se esiste;
altrimenti semplicemente cancellalo.
L'ultima parte funziona perché il nodo più a sinistra nel sottoalbero destro è garantito essere più grande.
più piccolo di tutti i nodi nel sottoalbero sinistro, più piccolo di tutti gli altri nodi nel sottoalbero destro, e
non ha alcun sottotree sinistro. Ad esempio, se eliminiamo il nodo con valore 11 dall'albero in
Figure 6.1, we get the tree displayed in Figure 7.1.
8 8
3 11 3 12
1 6 9 14 1 6 9 14
7 10 12 15 7 10 15
In pratica, dobbiamo trasformare l'algoritmo sopra (specificato a parole) in un modo più dettagliato
algoritmo specificato utilizzando gli operatori primitivi degli alberi binari:
cancella(valore v, albero t) {
se ( èVuoto(t) )
errore('Errore: l'elemento dato non è nell'albero dato')
altrimenti
se ( v < radice(t) ) // elimina dal sottoalbero sinistro
ritorna CreaAlbero(radicе(t), elimina(v,sinistra(t)), destra(t));
altrimenti se ( v > radice(t) //
) elimina dal sottoalbero destro
ritorna FaiAlbero(radice(t), sinistra(t), elimina(v, destra(t)));
altro // l'elemento v da eliminare è root(t)
se ( èVuoto(sinistra(t)) )
restituisci destra(t)
elseif ( èVuoto(destro(t)) )
restituisci sinistra(t)
45
è importante dire esplicitamente quali sono le precondizioni. Spesso è più sicuro iniziare ciascuna
procedura con un controllo per determinare se le precondizioni sono soddisfatte, con un appro-
il messaggio di errore privata prodotto quando non lo sono, ma che può avere un costo di tempo significativo
se la procedura viene chiamata molte volte. Prima, per trovare il nodo più piccolo, abbiamo:
smallestNode(albero t) {
// Precondizione: t è un albero di ricerca binario non vuoto
se ( èVuoto(sinistra(t) )
restituisci radice(t)
altrimenti
restituisci smallestNode(left(t));
}
che utilizza il fatto che, secondo la definizione di un albero di ricerca binario, il nodo più piccolo è spesso
il nodo più a sinistra. Cerca ricorsivamente nel sottoalbero sinistro finché non raggiunge un albero vuoto, a
in quale punto può restituire la radice. Il secondo sotto-algoritmo utilizza la stessa idea:
rimuoviNodoPiuPiccolo(albero t) {
// Precondizione: t è un albero di ricerca binario non vuoto
if ( isEmpty(left(t) )
restituire giusto(t)
altrimenti
ritorna MakeTree(root(t), removeSmallestNode(left(t)), right(t))
}
eccetto che l'albero rimanente viene restituito anziché il nodo più piccolo.
Queste procedure sono ulteriori esempi di algoritmi ricorsivi. In ogni caso, la ricorsione
è garantito che termini, poiché ogni chiamata ricorsiva coinvolge un albero più piccolo, il che significa
che alla fine troveremo ciò che stiamo cercando o raggiungeremo un albero vuoto.
È chiaro dall'algoritmo che la cancellazione di un nodo richiede lo stesso numero di
passaggi come cercare un nodo o inserire un nuovo nodo, cioè l'altezza media del binario
albero di ricerca, oO(log2n) dove n è il numero totale di nodi sull'albero.
èbst(albero t) {
se ( èVuoto(t) )
ritorna vero
altro
return ( allsmaller(left(t),root(t)) and isbst(left(t))
e tutti più grandi(giusto(t),radice(t)) e è bst(destro(t)) )
}
46
tuttipiùpiccoli(albero t, valore v) {
se ( èVuoto(t) )
restituire vero
altrimenti
( (root(t) < v) e allsmaller(left(t),v)
e tutte le dimensioni minori(destro(t),v) )
tuttomaggiore(albero t, valore v) {
se ( èVuoto(t) )
restituisci vero
altro
ritorna ( (root(t) > v) e allbigger(left(t),v) )
e tutte le più grandi(destra(t),v)
}
Tuttavia, l'algoritmo più semplice o più ovvio non è sempre il più efficiente. Esercizio:
identificare cosa è inefficiente in questo algoritmo e formulare un algoritmo più efficiente.
printInOrder(tree t) {
se ( non è vuoto(t) ) {
stampaInOrdine(sinistra(t))
stampa(radice(t))
stampaInOrdine(destro(t))
}
}
Quindi, se la collezione di elementi da ordinare è fornita come un array di dimensione nota n, possono essere
essere stampati in ordine ordinato dall'algoritmo:
ordina(array a di dimensione n) {
t = AlberoVuoto
per i = 0,1,...,n-1
t = inserisci(a[i],t)
stampaInOrdine(t)
}
che inizia con un albero vuoto, inserisce tutti gli elementi in esso usando insert(v,t) per dare un
albero di ricerca binario, e poi li stampa in ordine usando printInOrder(t). Esercizio: modifica
questo algoritmo in modo che invece di stampare i valori ordinati, vengano rimessi nell'originale
array in ordine crescente.
47
7.10 Bilanciamento degli alberi di ricerca binari
Se gli elementi vengono aggiunti a un albero di ricerca binario in ordine casuale, l'albero tende ad essere abbastanza
ben bilanciato con un'altezza non molto più grande di un tronco2n. Tuttavia, ci sono molte situazioni
dove gli elementi aggiunti non sono in ordine casuale, come quando si aggiungono nuovi ID studente. In
nel caso estremo in cui i nuovi elementi vengano aggiunti in ordine crescente, l'albero sarà lungo
diramarsi a destra, con altezza n log2n.
Se tutti gli elementi da inserire in un albero di ricerca binaria sono già ordinati, è diretto-
forward to build a perfectly balanced binary tree from them. One simply has to recursively
costruire un albero binario con l'elemento centrale (cioè, mediano) come radice, il sottoalbero sinistro composto da
degli oggetti più piccoli, e il sottobosco destro composto dagli oggetti più grandi. Questa idea può essere utilizzata
torebalanceany existing binary search tree, because the existing tree can easily be output
in un array ordinato come discusso nella Sezione 7.9. Esercizio: Scrivi un algoritmo che riequilibri
un albero di ricerca binaria in questo modo, e calcolare la sua complessità temporale.
Un altro modo per evitare alberi di ricerca binari sbilanciati è riequilibrarli di tanto in tanto.
tempo usando rotazioni ad albero. Tali rotazioni ad albero sono meglio comprese nel modo seguente: Qualsiasi binario
Un albero di ricerca contenente almeno due nodi può essere chiaramente disegnato in una delle due forme:
where B and D are the required two nodes to be rotated, and A, C and E are binary search
sotto-alberi (ognuno dei quali può essere vuoto). Le due forme sono collegate dall'albero sinistro e dall'albero destro
rotazioni che preservano chiaramente la proprietà dell'albero di ricerca binario. In questo caso, eventuali nodi in
il sotto-albero A verrebbe spostato verso l'alto nell'albero mediante una rotazione a destra, e qualsiasi nodo nel sotto-albero E
sarebbe spostato verso l'alto nell'albero da una rotazione a sinistra. Ad esempio, se la forma a sinistra avesse A che consiste
di due nodi, e C ed E che consistono in un nodo, l'altezza dell'albero verrebbe ridotta
di uno e diventare perfettamente bilanciato tramite una rotazione a destra dell'albero.
Tipicamente, tali rotazioni degli alberi devono essere applicate a molti diversi sotto-alberi di un
albero completo per renderlo perfettamente bilanciato. Ad esempio, se la forma sinistra aveva C composto da due
nodi, e A ed E consistenti di un nodo, l'albero sarebbe bilanciato eseguendo prima
una rotazione a sinistra del sotto-albero A-B-C, seguita da una rotazione a destra dell'intero albero.
pratica, trovando sequenze adatte di rotazioni arboree appropriate per riequilibrare un arbitrario
l'albero di ricerca binaria non è semplice, ma è possibile formulare un bilanciamento sistematico
algoritmi che sono più efficienti rispetto a restituire l'intero albero e ricostruirlo.
48
compromesso tra il tempo necessario per il riequilibrio e il tempo risparmiato grazie all'altezza ridotta
dell'albero, ma in generale ne vale la pena.
Il primo tipo di albero di ricerca binario autobilanciante era l'albero AVL (prende il nome da...
inventori G.M. Adelson-Velskii e E.M. Landis). Questi mantengono la differenza di altezze
dei due sotto-alberi di tutti i nodi essere al massimo uno. Ciò richiede che l'albero sia periodicamente
ri-equilibrato eseguendo una o più rotazioni ad albero come discusso sopra, ma la complessità
l'inserimento, la cancellazione e la ricerca rimangono a O(log2n).
L'idea generale è di tenere traccia del fattore di bilanciamento per ciascun nodo, che è l'altezza
dell'albero sinistro meno l'altezza dell'albero destro. Per definizione, tutti i nodi in un
L'albero AVL avrà un fattore di bilanciamento nell'intervallo intero [-1, 1]. Tuttavia, l'inserimento o la cancellazione
di un nodo potrebbe lasciare che in un’intervallo più ampio [−2,2] richiedendo una rotazione dell'albero per riportarlo indietro
in forma AVL. Esercizio: Trova alcuni algoritmi adatti per eseguire alberi AVL in modo efficiente
rotazioni. Confrontale con altri approcci di auto-bilanciamento come gli alberi rosso-neri.
7.12 Alberi B
L'AB-tree è una generalizzazione di un albero di ricerca binario auto-bilanciante in cui ogni nodo può contenere
più di una chiave di ricerca e avere più di due figli. La struttura è progettata per
consente un'autoregolazione più efficiente e offre vantaggi particolari quando i dati del nodo sono necessari
da essere conservati in memoria esterna come unità disco. La definizione standard (Knuth) è:
Sembra non esserci una risposta definitiva alla domanda su cosa stia per "B" in "B-Tree".
Certamente non è "Binario", ma potrebbe benissimo essere "bilanciato", "ampio" o "cespuglioso".
o anche "Boeing" perché sono stati inventati da persone del Boeing Research Labs.
La rappresentazione standard dell'esempio di ordine semplice 4 con 9 chiavi di ricerca sarebbe:
Le chiavi di ricerca contenute in ciascun nodo sono ordinate (ad esempio, 1, 2, 5 nell'esempio), e il non foglia
le chiavi di ricerca del nodo (cioè, gli elementi 8 e 17 nell'esempio) agiscono come valori di separazione per dividere
49
il contenuto dei suoi sotto-alberi in modo molto simile al valore di un nodo in una ricerca binaria
l'albero separa i valori contenuti nei suoi due sotto-alberi. Ad esempio, se un nodo ha 3 nodi figli
(o sottoalberi) allora deve avere 2 valori di separazione s1 e s2. Tutti i valori nel più a sinistra
sottoalbero sarà minore di s1, tutti i valori nel sottoalbero centrale saranno tra s1 e s2, e tutti
I valori nell'albero più a destra saranno maggiori di s2. Questo consente l'inserimento e la ricerca.
procedere dalla radice verso il basso in modo simile agli alberi di ricerca binari.
La restrizione sul numero di bambini deve essere compresa tra m/2 e m significa che il migliore
l'altezza di un albero mB contenente n chiavi di ricerca è logm e l'altezza del caso peggiore
è logm/2 n. Chiaramente i costi di inserimento, eliminazione e ricerca saranno tutti proporzionali a
l'altezza dell'albero, come in un albero di ricerca binaria, che li rende molto efficienti. Il requisito
che tutti i nodi foglia sono allo stesso livello significa che gli B-alberi sono sempre bilanciati e quindi
avere un'altezza minima, anche se il riequilibrio sarà spesso necessario per ripristinare quella proprietà dopo
inserimenti e cancellazioni.
L'ordine di un B-tree è tipicamente scelto per ottimizzare una particolare applicazione e implementare
per mantenere le condizioni della definizione dell'albero B, spesso i nodi non foglia devono
essere diviso o unito quando nuovi elementi vengono inseriti o eliminati dall'albero (ed è per questo che
c'è un fattore di due tra il numero minimo e massimo di bambini), andrebal-
L'assegnazione è spesso necessaria. Questo rende gli algoritmi di inserimento e cancellazione un po' più
più complicato rispetto agli alberi di ricerca binaria. Un vantaggio degli B-tree rispetto agli alberi binari auto-bilanciati
Gli alberi di ricerca, tuttavia, presentano il vantaggio che l'intervallo dei nodi figli significa che il bilanciamento è necessario meno frequentemente.
frequentemente. Uno svantaggio è che potrebbe esserci un maggiore spreco di spazio perché i nodi raramente
essere completamente pieni. Ci sono anche i costi per mantenere gli oggetti all'interno di ogni nodo ordinati, e
dover cercare tra di loro, ma per ordini ragionevolmente piccoli, quel costo è basso. Esercizio:
trova alcuni algoritmi adatti per l'inserimento, la cancellazione e il riequilibrio degli alberi B.
50
Capitolo 8
Definizione. Un albero binario è completo se ogni livello, eccetto forse l'ultimo, è completamente
riempito, e tutte le foglie dell'ultimo livello sono posizionate il più a sinistra possibile.
Intuitivamente, un albero binario completo è quello che può essere ottenuto riempiendo i nodi partendo da
con la radice, e poi ogni livello successivo a turno, sempre da sinistra, fino a quando non ci si esaurisce di
I nodi. Gli alberi binari completi hanno sempre un'altezza minima per le loro dimensioni n, ovvero log2n, e
sono sempre perfettamente bilanciati (ma non ogni albero perfettamente bilanciato è completo nel senso
della definizione sopra). Inoltre, e ciò è ancora più importante, è possibile che possano essere archiviati
in modo diretto negli array, dall'alto verso il basso e da sinistra a destra, come nel seguente esempio:
a[1]
a[2] a[3]
Per gli alberi binari completi, questi array forniscono rappresentazioni molto compatte.
Nota che questa volta abbiamo scelto di iniziare l'array con l'indice 1 anziché 0. Questo
ha diversi vantaggi computazionali. I nodi sul livello hanno indici 2io ,· · · ,2 io+1-1.
Il livello di un nodo con indice iisblog2ic, cioè, log2arrotondato per difetto. I bambini di un
I nodi con indice i, se esistono, hanno indici 2i e 2i + 1. Il genitore di un figlio con indice i
ha indexi/2 (utilizzando la divisione intera). Questo consente i seguenti semplici algoritmi:
boolean isRoot(int i) {
restituisci i == 1
}
51
int livello(int i) {
ritorna log(i)
}
int genitore(int i) {
restituisci i / 2
}
int sinistra(int i) {
ritorna 2 * i
}
int destra(int i) {
restituisci 2 * i + 1
}
52
In alternativa, si potrebbe definire un albero heap come un albero binario completo tale che la priorità di
ogni nodo è maggiore (o uguale) a quello di tutti i suoi discendenti. Oppure, come un albero binario completo
albero per cui le priorità diventano sempre più piccole lungo ogni percorso verso il basso nell'albero.
La differenza più ovvia tra un albero heap binario e un albero di ricerca binario è che
il numero più grande ora si trova alla radice piuttosto che al nodo più a destra. In secondo luogo,
whereas with binary search trees, the left and right sub-trees connected to a given parent
i nodi svolgono ruoli molto diversi, sono intercambiabili negli alberi heap binari.
Tre esempi di alberi binari che sono alberi heap validi sono:
96
9 9
90 70
8 8 3 2
80 75 42 60
1 3 1
17 44 10 72 14
6 6 6
4 3 5 5 4
5 4 3 3
il primo perché 5>4 viola l'ordine di priorità richiesto, il secondo perché non lo è
perfettamente equilibrato e quindi non completo, e il terzo perché non è completo a causa di
il nodo nell'ultimo livello non è il più a sinistra possibile.
53
boolean heapEmpty(array heap, int n) {
restituire n == 0
}
Inserire e eliminare nodi dell'albero heap è anch'esso semplice, ma non proprio così facile.
Poiché teniamo sempre traccia dell'ultima posizione nell'albero che è stata riempita finora, noi
può facilmente inserire un nuovo elemento nella posizione n+1, a condizione che ci sia ancora spazio nell'array,
e incremento. L'albero risultante sarà ancora un albero binario completo, ma l'albero heap
la proprietà di ordinamento della priorità potrebbe essere stata violata. Pertanto, potremmo dover 'far salire' il
nuovo elemento in una posizione valida. Questo può essere fatto facilmente confrontando la sua priorità con
quello del suo genitore, e se il nuovo elemento ha una priorità superiore, allora viene scambiato con il suo
genitore. Potremmo dover ripetere questo processo, ma una volta che raggiungiamo un genitore che ha un valore più alto o
priorità equivalente, possiamo fermarci perché sappiamo che non possono esserci elementi di priorità inferiore più in alto
l'albero. Quindi un algoritmo che inserisce un nuovo nodo dell'albero heap con priorità p è:
54
Note that thisinsertalgorithm does not increment the heap sizen– that has to be done
separately by whatever algorithm calls it.
L'inserimento di un nodo richiede al massimo O(log2n) passi, perché il numero massimo di volte
potremmo dover 'far salire' il nuovo elemento è l'altezza dell'albero che è log2n.
To use a binary heap tree as a priority queue, we will regularly need to delete the root, i.e.
rimuovere il nodo con la priorità più alta. Ci rimarrà quindi qualcosa che non è un
Albero binario in generale. Tuttavia, possiamo facilmente trasformarlo di nuovo in un albero binario completo prendendo
il nodo nella posizione 'ultima' e usandolo per riempire la nuova vacanza alla radice. Tuttavia, mentre
con l'inserimento di un nuovo elemento, la proprietà dell'albero heap (ordinamento di priorità) potrebbe essere violata. In
in quel caso, dovremo 'far scendere' la nuova radice confrontandola con entrambi i suoi figli
e scambiandolo con il più grande. Questo processo viene poi ripetuto fino a quando il nuovo elemento radice
ha trovato un luogo valido. Pertanto, un algoritmo adatto è:
heap[1] = heap[n]
bubbleDown(1, heap, n-1)
}
}
Un processo simile può essere applicato anche se dobbiamo eliminare un altro nodo dall'albero heap.
ma in quel caso potremmo dover 'far risalire' l'ultimo nodo spostato piuttosto che farlo scendere.
Poiché l'albero heap originale è ordinato, gli elementi dovranno essere solo spostati verso l'alto o verso il basso.
mai entrambi, quindi possiamo semplicemente chiamare entrambi, perché nessuna delle procedure cambia nulla se è
non necessario. Pertanto, un algoritmo che elimina qualsiasi nodo da un albero heap è:
heap[i] = heap[n]
bubbleUp(i,heap,n-1)
bollaGiù(i,montagna,n-1)
}
}
Il processo di discesa a bolle è più difficile da implementare rispetto al processo di salita a bolle, perché un nodo
può avere nessun, un o due figli, e questi tre casi devono essere gestiti in modo diverso. In
nel caso di due bambini, è fondamentale che quando entrambi i bambini hanno una priorità più alta rispetto a
dato nodo, è quello con la priorità più alta che viene spostato verso l'alto, altrimenti il loro ordinamento di priorità sarà
essere violato. Pertanto abbiamo:
55
bubbleDown(int i, array heap, int n) {
se ( sinistra(i) > n ) // nessun bambino
restituire
altrimenti se ( destra(i) > n ) // solo figlio sinistro
se ( heap[i] < heap[left(i)] )
scambia heap[i] e heap[left(i)]
altro due bambini
se ( heap[left(i)] > heap[right(i)] e heap[i] < heap[left(i)] ) {
scambia heap[i] e heap[left(i)]
bubbleDown(left(i),heap,n)
}
elseif ( heap[i] < heap[right(i)] ) {
scambia heap[i] e heap[right(i)]
bubbleDown(destro(i),heap,n)
}
}
}
Allo stesso modo in cui l'algoritmo di inserimento non incrementa la dimensione dell'heap, questo elimina
l'algoritmo non decrementa la dimensione dell'heap - questo deve essere fatto separatamente da qualsiasi cosa
l'algoritmo lo chiama. Nota anche che questo algoritmo non tenta di essere giusto nel senso che
se due o più nodi hanno la stessa priorità, non è necessariamente quello che ha aspettato
il più lungo verrà rimosso per primo. Tuttavia, questo fattore potrebbe essere facilmente risolto, se necessario, da
tenere traccia degli orari di arrivo e utilizzare ciò nei casi di priorità uguale.
Come per l'inserimento, la cancellazione richiede al massimo O(log2n) passaggi, perché il numero massimo
di volte potrebbe dover risalire o scendere l'elemento di sostituzione è l'altezza di
l'albero che è legna2n.
a[1] scambiandoli con il più grande dei loro figli fino a quando non sono posizionati a
una foglia, o finché i loro figli sono entrambi più piccoli, otteniamo un albero heap valido.
Considera un semplice esempio di array di elementi da cui deve essere costruito un albero heap:
5 8 3 9 1 4 7 6 2
Possiamo iniziare disegnando semplicemente l'array come un albero e vedere che le ultime 5 voci (quelle con
gli indici maggiori di 9/2 = 4) sono foglie dell'albero, come segue:
56
5
8 3
9 1 4 7
6 2
Quindi l'algoritmo di riordino inizia a spingere verso il basso a[n/2] = a[4] = 9, il che trasforma
non è necessario, quindi l'array rimane lo stesso. Nexta[3] =3 viene spostato in basso,
scambiando con a[7] = 7, dando:
5 8 7 9 1 4 3 6 2
5 9 7 8 1 4 3 6 2
Finalmente, a[1] = 5 viene fatto scendere, scambiando con a[2] = 9, per dare per primo:
9 5 7 8 1 4 3 6 2
9 8 7 5 1 4 3 6 2
9 8 7 6 1 4 3 5 2
heapify(array a, int n) {
per ( i = n/2 ; i > 0 ; i-- )
bubbleDown(i,a,n)
}
La complessità temporale di questo algoritmo di creazione dell'albero heap potrebbe essere calcolata come segue: Esso
potenzialmente scende a bn/2c oggetti, vale a dire quelli con indici 1, . . . , bn/2c. Il massimo
il numero di passaggi di bubble down per ciascuno di quegli elementi è l'altezza dell'albero, che è log2n,
e ogni passo prevede due confronti - uno per trovare il nodo figlio di massima priorità e uno
per confrontare l'elemento con quel nodo figlio. Quindi il numero totale di confronti coinvolti è
al massimo (n/2).log2n.2 =nlog2n, che è lo stesso di ciò che avremmo inserendo l'array
elementi uno alla volta in un albero inizialmente vuoto.
In fact, this is a good example of a situation in which a naive counting of loops and tree
heights sovrastima la complessità temporale. Questo perché il numero di passaggi di bubble down
57
sarà di solito inferiore all'altezza completa dell'albero. In effetti, a ogni livello man mano che scendi il
albero, ci sono più nodi e meno passaggi potenziali di discesa a bolle, quindi il numero totale di
le operazioni saranno in realtà molto meno del previsto2 n. Per essere sicuri della classe di complessità, noi
è necessario eseguire un calcolo più accurato. Ad ogni livello di un albero di altezza ci saranno
essere 2inodi, con al massimo h−i passi di discesa della bolla, ognuno con 2 confronti, quindi il totale
il numero di confronti per un albero di altezza sarà in media
h h h
C(h) = h−i j
2io (h−i) = 2h = 2h
X X 2h−io X 2j
i=0 i=0 j=0
La somma finale converge a 2 man mano che h aumenta (vedi Appendice A.4), quindi per grandi h abbiamo
∞ j
C(h)≈2 h h h+1
X 2j = 2 .2 = 2 ≈n
j=0
e il caso peggiore non sarà più del doppio di ciò. Pertanto, il numero totale di operazioni
isO(2h+1) =O(n), meaning that the complexity class ofheapifyis actuallyO(n), which is
meglio di O(n log)2n) complessità dell'inserimento degli oggetti uno alla volta.
1. Sposta uno alla volta tutti gli oggetti dall'albero heap più piccolo nell'albero heap più grande.
utilizzando l'algoritmo standard di inserimento. Questo comporterà lo spostamento di O(n) elementi, e ciascuno
di loro dovranno essere portati a costo O(log2n), dando una complessità temporale complessiva
diO(nlog2n).
2. Sposta ripetutamente gli ultimi elementi da un albero heap all'altro utilizzando lo standard
inserisci algoritmo, fino a quando il nuovo albero binario makeTree(0,t,s) è completo. Quindi sposta
l'ultimo elemento del nuovo albero per sostituire la radice fittizia "0" e farlo scendere.
radice. Il modo migliore per farlo dipenderà dalle dimensioni dei due alberi, quindi questo algoritmo
non è del tutto semplice. In media, circa la metà degli articoli nell'ultimo livello di uno
l'albero dovrà essere spostato e riempito, quindi ci saranno O(n) movimenti, ciascuno con un costo di
O(log2 n), dando nuovamente una complessità temporale complessiva di O(n log2 n). Tuttavia, il reale
il numero di operazioni richieste sarà, in media, molto inferiore rispetto all'approccio precedente,
di un fattore di circa quattro, quindi questo approccio è più efficiente, anche se il
l'algoritmo è più complesso.
58
Se i due alberi binari heap sono tali che sono richiesti molto pochi spostamenti per il secondo
l'approccio, allora potrebbe sembrare una scelta migliore rispetto al terzo approccio.
However,makeTreewill itself generally be anO(n) procedure if the trees are array-based,
anziché basati su puntatori, come di solito sono per gli alberi heap binari. Quindi, per basati su array
nei heap binari di dimensioni simili, il terzo approccio è solitamente il migliore.
Se gli alberi heap da unire hanno dimensioni molto diverse n e m < n, il primo approccio
avrà complessità temporale complessiva O(mlog2n), che potrebbe essere più efficiente di un O(n)
approccio ifm n. In pratica, un buon algoritmo di merge di uso generale controllerebbe il
le dimensioni dei due alberi e utilizzale per determinare il miglior approccio da applicare.
Un albero binomiale di ordine k ha un nodo radice con figli che sono radici di alberi binomiali.
di ordini k−1, k−2, ..., 2, 1, 0 (in quest'ordine).
Quindi, un albero binomiale di ordine k ha altezza k, contiene 2knodi, e è costruito in modo triviale
attaccando un albero binomiale di ordine k−1 come il figlio sinistro più estremo di un altro albero binomiale di ordine k−1
albero. Gli alberi binomiali di ordine 0, 1, 2 e 3 assumono la forma:
Ogni albero binomiale costitutivo deve soddisfare la proprietà di ordinamento di priorità, cioè ogni nodo
deve avere una priorità inferiore o uguale a quella del suo genitore.
59
La struttura di tale cumulo è facilmente comprensibile notando che un albero binomiale di ordine k
contiene esattamente 2knodi, e un mucchio binomiale può contenere solo zero o un albero binomiale di
ogni ordine, quindi il numero totale di nodi in un Binomial Heap deve essere
∞
n= bk 2k bk∈[0,1]
X
k=0
dovekspecifica il numero di alberi di ordine k. Quindi c'è una corrispondenza uno a uno tra
la struttura del cumulo binomiale e la rappresentazione binaria standard del numero n, e
Poiché la rappresentazione binaria è chiaramente unica, anche la struttura dell'heap binomiale lo è.
il numero massimo di alberi in un heap con nnodi quindi è uguale al numero di cifre quando
nis scritto in binario senza zeri iniziali, cioè log2n+1. L'heap può essere memorizzato in modo efficiente
come una lista collegata di nodi radice ordinati in ordine crescente di ordine dell'albero.
L'operazione più importante per i monticelli binomiali è la fusione, perché può essere utilizzata come
un sotto-processo per la maggior parte delle altre operazioni. Sottostante a ciò è la fusione di due alberi binomiali
di ordine j in un albero binomiale di ordine j+1. Per definizione, ciò si ottiene aggiungendo uno di
quegli alberi come il sottobosco più a sinistra della radice dell'altro, e la preservazione della priorità
l'ordinamento richiede semplicemente che sia l'albero con la radice di massima priorità a fornire la
radice dell'albero combinato. Questo ha chiaramente una complessità temporale O(1). Quindi unendo due interi
i cumuli binomiali si ottengono unendo gli alberi costitutivi ogni volta che ce ne sono due di essi
stessa sequenza, in modo sequenziale analogo all'addizione di due numeri binari. In questo
In questo caso, la complessità di inserimento O(1) sarà moltiplicata per il numero di alberi, che è O(log2n),
quindi la complessità temporale complessiva di unione è O(log2n). Questo è meglio della complessità O(n)
della fusione di heap binari che può essere ottenuta concatenando gli array heap e utilizzando il
Algoritmo di heapify O(n).
L'inserimento di un nuovo elemento in un heap binomiale esistente può essere facilmente effettuato trattando
il nuovo elemento come un mucchio binomiale costituito da un singolo nodo (cioè, un albero di ordine zero),
and merging that using the standard merge algorithm. The average time complexity of that
insertis given by computing the average number ofO(1) tree combinations required. The
la probabilità di aver bisogno della combinazione zero ordine è 0,5, la probabilità di aver bisogno di un secondo
la combinazione è 0.52 , e il terzo è 0,53 , e così via, che sommano a uno. Quindi l'inserimento ha
Complessità temporale O(1) complessiva. È migliore di O(log2n) complessità dell'inserimento in
un heap binario standard.
Creare un intero nuovo heap binomiale da zero può essere raggiunto utilizzando l'inserimento O(1)
processa ciascuno degli elementi, dando una complessità temporale complessiva di O(n). In questo caso, ci
non c'è un processo migliore, quindi heapify qui ha la stessa complessità temporale dell'algoritmo heapify
per heap binari.
Un'altra operazione importante nell'heap in pratica è quella di aggiornare l'heap dopo un incremento.
ing un nodo priorità. Per gli heap binari standard, ciò richiede semplicemente l'applicazione del solito
processo bubble-up con O(log 2n) complessità. Chiaramente, un processo simile può essere utilizzato in bino-
cumuli mial, e questo sarà anche di O(log2n) complessità.
Il nodo con la priorità più alta in un heap binomiale sarà chiaramente il nodo radice con la priorità più alta,
e un puntatore a questo può essere mantenuto da ogni operazione di aggiornamento dell'heap senza aumentare il
La complessità dell'operazione. Servire l'elemento di massima priorità richiede di eliminare il massimo
il nodo di priorità dall'albero degli ordini in cui appare e che lo romperà in un altro
un mucchio binomiale composto da alberi di tutti gli ordini da 0 a j-1. Tuttavia, quegli alberi possono
può essere facilmente fuso di nuovo nell'heap originale utilizzando l'algoritmo di fusione standard, con il
60
complessità di unione standard di O(log2n). Cancellare i nodi non radice può essere fatto anche con
le operazioni esistenti aumentando la priorità del nodo rilevante all'infinito, risalendo e
utilizzando l'operazione di eliminazione della radice, di nuovo con O(log2n) complessità globale. Quindi, la complessità
di cancellazione è sempre O(log2n).
Esercizio: Trova versioni in pseudocodice degli algoritmi di unione, inserimento e cancellazione per i binomiali.
fagotti e vedere esattamente come si evolvono le loro complessità temporali.
61
Esercizio: Trova versioni in pseudocodice delle varie operazioni dell'heap di Fibonacci e lavora
scoprire come i numeri di Fibonacci siano coinvolti nel calcolo delle loro complessità temporali.
62
Capitolo 9
Ordinamento
per i = 0,...,n-1
stampa(a[i])
stamperemmo gli oggetti in ordine crescente. Se gli oggetti sono memorizzati in una lista collegata, noi
ci si aspetta che la prima voce sia la più piccola, la successiva la seconda più piccola, e così via. Spesso,
strutture più complicate come gli alberi di ricerca binaria o gli alberi a heap sono utilizzate per ordinare il
elementi, che possono poi essere stampati o scritti in un array o in una lista collegata, come desiderato.
Ordinare è importante perché avere gli oggetti in ordine rende molto più facile trovare un dato
voce, come l'articolo più economico o il file corrispondente a un particolare studente. È quindi
strettamente correlato al problema della ricerca, come abbiamo visto con la discussione sugli alberi di ricerca binaria.
Se l'ordinamento può essere fatto in anticipo (offline), questo consente un accesso più rapido ai dati richiesti.
item, which is important because that often has to be done on the fly (on-line). We have
già visto che, avendo gli elementi dei dati memorizzati in un array ordinato o in un albero di ricerca binaria,
possiamo ridurre la complessità media (e nel caso peggiore) della ricerca di un particolare elemento a
O(log2n) passi, mentre sarebbero O(n) passi senza ordinamento. Quindi, se dobbiamo spesso cercare
Per gli articoli in alto, vale la pena di ordinare prima l'intera collezione. Immagina di usare un dizionario
o rubrica telefonica in cui le voci non appaiono in un qualche ordine logico conosciuto.
Ne consegue che gli algoritmi di ordinamento sono strumenti importanti per i progettisti di programmi. Diversi
Gli algoritmi sono adatti a diverse situazioni, e vedremo che non esiste un 'migliore' ordinamento.
algoritmo per tutto, e quindi un certo numero di essi sarà introdotto in questo modulo.
Vale la pena notare che saremo lontani dal coprire tutti gli algoritmi di ordinamento esistenti - in effetti,
il campo è ancora molto vivo e ci sono sviluppi nuovi che avvengono continuamente. Tuttavia,
63
le strategie generali possono ora essere considerate ben comprese, e la maggior parte delle ultime
i nuovi algoritmi tendono ad essere derivati semplicemente modificando principi esistenti, anche se noi ancora
non hanno misure accurate delle prestazioni per alcuni algoritmi di ordinamento.
ordinamento per enumerazione Considera tutti gli articoli. Se sappiamo che ci sono N articoli che sono
più piccolo di quello che stiamo attualmente considerando, allora il suo finale
La posizione sarà al numero N + 1.
ordinamento per scambio Se due elementi risultano fuori ordine, scambiali. Ripeti
fino a quando tutti gli articoli sono in ordine.
ordinamento per selezione Trova l'oggetto più piccolo, mettilo in prima posizione, trova il più piccolo
degli oggetti rimanenti, mettilo al secondo posto . . .
ordinamento per inserimento Prendi gli oggetti uno alla volta e inseriscili in un inizialmente
struttura dati vuota in modo che la struttura dati continui a
essere ordinati in ogni fase.
dividi e conquista Dividi ricorsivamente il problema in sottoproblemi più piccoli fino a quando non
just have single items that are trivial to sort. Then put the sorted
i 'pezzi' insieme in un modo che preserva l'ordinamento.
Tutte queste strategie si basano sul confrontare gli oggetti e poi riordinarli di conseguenza.
Questi sono conosciuti come algoritmi di ordinamento basati su confronto. In seguito considereremo altri algoritmi non-
algoritmi basati sul confronto che sono possibili quando abbiamo conoscenze pregresse specifiche su
gli elementi che possono verificarsi, o restrizioni sulla gamma di elementi che possono verificarsi.
Le idee sopra sono basate sull'assunzione che tutti gli oggetti da ordinare si adatteranno in
la memoria interna del computer, motivo per cui vengono spesso definiti interni
algoritmi di ordinamento. Se l'intero insieme di elementi non può essere memorizzato nella memoria interna in un'unica
tempo, diverse tecniche devono essere utilizzate. Ogni giorno, data la crescente potenza e memoria
rispetto ai computer, lo storage esterno sta diventando molto meno comunemente necessario quando si ordinano, quindi noi
non considererà gli algoritmi di ordinamento esterno in dettaglio. Basta dire che generalmente funzionano per
dividere l'insieme di oggetti in sottoinsiemi contenenti quanti più elementi possibile in una volta
tempo, ordinando ogni sottoinsieme a turno, e poi unendo con cura i risultati.
64
avere tutte le informazioni necessarie per ordinare una collezione arbitraria di oggetti. Poi possiamo vedere
quanto bene alcuni algoritmi di ordinamento si confrontano con quel limite inferiore teorico.
In generale, domande di questo tipo sono piuttosto difficili, a causa della necessità di considerare tutto
possible algorithms. In fact, for some problems, optimal lower bounds are not yet known.
Un esempio importante è il cosiddetto Problema del Commesso Viaggiatore (TSP), per il quale tutti
gli algoritmi, noti per fornire la corretta soluzione del percorso più breve, sono estremamente ineffi-
sciocco nel peggiore dei casi (molti al punto di essere inutili nella pratica). In questi casi, uno
generalmente deve rilassare il problema per trovare soluzioni che sono probabilmente approssimativamente corrette.
Per il TSP, è ancora un problema aperto se esista un algoritmo fattibile che sia
garantito di dare il percorso esatto più breve.
Per gli algoritmi di ordinamento basati su confronti, tuttavia, si scopre che un limite inferiore stretto
il vincolo esiste. Chiaramente, anche se la raccolta di oggetti fornita è già ordinata, dobbiamo comunque
controlla tutti gli elementi uno alla volta per vedere se sono nell'ordine corretto. Pertanto, il più basso
il limite deve essere almeno n, il numero di elementi da ordinare, poiché abbiamo bisogno di almeno n passi per
esamina ogni elemento. Se conoscevamo già un algoritmo di ordinamento che funziona in n passi, allora
potremmo smettere di cercare un algoritmo migliore: sarebbe sia un limite inferiore che un limite superiore
vincolato al numero minimo di passi, e quindi a un limite esatto. Tuttavia, come vedremo
brevemente, nessun algoritmo può effettivamente richiedere meno di O(nlog2n) confronti nel peggiore
caso. Se, inoltre, possiamo progettare un algoritmo che funziona in O(nlog2n) passi, poi noi faremo
abbiamo ottenuto un limite esatto. Inizieremo dimostrando che ogni algoritmo ha bisogno di
almeno O(nlog2n) confronti.
Per cominciare, supponiamo di avere solo tre elementi, i, j e k. Se abbiamo trovato
se i≤j e j≤k, allora sappiamo che l'ordine ordinato è: i,j,k. Quindi ci sono voluti due
comparazioni per scoprirlo. In alcuni casi, tuttavia, è chiaro che avremo bisogno di tanti quanti ne serviranno
tre confronti. Ad esempio, se i primi due confronti ci dicono che i > j e j ≤ k, allora
sappiamo che jis è il più piccolo dei tre elementi, ma non possiamo dire da queste informazioni
comeioedkrelate. È necessaria un terza comparazione. Quindi qual è il numero medio e peggiore
di confronti che sono necessari? Questo può essere determinato meglio dall'apposito albero decisionale,
dove teniamo traccia delle informazioni raccolte finora e contiamo il numero di confronti
necessario. L'albero decisionale per il esempio dei tre elementi di cui stavamo discutendo è:
i <= j
sì no
j <= k i <= k
sì no sì no
Quindi, cosa possiamo dedurre da questo riguardo al caso generale? L'albero decisionale sarà ovviamente
sarà sempre un albero binario. È anche chiaro che la sua altezza ci dirà quante comparazioni avranno luogo.
essere necessario nel peggior caso, e che la lunghezza media di un percorso dalla radice a una foglia
ci darà il numero medio di confronti richiesti. Le foglie dell'albero decisionale sono
65
tutti i possibili risultati. Questi sono dati dai diversi possibili ordini che possiamo avere su n
elementi, quindi stiamo chiedendo in quanti modi è possibile disporre gli elementi. Il primo elemento può
può essere qualsiasi degli n elementi, il secondo può essere qualsiasi degli n−1 elementi rimanenti, e così via, quindi
il loro numero totale è n(n−1)(n−2)· · ·3·2·1 =n!. Pertanto vogliamo sapere l'altezza di
un albero binario che può ospitare fino a n! foglie. Il numero di foglie di un albero di
l'altezza è al massimo 2h , quindi vogliamo trovare h tale che
2h≥n! ohr≥log2(n!)
Esistono numerose espressioni approssimative che sono state derivate per il log.2(n!) per n grande,
ma hanno tutti lo stesso termine dominante, vale a dire nlog2n. (Ricorda che, quando si parla
riguardo alla complessità temporale, ignoriamo eventuali termini sub-dominanti e fattori costanti.) Quindi,
nessun algoritmo di ordinamento basato sul confrontare gli elementi può avere un caso medio o peggiore migliore
prestazioni migliori rispetto all'utilizzo di un numero di confronti che è approssimativamente nlog2nfor
largen.
Rimane da vedere se questoO(nlog2n) la complessità può effettivamente essere raggiunta nella pratica.
Per fare ciò, dovremmo esibire almeno un algoritmo con questo comportamento prestazionale.
(e convincerci che abbia davvero questo comportamento). Infatti, tra poco vedremo
ci sono diversi algoritmi con questo comportamento.
Procederemo ora esaminando a turno un numero di algoritmi di ordinamento di complessità crescente.
sophisticazione, che coinvolge le varie strategie elencate sopra. Il modo in cui funzionano dipende
su che tipo di struttura dati contiene gli elementi che desideriamo ordinare. Iniziamo con approcci
che lavorano con array semplici, per poi passare all'uso di strutture dati più complesse che
portare a algoritmi più efficienti.
Il Bubble Sort segue l'approccio dell'ordinamento per scambio. È molto facile da implementare, ma tende a
essere particolarmente lento da eseguire. Supponiamo di avere un array di dimensione n che desideriamo ordinare. Bubble
Il sort inizia confrontando a[n-1] con a[n-2] e li scambia se sono nell'ordine sbagliato.
Confronta a[n-2] con a[n-3] e li scambia se necessario, e così via. Questo significa
che una volta che raggiunge a[0], l'entrata più piccola sarà nel posto corretto. Poi inizia da
di nuovo, confrontando coppie di 'vicini', ma lasciando l'ingresso zero da solo (che è
conosciuto per essere corretto). Dopo essere tornato di nuovo davanti, la seconda voce più piccola sarà
in posizione. Continua a fare 'passaggi' sull'array finché non è ordinato. Più in generale, al i-esimo
Il metodo Bubble Sort confronta le voci vicine 'dalla parte posteriore', scambiandole quando necessario.
L'elemento con l'indice più basso che viene confrontato con il suo vicino a destra è isa[i-1]. Dopo il
Nella fase i, le voci a[0],...,a[i-1] sono nella loro posizione finale.
A questo punto vale la pena introdurre un semplice ‘caso di test’ di sizen = 4 per dimostrare come
i vari algoritmi di ordinamento funzionano:
4 1 3 2
Il Bubble Sort inizia confrontando a[3]=2 con a[2]=3. Poiché non sono in ordine, scambia.
loro, dando 4 1 2 3. Poi confronta a[2]=2 con a[1]=1. Poiché sono in ordine,
li lascia dove sono. Poi confronta a[1]=1 con a[0]=4, e quelli non sono in
ordine ancora una volta, quindi devono essere scambiati. Otteniamo 1 4 2 3. Nota che il più piccolo
l'elemento ha raggiunto il suo posto finale. Questo accadrà sempre dopo che il Bubble Sort avrà completato il suo primo
passare sopra l'array.
66
Ora che l'algoritmo ha raggiunto l'entrata zero, ricomincia da dietro, confrontando
a[3]=3 con a[2]=2. Questi valori sono in ordine, quindi non succede nulla. (Nota che questi
i numeri sono stati confrontati prima - non c'è nulla in Bubble Sort che lo impedisca di
confronti ripetuti, motivo per cui tende ad essere piuttosto lento!) Poi confronta a[2]=2
anda[1]=4. Questi non sono in ordine, quindi devono essere scambiati, dando 1 2 4 3. Poiché
sappiamo già che a[0] contiene l'elemento più piccolo, lo lasciamo da solo, e il secondo passaggio
è finito. Nota che ora anche la seconda voce più piccola è in posizione.
L'algoritmo ora inizia il terzo e ultimo passaggio, confrontando a[3]=3 e a[2]=4. Di nuovo
these are out of order and have to be swapped, giving 1 2 3 4 . Since it is known that
a[0]anda[1]contengono già gli articoli corretti, non vengono toccati. Inoltre, il
Il terzo elemento più piccolo è ora al suo posto, il che significa che il quarto più piccolo deve essere corretto.
quindi l'intero array è ordinato.
It is now clear that Bubble Sort can be implemented as follows:
Il ciclo esterno attraversa tutte le n−1 posizioni che potrebbero ancora dover essere scambiate a sinistra, e
il ciclo interno va dalla fine dell'array a quella posizione.
Come di consueto per gli algoritmi di ordinamento basati sul confronto, la complessità temporale verrà misurata
contando il numero di confronti che vengono effettuati. Il ciclo esterno viene eseguito
n−1 volte. Il ciclo interno viene eseguito (n−1)−(i−1) =n−i volte. Quindi il numero di
il confronto è lo stesso in ogni caso, vale a dire
n−1n−1 n−1
XX 1 = X (n−i)
i=1j=i i=1
= (n−1) + (n−2) +· · ·+ 1
n(n−1)
= .
2
Quindi il numero di confronti nel caso peggiore e nel caso medio è proporzionale a n.2 ,
e quindi le complessità temporali medie e nel peggior caso sono O(n2 ).
L'ordinamento per inserimento (non sorprendentemente) è una forma di ordinamento per inserimento. Inizia trattando il primo
entrya[0] come un array già ordinato, poi controlla la seconda entrya[1] e la confronta con
il primo. Se sono nell'ordine sbagliato, scambia i due. Questo lascia a[0], a[1] ordinati.
Poi prende il terzo elemento e lo posiziona al posto giusto, lasciando a[0], a[1], a[2]
ordinato, e così via. Più in generale, all'inizio della i-esima fase, l'Insertion Sort ha il
entriesa[0],..., a[i-1] ordinati e inserisce a[i], dando entry ordinati a[0],...,a[i].
Per l'array di partenza di esempio 4 1 3 2, l'Insertion Sort inizia considerando a[0]=4
come ordinato, poi prende upa[1] e 'lo inserisce' nell'array già ordinato, aumentando il
dimensione di esso di 1. Siccome a[1]=1 è più piccolo di a[0]=4, deve essere inserito nello spazio zero,
67
ma quel posto ha già un valore. Quindi prima spostiamo a[0] 'su' di una posizione in a[1] (cura
essere portati a ricordare prima!), e poi possiamo spostare l'oldato, dando
1 4 3 2 .
Nel passo successivo, l'algoritmo tratta a[0], a[1] come un array già ordinato e cerca di
inserta[2]=3. Questo valore ovviamente deve adattarsi tra a[0]=1 e a[1]=4. Questo si ottiene
spostando a[1] 'su' di una posizione a a[2] (il cui valore assumiamo di aver ricordato),
permettendoci di spostare il valore attuale in a[1], dando 1 3 4 2.
Infine, a[3]=2 deve essere inserito nell'array ordinato a[0],...,a[2]. Poiché a[2]=4 è
maggiore di 2, viene spostato 'su' di una posizione, e lo stesso accade per a[1]=3. Confronto con
a[0]=1 dimostra che a[1] era lo slot che stavamo cercando, dando 1 2 3 4.
L'algoritmo generale per l'ordinamento per inserimento può quindi essere scritto:
Il ciclo esterno scorre su n−1 elementi da inserire, e il ciclo interno prende ciascun successivo
l'elemento e lo scambia nuovamente attraverso la porzione attualmente ordinata fino a raggiungere la sua posizione corretta.
Tuttavia, questo comporta tipicamente lo scambio di ogni elemento successivo molte volte per portarlo nella sua giusta posizione.
posizione, quindi è più efficiente memorizzare ogni prossimo elemento in una variabile temporanea e solo
inseriscilo nella sua posizione corretta quando è stata trovata e il suo contenuto spostato:
Il ciclo esterno attraversa di nuovo n−1 elementi, e il ciclo interno torna attraverso l'attualmente
porzione ordinata fino a trovare la posizione corretta per il prossimo elemento da inserire.
La complessità temporale è nuovamente considerata come il numero di confronti effettuati.
Il ciclo esterno viene sempre eseguito n−1 volte. Quante volte viene eseguito il ciclo interno?
dipende dagli oggetti da ordinare. Nel caso peggiore, verrà eseguito volte; in media,
sarà la metà di tanto. Pertanto, il numero di confronti nel caso peggiore è:
n−1i n−1
XX 1 = X io
i=1j=1 i=1
= 1 + 2 + · · · + (n−1)
n(n−1)
= ;
2
68
e nel caso medio è la metà di quello, ovvero n(n−1)/4. Quindi, caso medio e caso peggiore
il numero di passaggi per l'Insertion Sort è proporzionale a n2 , e quindi la media e
i casi peggiori le complessità temporali sono entrambe O(n)2 ).
Selection Sort è (non sorprendentemente) una forma di ordinamento per selezione. Prima trova l'elemento più piccolo
e lo inserisce in a[0] scambiandolo con qualunque oggetto si trovi già in quella posizione. Poi
trova il secondo elemento più piccolo e lo scambia con l'elemento in a[1]. Continua in questo modo
modo fino a quando l'intero array è ordinato. Più in generale, alla i-esima fase, il Selection Sort trova il
l'elemento più piccolo e lo scambia con l'elemento in a[i-1]. Ovviamente non c'è bisogno di controllare
per il i-esimo elemento più piccolo nei primi i−1 elementi dell'array.
Per l'array iniziale di esempio 4 1 3 2, il Selection Sort trova per primo il più piccolo
elemento nell'intero array, che isa[1]=1, e scambia questo valore con quello ina[0]dando
1 4 3 2. Poi, per il secondo passaggio, trova l'elemento più piccolo nell'array ridotto
a[1],a[2],a[3], che implica a[3]=2, e scambia questo in a[1], dando 1 2 3 4. Infine, esso
trova il più piccolo dell'array ridotto a[2],a[3], che è a[2]=3, e lo scambia in a[2]
o riconosce che uno scambio non è necessario, dando 1 2 3 4.
L'algoritmo generale per l'ordinamento per selezione può essere scritto:
69
9.7 Confronto di O(n2 algoritmi di ordinamento
Wehave now seen three different array based sorting algorithms, all based on different sorting
strategie, e tutto con O(n)2 ) complessità temporale. Quindi si potrebbe immaginare che non faccia
molta differenza quale di questi algoritmi venga utilizzato. Tuttavia, in pratica, può effettivamente fare
una grande differenza quale algoritmo viene scelto. La seguente tabella mostra il tempo di esecuzione misurato
tempi dei tre algoritmi applicati a array di interi delle dimensioni indicate nella riga superiore:
Qui O1024 denota un array con 1024 voci già ordinate, e R1024 è un
array che è ordinato in ordine inverso, cioè, dal più grande al più piccolo. Tutti gli altri
gli array sono stati riempiti casualmente. Attenzione: tabelle di misure come questa sono sempre dipendenti
sull'ordinamento casuale utilizzato, sull'implementazione del linguaggio di programmazione coinvolto, e
sulla macchina su cui è stato eseguito, e quindi non sarà mai esattamente lo stesso.
Quindi, da dove vengono esattamente queste differenze? Per cominciare, l'ordinamento per selezione è sempre
efettua(n−1)/2 confronti, ma esegue al massimo n−1 scambi. Ogni scambio richiede tre
le assegnazioni e le operazioni richiedono, infatti, più tempo rispetto a un confronto. Bubble Sort, d'altra parte,
fa molte scambi. L'Insertion Sort funziona particolarmente bene su dati già ordinati –
in tal caso, fa solo n−1 confronti. Vale la pena tenerne conto per alcuni
applicazioni, perché se solo poche voci sono fuori posto, l'Insertion Sort può essere molto veloce.
Questi confronti servono a dimostrare che le considerazioni sulla complessità possono essere piuttosto delicate, e
richiede un buon giudizio riguardo a quali operazioni contare. Spesso è una buona idea eseguire
alcuni esperimenti per testare le considerazioni teoriche e vedere se ci sono semplificazioni
si basano su realtà pratiche. Ad esempio, abbiamo supposto qui che tutti i confronti costino
lo stesso, ma ciò potrebbe non essere vero per grandi numeri o stringhe di caratteri.
Cosa esattamente contare quando si considera la complessità di un particolare algoritmo è sempre
una decisione giudiziosa. Dovrai acquisire esperienza prima di sentirti a tuo agio nel prendere
tali decisioni da solo. Inoltre, quando vuoi migliorare le performance di un
algoritmo, potresti voler determinare il maggiore utilizzatore delle risorse informatiche e concentrarti su
migliorare questo. Qualcos'altro di cui essere consapevoli quando si effettuano questi calcoli è che è
non è una cattiva idea tenere traccia di eventuali fattori costanti, in particolare quelli che vanno con il
sottoterminedominante. Negli esempi sopra, il fattore applicato al sottoterminedominante,
namelyn2 , varia. È 1/2 per il caso medio di Bubble Sort e Selection Sort, ma solo
1/4 per l'Insertion Sort. È certamente utile sapere che un algoritmo che è lineare sarà
performare meglio di uno quadratico a condizione che la dimensione del problema sia abbastanza grande, ma se
Sai che il tuo problema ha una dimensione di, diciamo, al massimo 100, quindi una complessità di (1/20)n2
sarà preferibile a uno di 20n. O se sai che il tuo programma viene utilizzato solo su
campioni piccoli, poi utilizzare l'algoritmo più semplice che puoi trovare potrebbe essere complessivamente vantaggioso – è
è più facile da programmare e non c'è molto tempo di calcolo da risparmiare.
Infine, i numeri sopra ti danno un'idea del perché, per i progettisti di programmi, il generale
La regola è di non usare mai il Bubble Sort. È certamente facile da programmare, ma questo è tutto ciò che ha.
andando per questo. È meglio evitarlo del tutto.
70
9.8 Stabilità degli algoritmi di ordinamento
Spesso si vuole ordinare articoli che potrebbero avere chiavi identiche (ad esempio, età in anni) in modo tale che
modo in cui gli elementi con chiavi identiche sono mantenuti nel loro ordine originale, in particolare se gli elementi
sono già stati ordinati secondo criteri diversi (ad esempio, alfabetico). Quindi, se denotiamo
l'ordine originale di un array di elementi per sottoscritti, vogliamo che i sottoscritti finiscano in
ordina per ciascun set di elementi con chiavi identiche. Ad esempio, se iniziamo con l'array
[51 ,42 ,63 ,54 ,65 ,76 ,57 ,28 ,99 ], dovrebbe essere ordinato in [28 ,42 ,51 ,54 ,57 ,63 ,65 ,76 ,99 ] e non a
[28 ,42 ,54 ,51 ,57 ,63 ,65 ,76 ,99 Gli algoritmi di ordinamento che soddisfano questa utile proprietà sono detti
essere stabile.
Il modo più semplice per determinare se un certo algoritmo è stabile è considerare se
l'algoritmo può mai scambiare articoli identici tra loro. In questo modo, la stabilità del
Gli algoritmi di ordinamento studiati finora possono essere facilmente stabiliti:
Ordinamento a bolle Questo è stabile perché nessun elemento viene scambiato oltre un altro a meno che non siano
in ordine sbagliato. Quindi gli elementi con chiavi identiche avranno il loro originale
ordine preservato.
Ordinamento per Inserimento Questo è stabile perché nessun elemento viene scambiato oltre un altro a meno che non abbia un
chiave più piccola. Quindi gli elementi con chiavi identiche avranno il loro ordine originale
preservato.
Ordinamento per selezione Questo non è stabile, perché non c'è nulla che impedisca a un oggetto di essere scambiato
passare un altro elemento che ha una chiave identica. Ad esempio, l'array
[21 ,22 ,13 ] sarebbe ordinato a [13 ,22 ,21 ] che ha articoli 22e 21nella
ordine sbagliato.
La questione della stabilità dell'ordinamento deve essere presa in considerazione quando si sviluppano algoritmi di ordinamento più complessi
algoritmi. Spesso ci sono versioni stabili e non stabili degli algoritmi, e bisogna
considera se il costo aggiuntivo per mantenere la stabilità vale lo sforzo.
Consideriamo ora un modo di implementare un algoritmo di ordinamento per inserimento utilizzando un dato
struttura meglio adatta al problema. L'idea qui, che abbiamo già visto prima,
comporta l'inserimento degli elementi da ordinare in un albero di ricerca binario inizialmente vuoto. Poi,
quando tutti gli elementi sono stati inseriti, sappiamo che possiamo attraversare l'albero di ricerca binaria per
visita tutti gli elementi nell'ordine corretto. Questo algoritmo di ordinamento si chiama Treesort, e per il
versione base, richiediamo che tutte le chiavi di ricerca siano diverse.
Ovviamente, l'albero deve essere mantenuto bilanciato per minimizzare il numero di confronti,
poiché ciò dipende dall'altezza dell'albero. Per un albero bilanciato che è O(log2n). Se l'albero
non è mantenuto bilanciato, sarà più di così e potenzialmente O(n).
Il Treesort può essere difficile da confrontare con altri algoritmi di ordinamento, poiché restituisce un albero.
piuttosto che un array, come la struttura dati ordinata. Dovrebbe essere scelto se è desiderabile
avere gli elementi memorizzati in un albero di ricerca binaria comunque. Questo è solitamente il caso se gli oggetti
vengono frequentemente eliminati o inseriti, poiché un albero di ricerca binario consente queste operazioni di
implementato in modo efficiente, con complessità temporale O(log2n) per articolo. Inoltre, come abbiamo visto
prima, cercare elementi è anche efficiente, di nuovo con una complessità temporale O(log2n).
71
Anche se abbiamo un array di elementi da cui partire, e vogliamo finire con un array ordinato,
possiamo ancora utilizzare Treesort. Tuttavia, per inserire gli elementi ordinati nell'array originale, we will
hai bisogno di un'altra procedura fillArray(tree t, array a, int j) per attraversare l'albero t e riempire il
arraya. That is easiest done by passing and returning an indexjthat keeps track of the
prossima posizione dell'array da riempire. Questo porta all'algoritmo completo di Treesort:
treeSort(array a) {
t = AlberoVuoto
per ( i = 0 ; i < dimensione(a) ; i++ )
t = inserisci(a[i], t)
fillArray(t,a,0)
}
che assume che ais sia un puntatore alla posizione dell'array e che i suoi elementi possano essere accessibili
e aggiornato dato ciò e l'indice dell'array pertinente.
Poiché ci sono elementi da inserire nell'albero, e ogni inserimento ha una complessità temporale
O(log2n), Treesort has an overall average time complexity ofO(nlog2n). Quindi, abbiamo già
un algoritmo che raggiunge la migliore complessità temporale media teorica di O(nlog)2n).
Tieni presente, tuttavia, che se l'albero non viene mantenuto bilanciato mentre gli elementi vengono inseriti, e
gli oggetti sono già ordinati, l'altezza dell'albero e il numero di confronti per inserimento
sarà O(n), portando a una complessità temporale nel caso peggiore di O(n2 ), che non è meglio del
algoritmi basati su array più semplici che abbiamo già considerato.
Esercizio: Finora abbiamo assunto che gli elementi memorizzati in un Albero di Ricerca Binaria non devono
contenga eventuali duplicati. Trova i modi più semplici per rilassare quella restrizione e determinare come
La scelta dell'approccio influisce sulla stabilità dell'algoritmo Treesort associato.
Ora consideriamo un altro modo di implementare un algoritmo di ordinamento per selezione utilizzando un più
struttura dati efficiente che abbiamo già studiato. L'idea di base qui è che sarebbe
aiutare se potessimo pre-organizzare i dati in modo che la selezione dell'elemento più piccolo / più grande diventi
più facile. A tale riguardo, ricorda l'idea di priorità in coda discussa in precedenza. Possiamo prendere il
il valore di ogni elemento deve essere la sua priorità e poi mettere in coda gli elementi di conseguenza. Poi, se rimuoviamo
l'elemento con la priorità più alta a ciascun passo possiamo riempire un array in ordine 'dalla parte posteriore',
iniziare con l'oggetto più grande.
Le code di priorità possono essere implementate in diversi modi, e abbiamo già
ho studiato una semplice implementazione usando alberi heap binari nel Capitolo 8. Tuttavia,
potrebbe esserci un modo migliore, quindi vale la pena considerare le altre possibilità.
72
Un modo ovvio di implementarli sarebbe utilizzare un array ordinato, in modo che l'ingresso
con la massima priorità appare ina[n]. Rimuovere questo elemento sarebbe molto semplice, ma
inserire un nuovo elemento comporterebbe sempre trovare la posizione giusta e spostare un certo numero di
oggetti a destra per fare spazio per esso. Ad esempio, inserendo a3 nella coda [1,2,4]:
n 0 1 2 3 4 5
a[n]1 2 4
n 0 1 2 3 4 5
a[n]1 2 4
n 0 1 2 3 4 5
a[n]1 2 3 4
Quel tipo di inserimento di elementi è effettivamente un ordinamento per inserimento ed è chiaramente inefficiente in generale, di
clearly inefficient in general, ofO(n) complexity rather thanO(log2n) con un albero heap.
Pertanto, di quelle tre rappresentazioni, solo una è utile per portare a termine l'idea sopra.
in modo efficiente. Un array non ordinato è quello da cui siamo partiti, quindi non è di aiuto, e ordinare
l'array è ciò che stiamo cercando di raggiungere, quindi gli heap sono la strada da seguire.
Per utilizzare gli alberi binari a heap, dobbiamo prima prendere l'array non ordinato e riorganizzarlo.
in modo che soddisfi l'ordinamento di priorità dell'albero heap. Abbiamo già studiato l'heapify
algoritmo che può farlo con una complessità temporale di O(n). Poi dobbiamo estrarre l'ordinato
array da esso. Nella struttura ad albero heap, l'elemento con la massima priorità, cioè l'elemento più grande, è
sempre ina[1]. Nell'array ordinato, dovrebbe essere nell'ultima posizione a[n]. Se semplicemente scambiamo
i due, avremo quell'elemento nella posizione giusta dell'array, e abbiamo anche iniziato il
procedura standard per rimuovere la radice dell'albero heap, poiché a[n] è precisamente l'elemento che
verrebbe spostato nella posizione di radice al passo successivo. Poiché a[n] ora contiene il corretto
elemento, non dovremo mai più guardarlo. Invece, prendiamo semplicemente gli elementi a[1],...,a[n-1]
e riportarli in una forma ad albero a torrente utilizzando la procedura di discesa a bolle sulla nuova radice,
che sappiamo avere complessità O(log2n).
Ora il secondo elemento più grande è in posizionea[1], e la sua posizione finale dovrebbe esserea[n-1].
quindi ora scambiamo questi due elementi. Poi riordiniamo a[1],...,a[n-2] di nuovo in un albero heap
utilizzando la procedura di discesa a bolle sul nuovo radice. E così via.
Quando il passo i è stato completato, gli elementi a[n-i+1],...,a[n] avranno il corretto
voci, e ci sarà un albero heap per gli elementi a[1],...,a[n-i]. Nota che la dimensione,
e quindi l'altezza dell'albero heap diminuisce ad ogni passo. Come parte del passo i-esimo,
dobbiamo portare giù il nuovo nodo principale. Questo richiederà al massimo il doppio delle comparazioni rispetto a
l'altezza dell'albero heap originale, che è log2Quindi complessivamente ci sono n−1 passaggi, con almeno
most 2log2confronti, per un totale di 2(n−1)log 2n. Il numero di confronti sarà effettivamente
essere inferiore a quello, perché il numero di passaggi di bubble down sarà di solito inferiore al totale
l'altezza dell'albero, ma di solito non molto meno, quindi la complessità temporale è ancora O(nlog2n).
L'algoritmo completo Heapsort può quindi essere scritto in una forma molto semplice, utilizzando il bubble
le procedure down e heapify che abbiamo già dal Capitolo 8. Prima heapify converte il
73
array into a binary heap tree, and then the for loop moves each successive root one item at
un tempo nella posizione corretta nell'array ordinato:
heapSort(array a, int n) {
heapify(a,n)
for( j = n ; j > 1 ; j-- ) {
scambia a[1] e a[j]
bubbleDown(1,a,j-1)
}
}
È chiaro dal passaggio di scambio che l'ordine degli oggetti identici può facilmente essere invertito, quindi ci
non c'è modo di rendere l'algoritmo Heapsort stabile.
Le complessità temporali medie e nel peggiore dei casi dell'intero algoritmo Heapsort sono fornite
dalla somma di due funzioni di complessità, prima quella di heapify che riordina l'originale non ordinato
array in un albero heap che è O(n), e poi quello di fare l'array ordinato fuori dai
albero heap che è O(n log)2n) provenienti dagli O(n) bubble-down, ciascuno dei quali ha O(log2n)
complessità. Quindi, la complessità media complessiva e quella nel caso peggiore sono entrambe O(nlog2n), e
abbiamo ora un algoritmo di ordinamento che raggiunge il migliore tempo di complessità nel caso peggiore teorico
Utilizzando code di priorità più sofisticate, come gli heap binomiali o di Fibonacci, non può
migliora su questo perché hanno la stessa complessità temporale di cancellazione.
Una funzionalità utile di Heapsort è che se è necessario trovare solo i m più grandi elementi e
ordinato, invece di alln, la complessità della seconda fase è solo O(mlog2n), che può
può facilmente essere inferiore a O(n) e quindi rendere l'intero algoritmo solo O(n).
74
9.12 Quicksort
L'idea generale qui è di suddividere (o partizionare) ripetutamente l'array dato in modo tale che
tutti gli elementi nel primo sotto-array sono più piccoli di tutti gli elementi nel secondo sotto-array, e
quindi concatenare tutti i sotto-array per ottenere l'array completo ordinato.
Come suddividere. La domanda importante è come eseguire questo tipo di divisione nel modo migliore.
in modo efficiente. Se l'array è molto semplice, ad esempio [4,3,7,8,1,6], allora una buona divisione sarebbe
put all the items smaller than 5 into one part, giving [4,3,1], and all the items bigger than
o uguale a 5 nell'altro, cioè [7,8,6]. Infatti, spostando tutti gli elementi con una chiave più piccola di
alcuni valori dati in un sotto-array, e tutte le voci con una chiave pari o superiore nell'altro
l'array secondario è la strategia standard del Quicksort. Il valore che definisce la divisione è chiamato il
pivot. Tuttavia, non è ovvio quale sia il modo migliore per scegliere il valore di pivot.
Una situazione che dobbiamo assolutamente evitare è dividere l'array in una sottoarray vuota.
array e l'intero array di nuovo. Se facciamo così, l'algoritmo non solo funzionerà male, ma
non terminerà nemmeno. Tuttavia, se il pivot è scelto come un elemento nell'array, e il
il pivot è mantenuto in mezzo e separato da entrambi i sotto-array, poi i sotto-array vengono ordinati
ad ogni ricorsione ci sarà sempre almeno un elemento in meno rispetto all'array precedente, e il
l'algoritmo è garantito per terminare.
Quindi, risulta conveniente suddividere l'array in ogni fase nei sotto-array di valori
minore o uguale a un elemento pivot scelto, seguito da quell'elemento pivot scelto, seguito da
dal sotto-array di valori maggiori o uguali all'elemento pivot scelto. Inoltre, per risparmiare
spazio, in realtà non dividiamo l'array in array più piccoli. Invece, semplicemente riordiniamo il
l'intero array per riflettere la divisione. Diciamo che partizioniamo l'array, e il Quicksort
l'algoritmo viene quindi applicato ai sottoarray di questo array partizionato.
Affinché l'algoritmo venga chiamato ricorsivamente, per ordinare parti sempre più piccole dell'originale
array, dobbiamo indicare quale parte dell'array è attualmente in considerazione. Pertanto,
Quicksort viene chiamato dando l'indice più basso (sinistra) e l'indice più alto (destra) del sottoarray
deve funzionare su. Quindi l'algoritmo assume la forma:
75
Scegliere il pivot. Se scegliamo il pivot 'just right' (ad esempio, scegliendo 5 nell'esempio sopra),
quindi la suddivisione sarà il più equa possibile. Sfortunatamente, non c'è un modo rapido garantito
di trovare il pivot ottimale. Se le chiavi sono numeri interi, si potrebbe prendere il valore medio di tutti
le chiavi, ma ciò richiede di visitare tutte le voci per campionare la loro chiave, aggiungendo considerevoli
il sovraccarico per l'algoritmo, e se le chiavi sono più complicate, come le stringhe, non puoi
farlo affatto. Più importanti, non darebbe necessariamente un pivot che è un valore nel
array. Alcune strategie di scelta di pivot euristiche sensate sono:
•Usa un generatore di numeri casuali per produrre un indice k e poi usa a[k].
Nota che non si dovrebbe mai scegliere semplicemente la prima o l'ultima chiave dell'array come pivot.
perché se l'array è già quasi ordinato, ciò porterà a una scelta particolarmente cattiva
menzionato sopra, e questa situazione è in realtà piuttosto comune nella pratica.
Poiché ci sono così tante possibilità ragionevoli, e sono tutte abbastanza semplici,
non forniremo una implementazione specifica per nessuna di queste strategie di scelta del pivot, ma solo
assume that we have achoosePivot(a,left,right)procedure that returns the index of the
pivot per un particolare sotto-array (anziché il valore pivot stesso).
76
ferma. Infine, scambiamo il pivot dalla posizione finale nella posizione immediatamente
dopo i segni per dare [c, base, ada, java| |fortran, ocaml, haskell, pascal].
Poiché ovviamente non possiamo avere gli indici dei marker 'tra' le voci dell'array, faremo come-
sume il marcatore sinistro è a sinistra di [leftmark] e il marcatore destro è a destra
ofa[rightmark]. I marcatori sono quindi 'nello stesso posto' una volta che rightmark diventa
più piccolo di leftmark, che è quando ci fermiamo. Se assumiamo che le chiavi siano numeri interi, noi
può scrivere la procedura di partizionamento, che deve restituire la posizione finale del pivot, come:
Questo raggiunge una partizione che termina con gli stessi elementi nell'array, ma in un modo diverso.
ordine, con tutti gli elementi a sinistra della posizione di pivot restituita più piccoli o uguali al pivot
valore, e tutti gli elementi a destra maggiori o uguali al valore pivot.
Nota che questo algoritmo non richiede alcuna memoria extra - scambia semplicemente gli elementi nel
array originale. Tuttavia, lo scambio di elementi significa che l'algoritmo non è stabile. Per rendere
quicksort stabile, la partizione deve essere effettuata in modo tale che l'ordine degli elementi identici
non può mai essere invertito. Un approccio concettualmente semplice che fa questo, ma richiede più
la memoria e la copia consiste semplicemente nel passare sistematicamente attraverso l'intero array, riempiendo nuovamente il
arraya con elementi minori o uguali al pivot, e riempiendo un secondo arrayb con elementi
maggiore o uguale al pivot, e infine copiando l'array b alla fine di a:
77
a[acount++] = a[i]
altrimenti
b[bcount++] = a[i]
}
per ( i = 0 ; i < bcount ; i++ )
a[acount++] = b[i]
restituisci right-bcount+1
}
Come la prima procedura di partizionamento, anche questa raggiunge una partizione con gli stessi elementi nel
array, ma in un ordine differente, con tutti gli elementi a sinistra della posizione del pivot restituito più piccoli
o uguale al valore di pivot, e tutti gli elementi a destra maggiori o uguali al valore di pivot.
78
Migliorare il Quicksort. È sempre utile dedicare del tempo ad ottimizzare la strategia
per definire il pivot, dato che il particolare problema in questione potrebbe benissimo consentire un più
approccio raffinato. In generale, il pivot sarà migliore se vengono campionati più elementi prima di esso
viene scelto. Ad esempio, si potrebbero controllare diversi articoli scelti a caso e prendere il
‘mediano’ uno di quelli, il cosiddetto mediana. Nota che per trovare la mediana di tutti i
oggetti, senza ordinarli prima, ci ritroveremmo a dover fare n2confronti, quindi noi
non posso farlo senza rendere Quicksort sgradevolmente lento.
Quicksort raramente è l'algoritmo più adatto se la dimensione del problema è piccola. Il motivo per
questi sono tutti i costi aggiuntivi della ricorsione (ad esempio, memorizzare tutti gli indirizzi di ritorno e formali
parametri). Quindi, una volta che il sotto-problema diventa 'piccolo' (una dimensione di 16 è spesso suggerita in
la letteratura), Quicksort dovrebbe smettere di chiamarsi e invece ordinare i restanti sotto-array
utilizzando un algoritmo più semplice come l'ordinamento per selezione.
9.13 Mergesort
L'altra strategia di ordinamento divide et impera basata sulla suddivisione ripetuta dell'array di
La suddivisione degli elementi in due sotto-array, menzionata nella Sezione 9.11, è chiamata mergesort. Questo semplicemente divide
l'array ad ogni fase nella sua prima e ultima metà, senza alcun riordino degli elementi in esso.
Tuttavia, ciò non porterà ovviamente a un insieme di sotto-array ordinati che possiamo semplicemente aggiungere.
l'uno con l'altro alla fine. Quindi mergesort necessita di un'altra procedura merge che unisce due ordinati
sotto-array in un altro array ordinato. Come con la ricerca binaria nella Sezione 4.4, variabili intere
sinistraedestra possono essere utilizzati per riferirsi all'indice inferiore e superiore dell'array pertinente, e
mid si riferisce alla fine del suo sotto-array sinistro. Quindi, un algoritmo di mergesort adatto è:
Si noti che sarebbe relativamente semplice modificare questo algoritmo di mergesort per operare su
liste collegate (di lunghezza nota) piuttosto che array. Per 'dividere' tale lista in due, tutto ciò che si deve fare è
imposta il puntatore della voce di lista thebn/2cth a null e usa il successivo a cui era precedentemente puntato
entry as the head of the new second list. Of course, care needs to be taken to keep the list
le informazioni sulle dimensioni rimangono intatte e sono necessari sforzi per trovare il puntatore cruciale per ciascuna divisione.
79
Tuttavia, l'implementazione sarà piuttosto diversa, a seconda di quale struttura dati
stiamo usando. Quando gli array vengono utilizzati, è effettivamente necessario che l'algoritmo di merge crei
un nuovo array per contenere temporaneamente il risultato dell'operazione. Al contrario, quando si utilizza
le liste collegate, sarebbe possibile far funzionare formergeto semplicemente cambiando il riferimento al successivo
node. Tuttavia, questo rende il codice un po' più confuso.
Per gli array, un algoritmo di fusione adatto inizierebbe creando un nuovo array b per memorizzare il
risultati, quindi aggiungi ripetutamente il prossimo elemento più piccolo fino a quando un sotto-array è completato, poi
copiare il resto del sotto-array non finito e infine copiare di nuovo in a:
È istruttivo confrontare questo con l'algoritmo di partizione per Quicksort per vedere esattamente
dove i due algoritmi di ordinamento differiscono. Come con partition2, l'algoritmo di fusione non scambia mai
oggetti identici passano l'uno accanto all'altro, e la scissione non cambia affatto l'ordinamento, quindi il
l'intero algoritmo Mergesort è stabile.
80
9.14 Sommario degli algoritmi di ordinamento basati su confronto
La seguente tabella riassume le principali proprietà di tutti gli algoritmi di ordinamento basati sul confronto.
ritmi che abbiamo considerato:
Per vedere cosa significano le complessità temporali nella pratica, la seguente tabella confronta il tipico
tempi di esecuzione di quelli degli algoritmi sopra che operano direttamente sugli array:
Come prima, gli array delle dimensioni indicate vengono riempiti casualmente, tranne O1024 che denota un array
con 1024 voci già ordinate, e R1024 che denota un array che è ordinato in
l'ordine inverso. Quicksort2 e Mergesort2 sono algoritmi in cui la procedura ricorsiva è
abbandonato a favore dell'Ordine di Selezione una volta che la dimensione dell'array scende a 16 o meno. Dovrebbe
va sottolineato ancora una volta che questi numeri sono di precisione limitata, poiché variano in qualche modo
a seconda della macchina e dell'implementazione del linguaggio.
Quello che deve essere sottolineato qui è che non esiste un 'miglior algoritmo di ordinamento' in generale, ma
che ci sono di solito buone e cattive scelte di algoritmi di ordinamento per circostanze particolari.
Spetta al progettista del programma assicurarsi che ne venga scelta una appropriata, a seconda
sulle proprietà dei dati da ordinare, come è meglio conservarli, se tutti gli elementi ordinati
sono richiesti piuttosto che qualche sottogruppo, e così via.
Tutti gli algoritmi di ordinamento sopra menzionati si basano su confronti tra gli elementi da ordinare,
e abbiamo visto che non possiamo ottenere una complessità temporale migliore di O(n log2n)
con confronti
algoritmi basati. Tuttavia, in alcune circostanze è possibile fare meglio di così con
algoritmi di ordinamento che non si basano su confronti.
81
It is always worth thinking about the data that needs to be sorted, and whether com-
I confronti sono davvero necessari. Ad esempio, supponiamo che tu sappia che gli elementi da ordinare sono i
numeri da 0 a n−1. Come li ordineresti? La risposta è sorprendentemente semplice. Noi
sappiamo che abbiamo voci nell'array e sappiamo esattamente quali elementi dovrebbero andarci
e in quale ordine. Questa è una situazione molto insolita per quanto riguarda l'ordinamento generale, eppure
this kind of thing often comes up in every-day life. For example, when a hotel needs to sort
the room keys for its 100 rooms. Rather than employing one of the comparison-based sorting
algoritmi, in questa situazione possiamo fare qualcosa di molto più semplice. Possiamo semplicemente mettere gli oggetti
direttamente nei luoghi appropriati, utilizzando un algoritmo come quello mostrato nella Figura 9.1:
Figura 9.1: In poche parole, metti gli articoli nell'ordine giusto usando i loro valori.
Questo algoritmo utilizza un secondo array per contenere i risultati, il che non è sicuramente molto efficiente in termini di memoria.
è efficiente, ma è possibile farne a meno. Si possono usare una serie di scambi all'interno dell'array
per posizionare gli oggetti nei posti giusti come mostrato nella Figura 9.2:
i=0
3 0 4 1 2
i=0
1 0 4 3 2 per ( i = 0 ; i < n; i++ ) {
mentre ( a[i] != i )
scambia a[a[i]] e a[i]
0 1 4 3 2 }
i=1
i=2
0 1 2 3 4
Figura 9.2: Scambiare gli elementi nell'ordine corretto senza utilizzare un nuovo array.
Per quanto riguarda la complessità temporale, non è ovviamente appropriato qui contare il
numero di confronti. Invece, è il numero di scambi o copie che è importante. Il
L'algoritmo della Figura 9.1 esegue n copie per riempire l'array b e poi un altro n per restituire il risultato
to arraya, so the overall time complexity isO(n). The time complexity of the algorithm of
La figura 9.2 sembra peggiore di quel che è realmente. Questo algoritmo esegue al massimo n−1 scambi, poiché
un elemento, cioè a[a[i]], è sempre scambiato nella sua posizione finale. Quindi, nel peggiore dei casi, questo ha un tempo
complexityO(n) too.
Questo esempio dovrebbe rendere chiaro che in situazioni particolari, l'ordinamento potrebbe essere per-
formato da mezzi molto più semplici (e veloci) rispetto ai tradizionali algoritmi di ordinamento per confronto, anche se
le situazioni più realistiche non saranno così semplici come il caso qui. Ancora una volta, è il
responsibility of the program designer to take this possibility into account.
82
9.16 Ordinamenti Binari, a Secchiello, a Radice
Il metodo Bin, Bucket e Radix Sort sono tutti nomi per essenzialmente lo stesso metodo di ordinamento non basato su confronto
algoritmo di ordinamento che funziona bene quando gli oggetti sono etichettati da piccoli insiemi di valori. Per
esempio, supponi di avere un certo numero di date, per giorno e mese, e di doverle ordinare
in ordine. Un modo per farlo sarebbe creare una coda per ogni giorno e posizionare il
elementi (date) uno alla volta nella coda giusta in base al loro giorno (senza ordinarli)
ulteriormente). Poi forma un'unica grande coda da queste, concatenando tutte le code giornaliere a partire da
con il giorno 1 e continuando fino al giorno 31. Poi, per la seconda fase, crea una coda per ciascuno
mese, e posizionare le date nelle giuste code nell'ordine in cui appaiono nella coda
creato dalla prima fase. Forma di nuovo una lunga coda concatenando queste code mensili in
ordine. Questa coda finale è ordinata nell'ordine previsto.
Questo potrebbe sembrare sorprendente a prima vista, quindi consideriamo un semplice esempio:
[25/12, 28/08, 29/05, 01/05, 24/04, 03/01, 04/01, 25/04, 26/12, 26/04, 05/01, 20/04].
Per prima cosa creiamo e riempiamo le code per i giorni come segue:
01: [01/05]
03: [03/01]
04: [04/01]
05: [05/01]
20: [20/04]
24: [24/04]
25: [25/12, 25/04]
26: [26/12, 26/04]
28: [28/08]
29: [29/05]
Le code vuote non vengono mostrate - non c'è bisogno di creare code prima di colpire un elemento
che appartiene a loro. Quindi la concatenazione delle code dà:
[01/05, 03/01, 04/01, 05/01, 20/04, 24/04, 25/12, 25/04, 26/12, 26/04,28/08, 29/05].
Successivamente creiamo e riempiamo le code per i mesi che sono presenti, dando:
Infine, concatenando tutte queste code si ottengono gli elementi nell'ordine richiesto:
[03/01, 04/01, 05/01, 20/04, 24/04, 25/04, 26/04, 01/05, 29/05, 28/08, 25/12, 26/12].
Questo è chiamato Ordinamento Radix a Due Fasi, poiché ci sono chiaramente due fasi in esso.
83
L'estensione di questa idea per fornire un algoritmo di ordinamento generale dovrebbe essere ovvia: Per ogni
fase, crea un insieme ordinato di code corrispondenti ai valori possibili, quindi aggiungi ciascuno
elemento nell'ordine in cui appare fino alla fine della coda rilevante e infine concatenare il
le code in ordine. Ripeti questo processo per ciascun criterio di ordinamento. L'ulteriore cruciale
il dettaglio è che le fasi di attesa devono essere eseguite nell'ordine della significatività di ciascuna
criteri, con i criteri meno significativi per primi.
Ad esempio, se sai che i tuoi elementi da ordinare sono tutti (al massimo) numeri interi a due cifre,
puoi usare il Radix Sort per ordinarli. Prima crea e riempi le code per l'ultima cifra, concatena,
quindi crea e riempi le code per la prima cifra e concatena per lasciare gli elementi ordinati
ordine. Similmente, se sai che le tue chiavi sono tutte stringhe costituite da tre caratteri, tu
puoi nuovamente applicare il Radix Sort. Innanzitutto metti in coda in base al terzo carattere, poi il
secondo, e infine il primo, dando una ordinamento Radix a tre fasi.
Nota che, in nessun momento, l'algoritmo confronta effettivamente alcun elemento.
un tipo di algoritmo sfrutta il fatto che per ogni fase gli oggetti sono di un'esclusivamente
insieme ristretto, o, in altre parole, gli elementi sono di una forma particolare che è nota a priori.
La classe di complessità di questo algoritmo è O(n), poiché in ogni fase, ogni elemento viene trattato
precisamente una volta, e il numero di fasi è assunto essere piccolo e costante. Se l'area ridotta
set sono piccoli, il numero di operazioni coinvolte nel trovare la coda giusta per ogni elemento e
metterlo alla fine sarà piccolo, ma questo potrebbe diventare significativo se i set sono
grande. La concatenazione delle code comporterà alcuni sovraccarichi, ovviamente, ma questi saranno
essere piccoli se i set sono piccoli e le liste collegate, piuttosto che gli array, vengono utilizzate. Si deve essere
stai attento, però, perché se il numero totale di operazioni per ciascun elemento supera log2n, poi
la complessità complessiva è probabilmente maggiore di O(nlog)2n) complessità del più
algoritmi di confronto basati su confronto efficienti. Inoltre, se i set ristretti non sono noti in anticipo,
e potenzialmente grandi, i costi per trovarli e ordinarli potrebbero rendere il Radix sort peggiore
rispetto a un approccio basato sul confronto. Ancora una volta, è responsabilità del programma
il designer deve decidere se un dato problema può essere risolto più efficientemente con il Radix Sort
anziché un ordinamento basato su confronto.
84
Chapter 10
TabelleHash
85
012 Johnny Inglese Spy
007 James ObbligazioneSpia
583 Alex Cavaliere Spia
721 Sherlock Holmes Detective
722 Giacomo Villain Moriarty
2. Gli oggetti possono essere arbitrariamente complicati. Tuttavia, ai fini dei nostri scopi, l'unico rilevante
il dettaglio è che ogni oggetto ha una chiave unica e che le loro chiavi possono essere confrontate per
uguaglianza. Le chiavi vengono utilizzate per identificare oggetti in modo molto simile a come abbiamo fatto
per la ricerca e l'ordinamento.
interface Table {
Boolean èVuoto();
Boolean èPieno();
void Insert(Record);
Recupera registro(Chiave);
void Aggiorna(Record);
void Elimina{Chiave};
void Traversare();
}
Si noti che non abbiamo fissato esattamente come dovrebbe funzionare la memorizzazione dei record – questo è qualche-
cosa che viene con l'implementazione. Nota anche che potresti fornire un'interfaccia per
qualcun altro, che potrebbe poi scrivere un programma che esegue operazioni su tabelle senza
mai sapere come vengono implementati. Potresti sicuramente eseguire tutte quelle operazioni
con alberi di ricerca binari e array ordinati o non ordinati se lo desideri. I primi hanno addirittura
il vantaggio di un albero di ricerca binario è che non diventa mai pieno di per sé, poiché è solo limitato
dalla dimensione della memoria.
Questo approccio generale segue il modo sensato e comunemente usato per definire un
Classe Java: Prima pensa a cosa vuoi fare con la classe, e solo allora chiediti
86
su come esattamente potresti implementare i metodi. Quindi, linguaggi come Java supportano
meccanismi per definire tipi di dati astratti. Ma nota che, a differenza di una specifica
in inglese semplice, come sopra, una definizione di un'interfaccia è solo una specifica parziale
di un tipo di dati astratti, perché non spiega cosa dovrebbero fare i metodi;
spiega solo come vengono chiamati.
Implementazione tramite tabelle hash. L'idea qui è che, a spese di utilizzare di più
spazio di quanto strettamente necessario, possiamo accelerare le operazioni sulla tabella. Il resto di questo
capitolo descriverà come ciò avviene e quali sono i vari costi computazionali.
87
e così via. In questo caso, la funzione sarebbe la funzione identità h(k) = k. Tuttavia,
questa idea non è molto pratica se stiamo trattando con un numero relativamente ridotto di chiavi
di una enorme collezione di possibili chiavi. Ad esempio, molte aziende americane utilizzano le loro
numero di previdenza sociale a 9 cifre dei dipendenti come chiave, anche se non hanno nemmeno vicino a 109
i dipendenti. I numeri di previdenza sociale britannici sono addirittura peggiori, perché sono altrettanto lunghi
e di solito contengono una miscela di lettere e numeri. Chiaramente sarebbe molto inefficiente, se
non impossibile, riservare spazio per tutti e 109numeri di previdenza sociale che potrebbero verificarsi.
Invece, utilizziamo una funzione non banale, la cosiddetta funzione hash, per mappare lo spazio di
chiavi possibili per l'insieme degli indici del nostro array. Ad esempio, se dovessimo memorizzare voci su
500 dipendenti, potremmo creare un array con 1000 voci e utilizzare tre cifre dai loro
numero di previdenza sociale (forse le prime o le ultime tre) per determinare il posto nell'array
dove devono essere conservati i registri per ciascun singolo dipendente.
Questo approccio sembra un'ottima idea, ma c'è un problema piuttosto ovvio: Cosa
cosa succede se due dipendenti hanno gli stessi tre numeri? Questo è chiamato collisione
tra le due chiavi. Gran parte del resto di questo capitolo sarà dedicato ai vari
strategie per affrontare tali collisioni.
Prima di tutto, naturalmente, si dovrebbe cercare di evitare le collisioni. Se le chiavi che potrebbero
in realtà si verificano non sono distribuiti uniformemente nello spazio di tutte le possibili chiavi, particolare
si dovrebbe prestare attenzione nella scelta della funzione hash in modo tale che ci siano collisioni tra
essi sono meno probabili che si verifichino. Se, ad esempio, le prime tre cifre di un numero di previdenza sociale
aveva un significato geografico, quindi è particolarmente probabile che i dipendenti abbiano le tre cifre
significativo della regione in cui risiede l'azienda, e quindi scegliendo le prime tre cifre come un
La funzione hash potrebbe portare a molte collisioni. Tuttavia, quel problema potrebbe essere facilmente evitato.
da una scelta più prudente, come le ultime tre cifre.
Il paradosso del compleanno di von Mises. Come esempio, considera una raccolta di persone, e un
funzione hash che restituisce le loro date di nascita come il numero del giorno dell'anno, ad es. 1 gennaio
is 1, 2nd January is 2, . . . , 31st December is 365. One might think that if all we want to do
è conservare un numero modesto di 24 persone in questo modo in un array con 365 posizioni, collisioni
will be rather unlikely. However, it turns out that the probability of collision is bigger than
50%. Questo è così sorprendente a prima vista che questo fenomeno è diventato noto come il von
Il paradosso del compleanno di Mises, anche se non è davvero un paradosso nel senso stretto del termine.
È facile capire cosa sta succedendo. Supponiamo di avere un gruppo di n persone e
voglio scoprire quanto sia probabile che due di loro abbiano lo stesso compleanno, supponendo che il
I compleanni sono distribuiti uniformemente sui 365 giorni dell'anno. Chiamiamo questa probabilità
p(n). In realtà è più facile prima calcolare la probabilità q(n) che nessuno di essi condivida un
compleanno, e poi p(n) = 1−q(n). Per n = 1 questa probabilità è chiaramente q(1) = 1. Per n = 2
otteniamo q(2) = 364/365 perché, per la seconda persona aggiunta, 364 dei 365 giorni non sono il
compleanno della prima persona. Per n=3 otteniamo
364·363
q(3) = = 1−p(3)
3652
88
e per il caso generale n > 1 abbiamo
364·363· · ·(366−n)
q(n) = = 1−p(n)
365n−1
Potrebbe sorprendere che p(22) = 0,476 e p(23) = 0,507, il che significa che non appena ci sono
ci sono più di 22 persone in un gruppo, è più probabile che due di loro condividano un compleanno che
not. Si noti che nel mondo reale, la distribuzione dei compleanni durante l'anno non è precisamente
uniforme, ma questo aumenta solo la probabilità che due persone abbiano lo stesso compleanno. In
In altre parole, le collisioni di compleanno sono molto più probabili di quanto si possa pensare inizialmente.
Implicazioni per le tabelle hash. Se 23 posizioni casuali in una tabella di dimensioni 365 contengono più
Con più del 50% di probabilità di sovrapposizione, sembra inevitabile che si verifichino collisioni in qualsiasi hash
una tabella che non spreca una grande quantità di memoria. E le collisioni saranno ancora di più
probabilmente se la funzione di hashing non distribuisce gli elementi in modo casuale in tutta la tabella.
Per calcolare l'efficienza computazionale di una tabella hash, abbiamo bisogno di un modo per quantificare
quanto è piena la tabella, così possiamo calcolare la probabilità di collisioni e quindi determinare
quanto sforzo sarà necessario per affrontarli.
Il fattore di carico di una tabella hash. Supponiamo di avere una tabella hash di dimensione m, e attualmente
non ha voci. Poi chiamiamo λ = n/m il fattore di carico della tabella hash. Questo fattore di carico è
il modo ovvio di descrivere quanto è attualmente piena la tabella: una tabella hash con fattore di carico
0,25 è pieno al 25%, uno con un fattore di carico dello 0,50 è pieno al 50%, e così via. Quindi, se abbiamo un hash
tabella con fattore di carico λ, la probabilità che si verifichi una collisione per la prossima chiave che desideriamo
inserire èλ. Questo presume che ogni chiave dello spazio delle chiavi sia ugualmente probabile e che l'hash
la funzione diffonde uniformemente lo spazio delle chiavi sull'insieme degli indici del nostro array. Se questi ottimisti
se le assunzioni falliscono, allora la probabilità potrebbe essere ancora più alta.
Pertanto, per minimizzare le collisioni, è prudente mantenere bassa la percentuale di carico. Cinquanta percento è
una cifra massima spesso citata, mentre oltre l'ottanta percento di carico le prestazioni
deteriora considerevolmente. Vedremo più tardi esattamente quale effetto ha il fattore di carico della tabella su
la velocità delle operazioni di nostro interesse.
k=k1*262+k2∗261+k3∗260=k1∗262+k2∗26 +k3 .
89
Cioè, pensiamo alle stringhe come numeri codificati in base 26.
Ora è abbastanza facile passare da qualsiasi numero k (anziché una stringa) a un numero da 0
a 10. Ad esempio, possiamo prendere il resto che lascia il numero quando è diviso per 11. Questo
l'operazione di modulo CorJava è k % 11. Quindi la nostra funzione hash è
Codice PHL ORY GCM HKG GLA AKL FRA LAX DCA
h(X1 X2 X3 ) 4 8 6 4 8 7 5 1 1
È già chiaro che avremo collisioni di hash con cui dover fare i conti.
Iniziamo naturalmente con una tabella vuota della dimensione richiesta, cioè 11:
Chiaramente dobbiamo essere in grado di sapere se una particolare posizione nell'array è ancora vuota, o
se è già stato compilato. Possiamo assumere che ci sia una chiave o un'entrata unica (che
non è mai associato a un record) che indica che la posizione non è ancora stata occupata.
Tuttavia, per chiarezza, questa chiave non apparirà nelle immagini che utilizziamo.
Ora possiamo iniziare a inserire le chiavi in ordine. Il numero associato al primo elemento
PHL è 4, quindi lo posizioniamo all'indice 4, dando:
PHL
PHL ORY
Quindi HKG, che ha anch'esso valore 4, provoca la nostra prima collisione poiché la posizione corrispondente
è già stato riempito con PHL. Ora potremmo, ovviamente, cercare di affrontare questo semplicemente
dire che il tavolo è pieno, ma questo dà prestazioni così scadenti (a causa della frequenza con cui
si verificano collisioni) che è inaccettabile.
90
Secchi. Un'opzione ovvia è riservare un array bidimensionale fin dall'inizio. Possiamo
pensa a ciascuna colonna come a un secchio in cui gettiamo tutti gli elementi che danno un particolare
risultato quando la funzione di hash è fornita, quindi la quinta colonna contiene tutte le chiavi per le quali
la funzione hash si valuta a 4. Allora potremmo mettere HKG nello slot 'sotto' PHL, e
GLA in quello sottostante ORY, e continua a riempire la tabella nell'ordine dato fino a raggiungere:
0 1 2 3 4 5 6 7 8 9 10
LAX PHL FRA GCM AKL ORY
DCA HKG GLA
Lo svantaggio di questo approccio è che deve riservare abbastanza più spazio di quanto
sarà eventualmente richiesto, poiché deve tenere conto del probabile numero massimo di
collisioni. Anche se il tavolo è ancora piuttosto vuoto in generale, le collisioni diventeranno sempre più
probabile. Inoltre, quando si cerca una chiave particolare, sarà necessario cercare nell'intero
colonna associata alla sua posizione attesa, almeno fino a quando non si raggiunge uno slot vuoto. Se ci
è un ordine sulle chiavi, possono essere memorizzate in ordine crescente, il che significa che possiamo utilizzare il
una ricerca binaria più efficiente piuttosto che una ricerca lineare, ma l'ordinamento avrà un sovraccarico
di proprio. La complessità media della ricerca di un oggetto particolare dipende da quanti
Le voci nell'array sono già state riempite. Questo approccio si rivela essere più lento rispetto al
altre tecniche che prenderemo in considerazione, quindi non spenderemo più tempo su di esse, a parte
notando che risulta utile quando le voci sono conservate in un archivio esterno lento.
Catena diretta. Invece di riservare interi sotto-array (le colonne sopra) per le chiavi
che collidono, si può invece creare un elenco collegato per l'insieme delle voci corrispondenti a ciascuna
chiave. Il risultato per l'esempio sopra può essere rappresentato in questo modo:
0 1 2 3 4 5 6 7 8 9 10
Questo approccio non riserva alcuno spazio che non sarà occupato, ma ha lo svantaggio
affinché per trovare un particolare elemento, le liste dovranno essere attraversate. Tuttavia, aggiungendo il
il passo di hashing accelera ancora notevolmente il recupero.
Possiamo calcolare la dimensione della lista media non vuota che si verifica nella tabella hash come
segue. Con n elementi in un array di dimensione m, la probabilità che nessun elemento cada in un particolare
slot isq(n, m) =(m−1)nmQuindi il numero di slot con almeno un elemento che vi cade dentro è
m−1
N(n, m) =m.1−q(n, m) = m.1−( )n
m
91
e poiché ci sono in tutto articoli, il numero medio di articoli in un elenco non vuoto è:
k(n, m) = n n
= .
N(n, m) m.1−(m−1
)n
m
k+ 1 λ λ2
=1++ +O(λ3 )
2 4 24
confronti medi per una ricerca di successo, cioè che questa ha complessità O(1).
Per una ricerca non riuscita, abbiamo bisogno della dimensione media della lista inclusi gli spazi vuoti. Quello
sarà chiaramente ben/m=λ, e quindi in una ricerca non riuscita il numero medio di confronti
deciso che l'oggetto in questione non è presente sarà λ, che è di nuovo O(1).
Pertanto, né i tempi di ricerca riusciti né quelli non riusciti dipendono dal numero di chiavi.
nella tabella, ma solo sul fattore di carico, che può essere mantenuto basso scegliendo la dimensione del
la tabella hash deve essere abbastanza grande. Nota anche che l'inserimento avviene ancora più rapidamente, poiché tutto ciò che
devi solo inserire un nuovo elemento all'inizio dell'elenco appropriato. Pertanto, a parte
la complessità della classi di tutte le operazioni è costante, ossia O(1). Per il traverso, abbiamo bisogno di
per ordinare le chiavi, il che può essere fatto in O(nlog2n), come sappiamo dal Capitolo 9. Una variante
sarebbe rendere ciascuna lista collegata ordinata, il che accelererà la ricerca di un elemento, così come la velocità
la traversata verso l'alto leggermente, anche se questo non porterà nessuna delle due operazioni in una complessità diversa
Questa accelerazione sarebbe compensata rendendo l'operazione di inserimento più costosa.
cioè, richiederà leggermente più tempo, ma avrà comunque una complessità costante.
Nel complesso, tutte le complessità temporali per questo approccio sono chiaramente molto impressionanti rispetto
a quelli per array ordinati o alberi di ricerca binari (bilanciati).
92
e poi voleva mettere HKG all'indice 4, dove abbiamo trovato PHL.
La ricerca lineare riduce l'indice di uno a 3 e trova una posizione vuota in quella posizione,
quindi mettiamo HKG lì dando:
Successivamente desideriamo inserire GLA, con valore di hash 8, ma la posizione con quell'indice è già
riempito da ORY. Di nuovo il probing lineare riduce l'indice di uno, e poiché quel posto uno
a sinistra è libero, inseriamo GLA lì:
Poi abbiamo AKL, e anche se non abbiamo avuto il valore 7 prima, il corrispondente
la posizione è occupata da GLA. Quindi proviamo con l'indice successivo, ma quello contiene GCM, quindi noi
continua al successivo all'indice 5 che è vuoto, quindi mettiamo AKL lì:
["HKG","PHL","AKL","GCM","GLA","ORY"]
Ora continuiamo allo stesso modo con le chiavi rimanenti, raggiungendo infine:
Questo sembra piuttosto convincente: tutte le chiavi sono state inserite in un modo che sembra rendere
buon uso dello spazio che abbiamo riservato.
Tuttavia, cosa succede adesso se desideriamo trovare una chiave particolare? Non sarà più utile.
basta semplicemente applicare la funzione hash ad esso e controllare lì. Invece, dovremo
seguire le possibili posizioni di inserimento fino a quando non troviamo una vuota, che ci dice che la chiave
quello che stavamo cercando non è presente, dopotutto, perché sarebbe stato inserito lì. Questo
è per questo che ogni tabella hash che utilizza l'indirizzamento aperto dovrebbe avere almeno un posto vuoto in qualsiasi momento
tempo, e sarà dichiarato pieno quando rimarrà solo un luogo vuoto. Tuttavia, come vedremo,
le tabelle hash perdono gran parte del loro vantaggio di velocità se hanno un alto fattore di carico, quindi come questione
Di politica, molti più luoghi dovrebbero rimanere vuoti.
Quindi, per trovare la chiave AKL, controlleremmo prima all'indice 7, poi al 6 e al 5, dove siamo
successo. Cercando JFK, d'altra parte, inizieremmo con la sua posizione corretta,
dato dal valore della funzione hash 8, quindi controlleremmo gli indici 8, 7, 6, . . . , 1, 0, 10 in quest'ordine
fino a trovare uno spazio vuoto che ci dica che JFK non è affatto presente. Questo sembra
abbastanza male a prima vista, ma tieni a mente che abbiamo detto che punteremo a mantenere il
fattore di carico attorno al 50 percento, quindi ci sarebbero molti più posti vuoti che di fatto
ferma qualsiasi ulteriore ricerca.
Ma questa idea porta con sé un altro problema. Supponiamo di eliminare ora GCM dalla tabella.
and then search for AKL again. We would find the array empty at index 6 and stop searching,
e quindi concludere erroneamente che l'AKL non è presente. Questo è chiaramente inaccettabile, ma
allo stesso modo, non desideriamo dover cercare nell'intero array per essere sicuri che un'entrata sia
non ci sono. La soluzione è che riserviamo un'altra chiave per significare che una posizione è vuota, ma
that it did hold a key at some point. Let us assume that we use the character ‘!’ for that.
Dopo aver eliminato GCM, l'array sarebbe:
{"DCA":"DCA","LAX":"LAX","FRA":"FRA","HKG":"HKG","PHL":"PHL","AKL":"AKL"}
! GLA ORY
93
e quando cerchiamo AKL sapremmo di continuare oltre il punto esclamativo. Se,
d'altra parte, stiamo cercando di inserire una chiave, quindi possiamo ignorare eventuali punti esclamativi
e occupare nuovamente la posizione. Questo ora si occupa di tutti i nostri problemi, sebbene se noi
fai molte cancellazioni e inserimenti, finiremo con una tabella che è un po' un disastro. Un grande
il numero di punti esclamativi significa che dobbiamo continuare a cercare a lungo per trovare un
voce particolare nonostante il fatto che il fattore di carico potrebbe non essere così alto. Questo succede
se la cancellazione è un'operazione frequente. In tali casi, potrebbe essere meglio riempire una nuova tabella hash
di nuovo da zero, o utilizzare un'altra implementazione.
Se proviamo a inserire JFK, notiamo che la funzione hash si valuta nuovamente a 8. Quindi noi
continua a controllare le stesse posizioni che abbiamo appena controllato per inserire GLA. Questo sembra un
modo piuttosto inefficiente di farlo. Questo effetto è noto come clustering primario perché il
una nuova chiave JFK verrà inserita vicino alla chiave precedente con la stessa posizione primaria, GLA.
Significa che otteniamo un 'blocco' continuo di slot riempiti, e ogni volta che cerchiamo di inserire una chiave
che viene inviato nel blocco dalla funzione hash, dovremo testare tutte le posizioni fino a quando non
hit the end of the block, and then make such block even bigger by appending another entry
alla sua fine. Quindi questi blocchi, o cluster, continuano a crescere, non solo se colpiamo lo stesso primario
posizione ripetutamente, ma anche se colpiamo qualsiasi cosa che faccia parte dello stesso cluster. L'ultimo
l'effetto è chiamato clustering secondario. Nota che la ricerca di chiavi è anche negativamente influenzata da
questi effetti di clustering.
94
il risultato della divisione intera per 11, e poi prendi il resto che questo risultato lascia quando di nuovo
diviso per 11. Pertanto vorremmo utilizzare come nostra funzione di hash secondaria h2 (n) = (k/11)%11.
Tuttavia, ciò presenta un ulteriore problema: potrebbe dare zero a un certo punto, e ovviamente
non è possibile testare 'ogni posizione zero'. Una soluzione semplice è semplicemente creare l'hash secondario
funzione uno se quanto sopra valuterebbe a zero, cioè:
(k/11)%11se (k/11)%11=0,
h2 (n) =
1 altrimenti.
I valori di questo per il nostro esempio di set di chiavi sono forniti nella seguente tabella:
Codice PHL ORY GCM HKG GLA AKL FRA LAX DCA BHX
h2 (X1 X2 X3 ) 4 1 1 3 9 2 6 7 2 3
Possiamo quindi procedere dalla situazione in cui eravamo quando si è verificata la prima collisione:
con HKG la prossima chiave da inserire, che provoca una collisione con PHL. Dato che2 (HKG) = 3 noi
ora prova ogni terza posizione a sinistra per trovare uno slot libero:
Si noti che questo non ha creato un blocco. Quando ora cerchiamo di inserire GLA, troviamo di nuovo
la sua posizione principale bloccata da ORY. Dato che2 (GLA)
= 9, ora proviamo ogni nona posizione.
Contando verso sinistra da ORY, questo ci porta (ricominciando da dietro quando arriviamo al
dal primo slot all'ultima posizione in assoluto:
Il nostro esempio è troppo piccolo per dimostrare in modo convincente che questo metodo evita anche i clus-
comportamento, ma in generale lo fa.
It is clear that the trivial secondary hash functionh2 (n) = 1 riduce questo approccio a quello
of linear probing. It is also worth noting that, in both cases, proceeding to secondary positions
a sinistra è semplicemente una convenzione - potrebbe altrettanto bene essere a destra - ma ovviamente ha
deve essere chiarito quale direzione è stata scelta per una particolare tabella hash.
La complessità della ricerca. L'efficienza del double hashing è ancora più difficile da calcolare
rispetto a quella del probing lineare, e quindi presenteremo semplicemente i risultati senza una derivazione.
Con il fattore di carico λ, una ricerca riuscita richiede in media (1/λ) ln(1/(1−λ)) confronti,
e un tentativo non riuscito richiede 1/(1−λ). Nota che è il logaritmo naturale (in base
e = 2.71828...che si verifica qui, piuttosto che il solito logaritmo in base 2. Quindi, l'hash
La complessità temporale della ricerca in una tabella è ancora costante, cioè O(1).
95
10.10 Scegliere buone funzioni hash
In linea di principio, qualsiasi funzione conveniente può essere utilizzata come funzione hash primaria. Tuttavia, cosa
è importante quando si sceglie una buona funzione di hash assicurarsi che distribuisca lo spazio di
distribuire le chiavi possibili sul set degli indici della tabella hash il più uniformemente possibile, o più collisioni rispetto a
sarà necessario. In secondo luogo, è vantaggioso se eventuali cluster potenziali nello spazio di
le chiavi possibili sono spezzate (qualcosa che il resto in una divisione non farà), perché
in questo caso potremmo trovarci con una ‘esecuzione continua’ e problemi di clustering associati in
la tabella hash. Pertanto, quando si definiscono funzioni hash di stringhe di caratteri, non è mai un
buona idea rendere decisivi gli ultimi (o anche i primi) pochi caratteri.
Quando si scelgono le funzioni hash secondarie, per evitare il raggruppamento primario, si deve
per assicurarsi che diverse chiavi con la stessa posizione primaria diano risultati diversi quando
la funzione di hash secondaria viene applicata. In secondo luogo, bisogna fare attenzione a garantire che il
la funzione di hash secondaria non può produrre un numero che abbia un divisore comune con il
dimensione della tabella hash. Ad esempio, se la tabella hash ha dimensione 10, e otteniamo un secondario
una funzione hash che restituisce 2 (o 4, 6 o 8) come risultato, allora solo metà delle posizioni saranno
controllato, il che potrebbe portare a un fallimento (un ciclo infinito, per esempio) mentre la tabella è ancora
mezzo vuoto. Anche per grandi tabelle hash, questo può comunque essere un problema se le chiavi hash secondarie
può essere altrettanto grande. Un rimedio semplice per questo è sempre rendere la dimensione della tabella hash
un numero primo.
Mostra anche il notevole vantaggio che il doppio hashing ha rispetto all'indirizzamento lineare.
quando i fattori di carico diventano grandi. Se l'hashing doppio sia preferibile a
96
catena diretta (che sembra decisamente superiore, ma è generalmente più complessa da implementare e
mantenere) dipende dalle circostanze.
La seguente tabella mostra un confronto delle complessità temporali medie per i diversi
possibili implementazioni dell'interfaccia della tabella:
Le tabelle hash sono considerate piuttosto efficienti: la complessità della ricerca, dell'aggiornamento e della re-
Il recupero è indipendente dalle dimensioni della tabella. In pratica, tuttavia, quando si decide quale approccio
per utilizzare, dipenderà dal mix di operazioni normalmente eseguite. Ad esempio, molte
le cancellazioni e le inserzioni ripetute possono causare problemi di efficienza con alcune strategie delle tabelle hash
gies, come spiegato sopra. Per fare un esempio concreto, se ci sono 4096 voci in un bilanciato
l'albero di ricerca binario, in media richiede 12,25 confronti per completare una ricerca riuscita.
D'altra parte, possiamo aver bisogno di sole 1,39 comparazioni se utilizziamo una tabella hash, a condizione che
che manteniamo il suo fattore di carico al di sotto del 50 percento. Naturalmente, nonostante il loro vantaggio temporale, noi
non si dovrebbe mai dimenticare che le tabelle hash hanno uno svantaggio considerevole in termini di memoria
richiesti per implementarli in modo efficiente.
97
Capitolo 11
Grafici
Spesso è utile rappresentare le informazioni in una forma grafica più generale rispetto a quella considerata.
fino ad ora, come la seguente rappresentazione delle distanze tra le città:
44
Glasgow Edimburgo
110
215 Newcastle
168
Manchester
286
80
Birmingham
Swansea 119
117
Londra
157
198
Exeter
98
se esiste un modo per andare da A a B, oppure qual è il percorso più breve, o cosa
sarebbe il set di tubi più corto che collega tutte le località. C'è anche il famoso
Il problema del Commesso Viaggiatore che implica trovare il percorso più breve attraverso la struttura
che visita ogni città esattamente una volta.
A D
B C E
4
A D
1 2
1
2 2 E
6
1
2
B 2 3
C
3
In undirected graphs, we assume that every edge can be viewed as going both ways, that is,
un collegamento tra A e B va da A a B così come da B a A. Il primo grafo fornito a
l'inizio di questo capitolo è pesato e non diretto.
Un apathis è una sequenza di nodi o vertici v1 ,v2 , . . . ,v ntale cheioe avio+1sono connessi
da un arco per tutti 1≤i≤n−1. Nota che in un grafo orientato, l'arco da v iotovio+1
è quello che ha la direzione corrispondente. Un cerchio è un percorso non vuoto il cui primo
Il vertice è lo stesso del suo ultimo vertice. Un percorso è semplice se nessun vertice appare su di esso due volte.
l'eccezione di un cerchio, dove il primo e l'ultimo vertice possono essere gli stessi - questo è perché noi
devi 'aprire' il cerchio a un certo punto per ottenere un percorso, quindi questo è inevitabile).
99
Un grafo non orientato è connesso se ogni coppia di vertici ha un percorso che li collega.
Per i grafi diretti, la nozione di connettività ha due versioni distinte: diciamo che un
Un grafo orientato è debolmente connesso se per ogni due vertici A e B esiste un percorso da A
percorso da B a A. Diciamo che è fortemente collegato se ci sono percorsi che portano in entrambi i sensi
quindi, in un digrafo debolmente connesso, potrebbero esserci due vertici i e j tali che ci
non esiste alcun percorso da imitoj.
Un grafo ha chiaramente molte proprietà simili a quelle di un albero. Infatti, qualsiasi albero può essere visto
come un grafo semplice di un particolare tipo, cioè uno che è connesso e non contiene cerchi.
Perché un grafo, a differenza di un albero, non viene fornito con un ‘punto di partenza’ naturale da cui
c'è un percorso unico per ogni vertice, non ha senso parlare di genitori e figli
in un grafo. Invece, se due vertici A e B sono collegati da un arco e, diciamo che sono
i vicini, e il bordo che li connette è detto incidenti a A e B. Due bordi
che hanno un vertice in comune (ad esempio, uno che collega A e B e uno che collega B
eC) si dicono adiacenti.
Implementazione basata su array. La prima idea fondamentale per le implementazioni basate su array
è che possiamo rinominare convenientemente i vertici del grafo in modo che siano etichettati da
indici interi non negativi, diciamo da 0 a n−1, se non hanno già queste etichette.
Tuttavia, questo funziona solo se il grafo è fornito esplicitamente, cioè se sappiamo in anticipo come
quanti vertici ci saranno e quali coppie avranno archi tra di loro. Poi dobbiamo solo
per tenere traccia di quale vertice ha un arco verso quale altro vertice e, per i grafi pesati,
quali sono i pesi sugli archi. Per i grafi non pesati, possiamo farlo piuttosto facilmente in
ann×ntwo-dimensional binary arrayadj, anche chiamato matrice, il cosiddetto adiacente
matrice. Nel caso di grafi pesati, abbiamo invece una matrice pesi n×n.
Le rappresentazioni in array/matrice per i due esempi di grafi mostrati sopra sono quindi:
A B C D E A B C D E
0 1 2 3 4 0 1 2 3 4
A 00 1 0 1 0 Un 0 0 1∞4∞
B 10 0 1 0 0 B 1 2 0 2 2 6
C 21 0 0 0 1 C 2∞3 0 2 1
D 30 0 1 0 1 D 3 ∞ ∞ ∞0 1
E 40 0 0 0 0 E 4∞ ∞ 3 2 0
100
Nel primo caso, per il grafo non pesato, un '0' nella posizione adj[i][j] viene letto come falso, che
non c'è un arco dal vertice i al vertice j. Un '1', d'altra parte, viene letto come vero,
indica che c'è un bordo. È spesso utile utilizzare valori booleani qui, piuttosto che il
numeri 0 e 1, perché ci consente di eseguire operazioni sui booleani. Nella seconda
Nel caso, abbiamo un grafo pesato e abbiamo i pesi reali nella matrice invece,
utilizzando il simbolo dell'infinito ∞ per indicare quando non c'è un bordo.
Per un grafo non orientato, se c'è un 1 nella colonna i-esima e nella riga j-esima, sappiamo che
c'è un arco dal vertice i al vertice con il numero j, il che significa che c'è anche un
lato dal vertice j al vertice i. Questo significa che adj[i][j] == adj[j][i] sarà vero per tutti
iandjda 0 a n−1, quindi c'è alcune informazioni ridondanti qui. Diciamo che tale un
La matrice è simmetrica: è uguale alla sua immagine speculare lungo la diagonale principale.
0 1 2 3 4
Se ci sono pochissimi bordi, avremo molto
brevi elenchi per ogni voce dell'array, così da salvare
spazio superiore alla matrice di adiacenza/peso
rappresentazione. Questa implementazione sta usando
1 0 1 4 2 cosiddette liste di adiacenza. Nota che se siamo
1 2 3 1 3 considerando i grafi non orientati, c'è ancora
una certa quantità di ridondanza in questo rip-
presentazione, poiché ogni bordo è rappresentato
due volte, una in ciascuna lista corrispondente a
3 2 3 3 due vertici che collega. In Java, questo potrebbe
essere realizzati con qualcosa come:
4 2 2 2
classe Grafico {
Vertici[] teste;
classe privata Vertice {
3 4
int nome;
2 1 doppio peso;
Vertice successivo;
...//metodi per vertici
}
4 ...//metodi per grafi
6 }
101
Implementazione basata su puntatori. L'implementazione standard basata su puntatori degli alberi binari
Gli alberi, che sono essenzialmente una generalizzazione delle liste collegate, possono essere generalizzati per i grafi. In un
In un linguaggio come Java, un classGraph potrebbe avere quanto segue come classe interna:
classe Vertice {
string nome;
Vertice[] vicini;
double[] pesi;
}
Quando ogni vertice viene creato, un array vicini abbastanza grande da contenere (puntatori a)
tutti i suoi vicini viene allocato, con (per grafi ponderati) un array di dimensioni uguali pesi
accomodare i pesi associati. Poi collocchiamo i vicini di ciascun vertice in quelli
array in un ordine arbitrario. Qualsiasi voce nell'array dei vicini che non è necessaria verrà
mantieni un nullpointer come al solito. Ad esempio, il grafo pesato sopra sarebbe rappresentato
come segue, con ogni peso mostrato dopo il puntatore associato:
0 1 4 3 1
4 2 3
1 2 2 2 6 2 3 2 1
102
Una suddivisione di un grafo G può essere definita come un grafo risultante dalla suddivisione dei lati.
in G. Due grafi G e H possono quindi essere definiti come omoeomorfi se esiste un grafo
isomorfismo da un certo sottogruppo di G a un certo sottogruppo di H.
Una contrazione di un arco rimuove un arco da un grafo e unisce i due vertici precedentemente.
connected by it. This can lead to multiple edges between a pair of vertices, orself-loops
collegare un vertice a se stesso. Questi non sono consentiti nei grafi semplici, nel qual caso alcuni
i bordi possono dover essere eliminati. Allora un grafo non orientato H è detto un minore di un altro
grafo non orientato G se un grafo isomorfo a H può essere ottenuto da G contratti alcuni
bordo, eliminando alcuni bordi e eliminando alcuni vertici isolati.
11.4 Planarity
Un grafo pianificabile è un grafo che può essere incorporato in un piano. In altre parole, può essere disegnato
su un foglio di carta in modo che i bordi non si incrocino. Questo è importante in
applicazioni come la progettazione di circuiti stampati.
Si noti che è chiaramente possibile disegnare grafi planari in modo tale che il loro
i bordi si incrociano, ma la cosa cruciale è che possono essere trasformati (muovendo
vertici e/o deformando i lati) in una forma senza alcun incrocio di lati. Ad esempio,
i seguenti tre diagrammi rappresentano tutti lo stesso grafo planare:
Questo grafo è il grafo completamente connesso con quattro vertici, noto come K4 . Chiaramente tutti i subtitoli
i grafici di questo saranno anche planari.
In realtà è piuttosto difficile formulare algoritmi generali per determinare se un
Il grafo dato è planare. Per grafi piccoli, è facile controllare sistematicamente che non ci siano
ripositionamenti possibili dei vertici o deformazioni dei bordi che porteranno il grafo in modo esplicito
forma planare. Due grafi leggermente più grandi di K4che può essere dimostrato non planare in questo
graphico completamente connesso con cinque vertici, noto come K5 , e il grafico con tre
vertici completamente connessi ad altri tre vertici, noti come K3,3 :
Chiaramente, qualsiasi grafo più grande che contenga uno di questi due grafi non planari come sottografo deve
può essere non planare esso stesso, e qualsiasi suddivisione o levigatura dei bordi non avrà effetto su
103
la planarità. Infatti, si può dimostrare che questi due grafi formano la base di alcuni utili
teoremi sulla planarità. Il più noto di questi è il teorema di Kuratowski che afferma
un grafo finito è planare se e solo se non contiene un sottografo che è omeomorfo
a, o un sottoinsieme di, K5orK3,3 . Un altro, basato sul concetto di minorenni, è di Wagner
il teorema che afferma che “un grafo finito è planare se e solo se non ha K5orK3,3
come minorenne
Un buon approccio generale per testare la planarità è quindi cercare sottografi di
given graph that can be transformed intoK5orK3,3 Questo non è del tutto semplice,
ma esistono algoritmi che consentono di testare la planarità di un grafo con n vertici con
complessità temporale O(n). Esercizio: scopri esattamente come funzionano questi algoritmi.
104
formulando il percorso come un albero di ricerca e osservando l'ordine in cui si trovano gli elementi
aggiunto e processato.
Nota che sia con la ricerca in ampiezza che con la ricerca in profondità, l'ordine dei vertici dipende da
implementazione. Non c'è motivo perché il vicino di A, B, debba essere visitato prima di D nella
Esempio. Quindi è meglio parlare di un risultato di una ricerca in ampiezza o in profondità, piuttosto che
risultato. Nota anche che gli unici vertici che saranno elencati sono quelli nello stesso
compontenti connesse A. Se dobbiamo assicurarci che tutti i vertici siano visitati, potrebbe essere necessario
per avviare il processo di attraversamento con un numero di diversi vertici di partenza, scegliendo ogni volta
quello che non è stato contrassegnato come fatto quando la traversata precedente è terminata.
Esercizi: Scrivi algoritmi, in pseudocodice, per (1) visitare tutti i nodi di un grafo e (2) decidere
se un dato grafo è connesso o meno. Per (2) avrai effettivamente bisogno di due algoritmi,
uno per la forte nozione di connessione, e un altro per la debole nozione.
Note that the weights do not necessarily have to correspond to distances; they could, for
esempio, essere tempo (nel qual caso potremmo parlare di “percorsi più rapidi”) o denaro (nel qual caso
potremmo parlare di "percorsi più economici"), tra le altre possibilità. Considerando "astratto"
grafi in cui i pesi numerici sono lasciati non interpretati, possiamo occuparci di tutti tali
situazioni e altri. Ma nota che dobbiamo limitare i pesi dei bordi affinché siano non-
numeri negativi, perché se ci sono numeri negativi e cicli, possiamo avere sempre di più
percorsi lunghi con costi sempre più bassi, e nessun percorso con costo minimo.
Le applicazioni degli algoritmi del cammino più corto includono l'instradamento dei pacchetti internet (perché, se
send an email message from your computer to someone else, it has to go through various
email routers, until it reaches its final destination), train-ticket reservation systems (that
devo capire le migliori stazioni di collegamento), e i trovatori di percorsi di guida (che devono trovare
un percorso ottimale in un certo senso).
105
l'algoritmo finisce. Tuttavia, prima che l'algoritmo termini, D[z] è la migliore sovrastima
attualmente abbiamo la distanza da stoz. Inizialmente abbiamo D[s] = 0 e impostiamo D[z] = ∞
per tutti i vertici oltre i nodi di partenza. Poi l'algoritmo riduce ripetutamente il
sovrastimazioni fino a quando non è più possibile ridurle ulteriormente. Quando ciò accade, il
l'algoritmo termina, con ogni stima completamente vincolata e definita come rigorosa.
dell'intero algoritmo riportato di seguito. Il problema è quindi ridotto a sviluppare un algoritmo che
applicheremo sistematicamente questo miglioramento in modo che (1) alla fine otteniamo le stime precise
promesso sopra, e (2) che venga fatto nel modo più efficiente possibile.
L'algoritmo di Dijkstra, Versione 1. La prima versione di un tale algoritmo non è così efficiente
come potrebbe essere, ma è relativamente semplice e sicuramente corretto. (È sempre una buona idea per
inizia con un algoritmo semplice inefficiente, in modo che i risultati di esso possano essere utilizzati per verificare
il funzionamento di un algoritmo più complesso ed efficiente.) L'idea generale è che, ad ogni fase
dell'operazione dell'algoritmo, se un entryD[u] dell'arrayD ha il valore minimo tra
tutti i valori registrati in D, quindi la sovrastima D[u] deve essere effettivamente precisa, perché il
L'algoritmo di miglioramento discusso sopra non può certamente trovare un scorciatoia.
L'algoritmo seguente implementa questa idea:
106
// Aggiorniamo ripetutamente gli array ‘D’ e ‘tight’ fino a
// tutte le voci nell'array 'tight' contengono il valore true.
È chiaro che quando questo algoritmo termina, le voci di D non possono contenere stime inferiori di
le lunghezze dei percorsi più brevi. Ciò che forse non è così chiaro è perché le stime siano valide
sono realmente stretti, cioè sono le lunghezze minime dei percorsi. Per capire il perché, prima nota
che un sotto-percorso iniziale di un percorso più breve è esso stesso un percorso più breve. Per vedere questo, supponiamo che
desideri navigare da un vertice s a un vertice z, e che il percorso più breve da s a
accade di passare attraverso un certo vertice. Allora il tuo percorso da può essere suddiviso in
two paths, one going fromstou(an initial sub-path) and the other going fromutoz(a
sotto-percorso finale). Dato che l'intero percorso non diviso è un percorso più breve da s a z, l'iniziale
Il sottopercorso deve essere il cammino più breve da s a t, perché altrimenti potresti accorciare il tuo percorso.
sostituendo la sottoparola iniziale con una più breve, che non darebbe solo
un percorso più breve da stoubut anche da sto la destinazione finale z. Ora segue che per
Qualsiasi vertice di partenza, c'è un albero dei percorsi più brevi da quel vertice a tutti gli altri vertici. Il
il motivo è che i percorsi più brevi non possono avere cicli. Implicitamente, l'algoritmo di Dijkstra costruisce
questo albero a partire dalla radice, cioè dal vertice di partenza.
Se, come tende a essere il caso in pratica, desideriamo anche calcolare il percorso più breve,
anziché solo la sua lunghezza, dobbiamo anche introdurre un terzo array per tenere traccia del
’predecessore’ o ‘vertice precedente’ di ciascun vertice, in modo che il percorso possa essere seguito all'indietro da
il punto finale al punto di partenza. L'algoritmo può chiaramente essere adattato per lavorare con
grafi non pesati assegnando una matrice di pesi adeguata di 1 per i vertici connessi e
0s per vertici non connessi.
La complessità temporale di questo algoritmo è chiaramente O(n2 ) dove è il numero di vertici,
poiché ci sono operazioni di O(n) annidate all'interno del ripeti di O(n).
107
Un'implementazione diretta dell'algoritmo sopra, con del codice aggiunto per stampare lo stato
dei tre array a ciascuna fase intermedia, fornisce il seguente output, in cui "oo" è
usato per rappresentare il simbolo dell'infinito “∞”:
|A B C D E
--------+---------------------------------------
D |0 oo oo oo oo
stretto no no no no no
pred. |none nessuno none nessuno nessuno
A B C D E
--------+---------------------------------------
D 0 1 oo 4 oo
stretto sì no no no no
pred. nessuno A none A nessuno
|A B C D E
--------+---------------------------------------
D 0 1 3 3 7
stretto sì sì no no no
pred. |nessuno A B B B
|A B C D E
--------+---------------------------------------
D 0 1 3 3 4
stretto sì sì sì no no
sia. |none A B B C
108
Il vertice D ha una stima minima, ed è quindi vincolante.
|A B C D E
--------+---------------------------------------
D |0 1 3 3 4
stretto sì sì sì sì no
pred. |nessuno A B B C
A B C D E
--------+---------------------------------------
D |0 1 3 3 4
stretto sì sì sì yes sì
pred. |none A B B C
Once it is clear what is happening at each stage, it is usually more convenient to adopt a
notazione abbreviata che consente di rappresentare l'intero processo in un'unica tabella. Per
esempio, usando un "*" per rappresentare stretto, la distanza, lo stato e il predecessore per ciascun nodo a
ogni fase del esempio sopra può essere elencata in modo più conciso come segue:
Fase | A B C D E
-------+------------------------------------------------
1 0 oo oo oo oo
2 | 0 * 1 A oo 4 A oo
3 0 * 1 * A 3 B 3 B 7 B
4 | 0 * 1 * A 3 * B 3 B 4 C
5 | 0 * 1 * A 3 * B 3 * B 4 C
6 | 0 * 1 * A 3 * B 3 * B 4 * C
109
Un grafo orientato con matrice dei pesi 'peso' e
// un vertice di partenza 's'.
Un array 'D' di distanze come spiegato sopra.
110
sparsewithe=O(n). Cioè, di solito non ci sono molti più archi che vertici, e in
in questo caso la complessità temporale per entrambe le versioni della coda di priorità è O(n log2n), che è chiaro
miglioramento rispetto al precedente O(n2 ) algoritmo.
Come per l'algoritmo di Dijkstra, questo può essere facilmente adattato al caso di grafi non pesati
assegnando una matrice di pesi adeguata di 0 e 1.
La complessità temporale qui è chiaramente O(n3 ), poiché coinvolge tre cicli for annidati di O(n).
Questa è la stessa complessità dell'esecuzione di O(n)2 L'algoritmo di Dijkstra una volta per ciascuno di loro
vertici di partenza possibili. In generale, tuttavia, l'algoritmo di Floyd sarà più veloce di quello di Dijkstra,
anche se entrambi appartengono alla stessa classe di complessità, perché il primo esegue meno
111
istruzioni in ciascun passaggio attraverso i cicli. Tuttavia, se il grafo è sparso con e=O(n),
quindi possono essere eseguite più esecuzioni dell'algoritmo di Dijkstra con complessità temporale
O(n2 registro2n), e essere più veloce dell'algoritmo di Floyd.
Un esempio semplice. Supponiamo di voler calcolare le lunghezze dei percorsi più brevi tra
tutti i vertici nel seguente grafo pesato non orientato:
Iniziamo con la matrice delle distanze basata sui pesi di connessione e sui predecessori banali:
A B C D E A B C D E
A 0 1 14 4 ∞ A A A A A A
B 1 0 ∞ ∞ 2 B B B B B B
Inizia
C 14 ∞ 0 8 10 C C C C C C
D 4 ∞ 8 0 1 D D D D D D
E ∞ 2 10 1 0 E E E E E E
Quindi, per ogni vertice a turno, testiamo se un percorso più breve tramite quel vertice riduce uno dei
distanze e aggiornare gli array delle distanze e dei predecessori con eventuali riduzioni trovate. Il
cinque passaggi, con le voci aggiornate tra virgolette, sono come segue::
A B C D E A B C D E
A 0 1 14 4 ∞ A A A A A A
B 1 0 ‘15’ ‘5’ 2 B B B ["'A'","'A'"] B
A:
C 14 '15' 0 8 10 C C ‘A’ C C C
D 4 5 8 0 1 D D ‘A’ D D D
E ∞ 2 10 1 0 E E E E E E
A B C D E A B C D E
A 0 1 14 4 3 A A A A A ‘B’
B 1 0 15 5 2 B B B A A B
B:
C 14 15 0 8 10 C C A C C C
D 4 5 8 0 1 D D A D D D
E 3 2 10 1 0 E B E E E E
A B C D E A B C D E
A 0 1 14 4 3 A A A A A B
B 1 0 15 5 2 B B B A A B
C:
C 14 15 0 8 10 C C A C C C
D 4 5 8 0 1 D D A D D D
E 3 2 10 1 0 E B E E E E
112
A B C D E A B C D E
A 0 1 ‘12’ 4 3 A A A ‘D’ A B
B 1 0 13 5 2 B B B ‘D’ A B
D:
C ‘12’ ‘13’ 0 8 ‘9’ C ‘D’ A C C ‘D’
D 4 5 8 0 1 D D A D D D
E 3 2 9 1 0 E B E D E E
A B C D E A B C D E
A 0 1 12 4 3 A A A D A B
B 1 0 ‘11’ ‘3’ 2 B B B D ‘E’ B
E:
C 12 '11' 0 8 9 C D È C C D
D 4 ‘3’ 8 0 1 D D ‘È’ D D D
E 3 2 9 1 0 E B E D E E
A
sei 5
B 1 C
5 5
D
6 4
3 6 2
E F
Potremmo considerare i vertici come rappresentanti di case, e i pesi come le distanze tra.
loro. Ora immagina di essere incaricato di rifornire tutte queste case con una qualche merce
come acqua, gas o elettricità. Per ovvi motivi, vorrai mantenere la quantità di
scavare e posare tubi o cavi al minimo. Quindi, qual è la migliore disposizione di tubi o cavi
che puoi trovare, cioè quale disposizione ha la lunghezza complessiva più corta?
Ovviamente, dovremo scegliere alcuni dei bordi lungo cui scavare, ma non tutti.
esempio, se abbiamo già scelto il bordo tra A e D, e quello tra B e
D, quindi non c'è motivo di avere anche quello tra A e B. Più in generale, è chiaro
che vogliamo evitare cerchi. Inoltre, supponendo di avere solo un punto di alimentazione (è di
non importa quale dei vertici esso sia), abbiamo bisogno che l'intero layout sia connesso. Noi
Abbiamo già visto che un grafo connesso senza circoli è un albero.
113
Pertanto, ciò che stiamo cercando è un albero di copertura minimo del grafo. Un albero di copertura
of a graph is asubgraphthat is a tree which connects all the vertices together, so it ‘spans’ the
grafico originale ma utilizzando meno spigoli. Qui, minimo si riferisce alla somma di tutti i pesi di
i lati contenuti in quell'albero, quindi un albero di copertura minimo ha un peso totale inferiore o uguale
al peso totale di ogni altro albero di copertura. Come vedremo, non ci sarà necessariamente
un albero di copertura minimale unico per un grafo dato.
Osservazioni riguardanti gli alberi di copertura. Per gli altri algoritmi sui grafi abbiamo cov-
finora, abbiamo iniziato facendo alcune osservazioni che ci hanno permesso di arrivare a una
idea per un algoritmo, così come una strategia per formulare una prova che l'algoritmo ha funzionato
in effetti performare come desiderato. Quindi, per trovare alcune idee che ci consentiranno di sviluppare un
algoritmo per il problema dell'albero di copertura minimo, dovremo fare alcune osservazioni
riguardo agli alberi di copertura minimi. Supponiamo, per il momento, che tutti i pesi nel
Il grafico sopra era uguale, per darci un'idea del tipo di forma di un albero di copertura minimo.
potrebbe avere in queste circostanze. Ecco alcuni esempi:
Possiamo notare immediatamente che la loro forma generale è tale che se aggiungiamo uno qualsiasi dei restanti
dai bordi, creeremmo un cerchio. Quindi possiamo vedere che passando da un albero di copertura a un altro
può essere ottenuto rimuovendo un arco e sostituendolo con un altro (verso il vertice che sarebbe
altrimenti essere scollegato) in modo tale che non venga creato alcun cerchio. Queste osservazioni non sono del tutto
sufficienti a portare a un algoritmo, ma sono abbastanza buoni da permitirci di dimostrare che gli algoritmi
troviamo che funziona davvero.
Algoritmi Greedy. Diciamo che un algoritmo è greedy se prende le sue decisioni basandosi solo
su ciò che è meglio dal punto di vista delle 'considerazioni locali', senza preoccuparsi di come il
la decisione potrebbe influenzare l'immagine complessiva. L'idea generale è di iniziare con un'approssimazione,
come abbiamo fatto nell'algoritmo di Dijkstra, e poi affinato in una serie di passaggi. L'algoritmo è
avido nel senso che la decisione in ciascun passo si basa solo su ciò che è meglio per il prossimo
step, and does not consider how that will affect the quality of the final overall solution. We
considereremo ora alcuni approcci greedy al problema dell'albero di copertura minimo.
L'algoritmo di Prim - Un approccio goloso basato sui vertici. Supponiamo di avere già
un albero di copertura che collega un certo insieme di vertici S. Possiamo quindi considerare tutti i lati che
collegare un vertice in Sto uno all'esterno di S, e aggiungere a S uno di quelli che ha peso minimo.
Questo non può assolutamente creare un cerchio, poiché deve aggiungere un vertice non ancora in S. Questo processo può
essere ripetuto, iniziando con qualsiasi vertice per essere l'unico elemento di S, che è un minimo banale
albero di copertura che non contiene bordi. Questo approccio è conosciuto come l'algoritmo di Prim.
Quando si implementa l'algoritmo di Prim, si può utilizzare sia un array che una lista per tenere traccia
del insieme dei vertici S raggiunti finora. Si potrebbe quindi mantenere un altro array o elenco più vicino
che, per ogni vertice non ancora in S, tiene traccia del vertice in S più vicino a i. Cioè, il
114
vertice in S che ha un arco verso i con peso minimo. Se closest tiene anche traccia del
i pesi di quei bordi, potremmo risparmiare tempo, perché dovremmo poi solo controllare il
pesi menzionati in quell'array o elenco.
Per il grafico sopra, partendo da S={A}, l'albero è costruito come segue:
A A A
1 1 1
B C B C B C
4 4 2
D D D
E F E F E F
A A
1 1
B 5 C B 5 C
4 2 3 4 2
D D
E F E F
È leggermente più difficile produrre un argomento convincente che questo algoritmo realmente
funziona meglio di quanto sia stato per gli altri algoritmi che abbiamo visto finora. È chiaro che l'algoritmo di Prim
l'algoritmo deve risultare in un albero di spanning, perché genera un albero che comprende tutti i vertici,
ma non è ovvio che sia minimo. Ci sono diversi possibili prove che lo sia, ma nessuna
sono diretti. I più semplici funzionano mostrando che l'insieme di tutti i possibili minimi
alberi di coperturaiodeve includere l'output dell'algoritmo di Prim.
Sia Y l'output dell'algoritmo di Prim, e X1sia un qualsiasi albero di copertura minimo. Il
quanto segue illustra una situazione del genere:
Non abbiamo realmente bisogno di sapere cosa X1è - dobbiamo solo conoscere le proprietà che deve avere
soddisfare, e poi lavorare sistematicamente attraverso tutte le possibilità, dimostrando che Y è minimo
spanning tree in each case. Clearly, ifX1=Y, allora l'algoritmo di Prim ha generato un minimo
albero di copertura. Altrimenti, lascia la prima edge aggiunta a Y che non è in X1 . Poi, poiché
X1è un albero di copertura, deve includere un percorso che collega i due estremi di e, e perché
circles are not allowed, there must be an edge inX1quello non è inY, che possiamo chiamaref.
Poiché l'algoritmo di Prim aggiunge invece di f, sappiamo che peso(e)≤peso(f). Allora crea
treeX2quello è X1con sostituito bye. Chiaramente X2è connesso, ha lo stesso numero di
bordi come X1 , abbraccia tutti i vertici e ha un peso totale non maggiore di X1 , quindi deve anche
115
essere un albero di copertura minimale. Ora possiamo ripetere questo processo fino a quando non abbiamo sostituito tutto il
bordo inX1che non sono in Y, e finiamo con l'albero di copertura minimo Xn=Y, che
completa la prova che Y è un albero di copertura minimale.
La complessità temporale dell'algoritmo standard di Prim è O(n2 ) perché ad ogni passo noi
devi scegliere un vertice da aggiungere a S, e poi aggiornare l'array closest, non dissimile da
la forma più semplice dell'algoritmo di Dijkstra. Tuttavia, come per l'algoritmo di Dijkstra, unBinary
Una coda di priorità basata su heap binomiale può essere utilizzata per velocizzare le operazioni tenendo traccia di
qual è il vertice di peso minimo da aggiungere per primo. Con una rappresentazione della lista di adiacenza,
questo può ridurre la complessità a O((e+n)log 2n). Infine, utilizzando il più sofisticato
L'heap di Fibonacci per la coda di priorità può migliorare ulteriormente questo a O(e+nlog) 2n). Quindi, utilizzando
l'approccio ottimale in ogni caso, l'algoritmo di Prim è O(nlog2n) per grafi sparsi che hanno
e=O(n), eO(n2 ) per grafi altamente connessi che hanno e=O(n2 ).
Proprio come nell'algoritmo di Floyd rispetto a quello di Dijkstra, dovremmo considerare se sia davvero
necessario elaborare ogni vertice in ogni fase, perché potrebbe essere sufficiente controllare solo
edge esistenti. Pertanto, ora consideriamo una strategia alternativa basata sui bordi:
L'algoritmo di Kruskal - Un approccio greedy basato sugli archi. Questo algoritmo non con-
prendere in considerazione i vertici direttamente, ma costruisce un albero di copertura minimo considerando e aggiungendo
bordi come segue: Supponiamo di avere già una raccolta di bordiT. Quindi, da tutti i
bordo non ancora in T, scegliere uno con peso minimo in modo che la sua aggiunta a T non
produce a circle, and add that toT. If we start withTbeing the empty set, and continue
fino a quando non possono essere aggiunti ulteriori spigoli, verrà prodotto un albero di copertura minimo. Questo approccio
è conosciuto come l'algoritmo di Kruskal.
Per lo stesso grafo utilizzato per l'algoritmo di Prim, questo algoritmo procede come segue:
1 1 1
B C
D 2 3 2
E F
1 1
5
3 4 2 3 4 2
In pratica, l'algoritmo di Kruskal è implementato in un modo piuttosto diverso rispetto all'algoritmo di Prim.
L'idea generale dei metodi più efficienti è quella di iniziare ordinando i bordi in base a
i loro pesi, e poi semplicemente passare attraverso quell'elenco di archi in ordine di peso crescente, e
o aggiungili a T, o rifiutali se produrrebbero un cerchio. Ci sono implementazioni
di ciò che può essere raggiunto con una complessità temporale totale O(elog2e), che è dominato
daO(elog2e) complessità di ordinare i bordi in primo luogo.
Ciò significa che la scelta tra l'algoritmo di Prim e l'algoritmo di Kruskal dipende
sulla connettività del particolare grafo in considerazione. Se il grafo è sparso, cioè.
116
il numero di spigoli non è molto superiore al numero di vertici, allora l'algoritmo di Kruskal
avrà lo stesso O(nlog2n) complessità come le versioni basate sulla coda di priorità ottimale di
L'algoritmo di Prim, ma sarà più veloce rispetto allo standard O(n2 ) L'algoritmo di Prim. Tuttavia, se
il grafo è altamente connesso, cioè il numero di archi è vicino al quadrato del numero di
vertici, avrà complessità O(n2 registro2n) e essere più lento dell'ottimale O(n2 ) versioni
dell'algoritmo di Prim.
un numero di clienti con una flotta di veicoli a costo minimale, dove quel costo può essere
il numero di veicoli richiesti, la distanza totale percorsa o il tempo totale di guida richiesto.
Spesso, per casi pratici, ci sono conflitti tra i vari obiettivi, e lì
c'è un compromesso tra i vari costi che devono essere bilanciati. In tali casi, un multi-
è necessario un approccio di ottimizzazione obiettivo che restituisca un fronte di Pareto non dominato
soluzioni, cioè un insieme di soluzioni per le quali non ci sono altre soluzioni che sia migliori in tutti
obiettivi. Inoltre, in pratica, ci sono di solito varie limitazioni coinvolte, come fisse
finestre temporali di consegna, o veicoli a capacità limitata, che devono essere soddisfatti, e che rende
trovare buone soluzioni ancora più difficile.
Poiché soluzioni esatte a questi problemi sono attualmente impossibili per tutti tranne che per i più piccoli
nei casi, si usano di solito approcci euristici, come il calcolo evolutivo, che
fornire soluzioni che sono probabilmente buone ma non possono essere dimostrate ottimali. Una popolare
l'approccio consiste nel mantenere un'intera popolazione di soluzioni e utilizzare l'evoluzione simulata tramite
selezione naturale per migliorare iterativamente la qualità di quelle soluzioni. Questo ha l'ulteriore
vantaggio di poter generare un intero fronte di Pareto di soluzioni invece di una sola
soluzione. Questo è attualmente ancora un'area di ricerca molto attiva.
117
Capitolo 12
Epilogo
Speriamo che il lettore sia d'accordo sul fatto che queste note abbiano raggiunto il loro obiettivo di introdurre
le strutture dati di base utilizzate nella scienza informatica e mostrare come possono essere utilizzate in
il design di algoritmi utili ed efficienti. Le strutture dati di base (array, liste, pile,
le code e gli alberi sono stati utilizzati in tutto, e usati come base del cruciale pro-
cessi, come memorizzare, ordinare e cercare dati, che sottendono a molte scienze informatiche
applicazioni. È stato dimostrato come idee dalla combinatoria e dalla probabilità
La teoria può essere utilizzata per calcolare l'efficienza degli algoritmi in funzione della dimensione del problema. Noi
118
Appendice A
√
√nanb=ab √n am/n=am=a √n √n m
√na / √n b = n a / b a−(m/n) = 1/(am ) =√n 1/(a) √n m
p
A.3 Logaritmi
Definizione: Il logaritmo di c con base a, scritto come logac è il numero reale che soddisfa il
equazionec=ab , in cui assumiamo che c > 0 e a > 1.
Ci sono due casi speciali da notare, vale a dire loguna1 = 0, poiché0= 1, e logaa= 1,
sincera1Dalla definizione, vediamo immediatamente che:
registroa0b= loga0a∗logunb.
119
Le regole chiave per i logaritmi sono:
logan=nloga
√n
loga= (1/n) loga
A.4 Sums
Spesso troviamo utile abbreviare una somma come segue:
n
s= ai=a1+a2+a3+· · ·+an
X
i=1
double s = 0
per ( i = 1 ; i <= n ; i++ )
s = s + a[i]
calcola la somma. L'uso più comune delle somme per i nostri scopi è quando si indaga su
complessità temporale di un algoritmo o programma. Per questo, spesso dobbiamo contare una variante di
1 + 2 +· · ·+n, so it is helpful to know that:
n
i = 1 + 2 + ... + n =
n(n+ 1)
X .
2
i=1
120
Usando la formula sopra, la complessità temporale k viene calcolata come segue:
Altre due somme che spesso si rivelano utili quando si calcolano complessità sono:
∞1 1 1 1 1
=1++++ +. . .= 2
X 2io 2 4 8 16
i=0
∞ io 1 2 3 4
=0++++ +. . .= 2
X 2i 2 4 8 16
i=0
n
io 1 2 3 n
= 0 + + + + . . .+
X 2io 2 4 8 2n 2 =O(1)
i=0
che sono necessari per calcolare la complessità della creazione di un albero heap e alcuni casi speciali
di quicksort.
Fn=Fn−1+Fn−2
con i valori di baseF0= 0, F1= 1. Quindi la sequenza inizia 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,
55, 89, 144, 233, 377, ...
121
Indice
tipo di dato astratto, 7, 12, 17, 18, 20, 35, 85 controllo, 46
astrazione, 40 child, 31
accesso, 9, 63 children, 31
metodi accessor, 13 circle, 99, 113
liste di adiacenza, 101 lista doppiamente collegata circolare, 19, 61
matrice di adiacenza, 100 raggruppamento, 94
adiacente, 100 collisione, 88
algoritmo, 5, 6, 15, 21, 26, 118 confrontando, 64
alfabetico, 40, 63 complete, 51
ancestor, 32 complessità, 26
appendi, 15 classe di complessità, 26, 29
arcs, 31, 99 componenti, 105
array, 9, 21, 51, 87, 100 condition, 13, 16, 18, 19, 32, 34
media, 65 connesso, 100, 113
average case, 25, 30, 78 componente connessa, 105
Albero AVL, 49 connection, 99, 100
complessità costante, 27, 92
B-tree, 49
fattore di bilanciamento, 49
fattori costanti, 29
vincoli, 117
bilanciato, 36, 48, 51
costruire, 13
caso base, 13, 32, 34
costruito, 12, 17, 18
miglior caso, 78
costruttori, 12, 13, 16–18, 32, 34
Notazione Big-O, 27
contenere, 102
biiezione, 102
Ordinamento per bin, 83
prove di correttezza, 7, 10
counter, 10
alberi a heap binari, 52, 72, 110, 116
complessità cubica, 27
ricerca binaria, 23
albero di ricerca binaria, 41 dati, 26
albero binario, 33, 34, 41 struttura dati, 5, 7, 21, 35, 85, 118
Heap binomiale, 59, 110, 116 albero decisionale, 65
albero binomiale, 59 Programmazione Dichiarativa, 6
percorso in ampiezza, 104 cancella, 45, 53, 61
bolla giù, 55, 56, 73 depth, 32
ordinamento a bolle, 66
traversata in profondità, 104
bollire, 54–56 operatori derivati, 34
Ordinamento a secchi, 83
procedimenti derivati, 15
secchi, 91 discendente, 32
build, 32, 34, 41, 56 modelli di design, 7
in modo distruttivo, 13
C, 5, 6, 10, 22, 23, 35, 90
122
digrafi, 99 heuristic, 76, 117
L'algoritmo di Dijkstra, 62, 105 omeomorfo, 103, 104
collegamento diretto, 91
diretto, 99 Programmazione Imperativa, 6
dividi e conquista, 74 implementazione, 14, 26, 37, 86
doppio hashing, 92, 94 implementazione, 6, 85
lista doppiamente collegata, 18 incident, 100
indice, 9
contrazione degli spigoli, 103 induction, 13, 32
quad-tree di bordo, 33 passo di induzione, 13, 32, 34
edges, 31, 99 asserzioni induttive, 11
efficienza, 5, 7, 25 inheritance, 41
incorporato, 103 insert, 42, 53, 60, 61, 94
lista vuota, 12 ordinamento per inserimento, 67
123
complessità logaritmica, 27 tipi di dati primitivi, 7
ciclo, 10 operatori primitivi, 16, 32, 34
loop-invariants, 10, 24 priority, 52
limite inferiore, 64 coda di priorità, 52, 72, 109
probabilmente approssimativamente corretto, 65
MakeList, 13 processore, 38
CreaAlbero, 34 programma, 6
matrice, 100 prova, 7, 115
mediana, 79 dimostrazione per induzione, 11, 36
merge, 58, 60, 61, 74, 80 pseudocodice, 5, 6, 10, 15, 22, 26
mergesort, 74, 79 push, 16, 17
albero di copertura minimo, 114
minore, 103, 104 quadtree, 32
aritmetica modulare, 90 complessità quadratica, 27
modulo, 90 queue, 17, 104
ottimizzazione multi-obiettivo, 117 Quicksort, 74, 75
mutatori, 13
Ordinamento radix, 83
124
strategie di ordinamento, 64
complessità spaziale, 25
albero di copertura, 114
sparse, 101, 111, 112
specifica, 7, 22, 85
stability, 71, 72, 74, 77, 80
stack, 16, 38, 104
storing, 9, 12, 40, 51, 85
fortemente connesso, 100
suddivisione, 102-104
sottografi, 102–104, 114
supergruppo, 102
symmetric, 101
table, 85
tre fasi, 84
tre celle, 18
stretto, 106
complessità temporale, 25, 26, 64
time complexity, constant, 15
time complexity, linear, 15, 23, 58, 104
time complexity, logarithmic, 24, 27
time complexity, quadratic, 70
top, 16, 18
trade-off, 25, 117
Problema del commesso viaggiatore, 65, 99, 117
traverso, 104
tree, 31, 100
rotazioni di albero, 48, 49
alberi come array, 51
Treesort, 71
due celle, 12
non direzionale, 99
limite superiore, 64
valore, 31
Problema di percorrenza dei veicoli, 117
verifica, 7, 10
vertices, 31, 99
paradosso del compleanno di von Mises, 88
125