Nozioni Algoritmi e strutture dati

COSTO

Caso peggiore: O( ⋅ lg )

Caso medio: Θ( ⋅ lg )

Caso migliore: Ω() ALGORITMO DI EUCLIDE

Algoritmo per trovare il massimo comune divisore tra due numeri interi

1) Se è allora è il

0 MCD

2) Se allora calcolo il resto della divisione

> 0 ÷ ⇒

= mod

a. Se allora è il

= 0 MCD

b. Se allora prende il valore di e prende il valore

≠ 0

di e si ripete nuovamente la divisione

COSTO

Caso peggiore: 2 )

O(

Caso medio: 2 )

Θ( ALGORITMO DI FIBONACCI

Algoritmo per calcolare la successione dei numeri di Fibonacci nella quale ogni numero è la somma dei due

numeri precedenti.

1. Se o allora il valore restituito è

= 1 = 2 1

2. Da a il numero stampato è

= 3 = ( − 1) + ( − 2)

Esiste una formula per calcolare :

= 1

1

= 2

2

=

1 1 + 1 −

√5 √5

̂

= (Φ − Φ ), Φ = ≈ 1,618 Φ = ≈ −0,618

2 2

√5

{

Nota bene! cresce all’aumentare di

!

Approssimazione di Stirling:

! = ( )

√2

ALGORITMO DI DIJKSTRA

Algoritmo per trovare il percorso minimo tra due vertici di

un grafo

Procedimento

1) Parto dal nodo iniziale

2) Pongo al nodo iniziale il potenziale e a tutti gli

0,

altri nodi l’etichetta ∞

3) Parto dal 1° nodo e analizzo i nodi a cui esso si

collega (se il grafo è diretto considero solo gli archi

uscenti) attribuendo a ciascuno di essi il peso

dell’arco che lo collega al nodo iniziale e togliendo l’etichetta ∞

4) Contrassegno il primo nodo perché ho analizzato tutti i percorsi che partono da lui

5) Passo al nodo che ha il valore minimo al momento e guardo i nodi a cui si collega attribuendo a questi

nodi il valore dell’arco che si collega al nodo di partenza più il valore che il nodo di partenza ha già

rispetto al primo nodo, segnando accanto ad ogni nodo il nodo di partenza

6) Una volta analizzati tutti i nodi e fatta la medesima cosa contrassegno il nodo e passo al nodo

successivo, sempre controllando che sia quello che ha ancora il valore minimo

7) Se per più nodi ricavo valori diversi mantengo sempre quello minimo

8) E così via, fino a quando tutti i nodi saranno contrassegnati

…

9) Una volta terminato questo processo parto dal nodo di cui devo calcolare la distanza rispetto al nodo

iniziale e il valore di tale distanza sarà quello segnato accanto e per ottenere il percorso devo partire

dal nodo finale e, procedendo all’indietro, ricavo tutti i nodi per cui sono passata tramite il nodo di

partenza di ogni nodo di passaggio.

Da usare quando gli archi hanno pesi diversi

Nota bene! Se gli archi non sono pesati o hanno tutti lo stesso peso, basta usare BFS

COSTO

Caso peggiore: ||)

O((|| + ⋅ lg )

Caso medio: ||)

Θ((|| + ⋅ lg )

Caso migliore: 2 | ||)

Ω(| +

Algoritmi di ordinamento Se le persone credono che la matematica non sia semplice, è

soltanto perché non si rendono conto di quanto la vita sia

complicata.

(John von Neumann)

BUBBLE SORT Ogni coppia di elementi adiacenti viene

comparata e invertita di posizione se sono

nell'ordine sbagliato. L'algoritmo continua

nuovamente a ri-eseguire questi passaggi per

tutta la lista finché non vengono più eseguiti

scambi, situazione che indica che la lista è

ordinata.

1) Inizia con il primo elemento e lo confronta con

quello adiacente a. Se sono già ordinati li lascia così

b. Se non sono già ordinati li scambia

2) Passa al secondo elemento e lo confronta con il terzo

a. Se sono già ordinati li lascia così

b. Se non sono già ordinati li scambia

3) Guarda il terzo e il quarto elemento e li confronta

4) E così via fino ad arrivare alla fine dell’array

5) Se gli elementi non sono ancora ordinati riparte dal primo e ricomincia la proceduta

6) Alla fine, tutti gli elementi saranno ordinati

Da usare quando l’array ha piccole dimensioni e inoltre è già parzialemente ordinato.

COSTO

Caso peggiore: 2 )

O(

Caso medio: 2 )

Θ(

Caso migliore: Ω()

INSERTION SORT

Per capire! INSERTION SORT opera nello stesso modo in cui molte persone

ordinano un mazzo di carte.

1. iniziamo con la mano sinistra vuota e le carte poste sul tavolo.

2. Prendiamo una carta e la inseriamo nella posizione corretta nella

mano sinistra. Per trovare la posizione corretta di una carta la

confrontiamo con quelle già presenti nel mazzo, da destra a

sinistra.

N.B. In qualsiasi momento nella mano sinistra ci sono le carte, che

prima erano in cima alla pila di carte sul tavolo, ordinate.

Explanation:

1) Parto da un array non ordinato

2) Parto dal primo elemento dell’array che considerato già ordinato

3) Prendo il secondo elemento dell’array

4) Confronto il secondo elemento dell’array con quello alla sua sua sinistra (con il primo elemento)

a. Se il primo elemento è minore del secondo elemento allora gli elementi sono già ordinati

b. Se il primo elemento è maggiore del secondo elemento allora inserisco il secondo elemento

prima del primo elemento

5) Passo al terzo termine che confronto con quello alla sua sinistra (il secondo

termine)

a. Se il secondo elemento è minore del terzo elemento allora gli

elementi sono già ordinati

b. Se il secondo elemento è maggiore del terzo elemento allora

inserisco il terzo elemento prima del secondo elemento e lo confronto

con quello alla sua sinistra (il primo elemento)

i. Se il primo elemento è minore del terzo elemento allora gli elementi sono ordinati

ii. Se il primo elemento è maggiore del terzo elemento allora inserisco il terzo elemento

prima del primo elemento

6) Così via fino a quando l’array non sarà completamente ordinato in senso crescente

Lati positivi:

Ordina gli elementi sul posto risparmia memoria

⇒

Semplice da implementare

Efficiente per ordinare un piccolo numero di elementi o insiemi di partenza quasi ordinati

Da usare quando l’array ha piccole dimensioni oppure l’array è già quasi ordinato

COSTO

Caso peggiore (numeri disposti in ordine decrescente): 2 )

O(

Caso medio (numeri già ordinati) 2 )

Θ(

Caso migliore: Ω() METODO DIVIDE ET IMPERA

Suddivide il problema in vari sottoproblemi, più facili da risolvere singolarmente e poi ricombina le soluzioni

ottenute. Θ(1) se ≤

Costo di un algoritmo Divide et Impera: () = {

⋅ ( ) + () + () negli altri casi

tempo per suddividere il problema

(): tempo per ricombinare le soluzioni

():

MERGE SORT La sequenza viene divisa in due metà (divide)

Ognuna di queste sottosequenza viene ordinata applicando

ricorsivamente l’algoritmo (impera)

Le due sottosequenze ordinate vengono fuse tramite la

funzione ausiliaria MERGE per riordinare quella originaria

(combina)

Procedimento

1. La sequenza di numeri di partenza viene divisa di volta in volta a

metà, fino ad arrivare agli elementi singoli

2. Gli elementi vengono ordinati a due a due con la procedura

MERGE

3. I sottoarray ordinati vengono combinati con la procedura MERGE

fino a tornare di nuovo alla sequenza originaria

COSTO

Caso peggiore: O( ⋅ lg )

Caso medio: Θ( ⋅ lg )

Caso migliore: () = Ω( ⋅ lg )

QUICKSORT

1) L’ultimo elemento dell’array è il pivot

2) Individuo itemFromLeft (il primo elemento da sinistra più grande del pivot)

3) Individuo itemFromRight (il primo elemento da destra più piccolo del pivot)

4) Scambio itemFromLeft e itemFromRight

5) Individuo un nuovo itemFromLeft e un nuovo itemFromRight

6) Proseguo così fino a quando l’itemFromLeft è più a destra dell’itemFromRight

7) A questo punto scambio il pivot con itemFromLeft e il pivot è ordinato

8) Considero a questo punto i due sottoarray in cui il pivot ordinato divide l’array

9) Per ogni sottoarray individuo come pivot l’ultimo elemento e applico la stessa procedura

…

10) Alla fine l’array sarà ordinato

Lati positivi:

Mediamente efficiente

Ordina sul posto

Non usare quicksort per array quasi ordinati. COSTO

Caso peggiore: 2 )

O(

Caso medio: Θ( ⋅ lg )

Caso peggiore (l’array è già ordinato): Ω( ⋅ lg )

RANDOMIZED QUICKSORT

1) Scelgo un pivot

2) Sposto il pivot alla fine dell’array

3) Individuo l’itemFromLeft che è l’elemento da sinistra più grande del

pivot e l’itemFromRight che è l’elemento da destra più piccolo del pivot

4) Scambio l’itemFromLeft con l’itemFromRight

5) Individuo un nuovo itemFromLeft e un nuovo itemFromRight

6) Scambio itemFromLeft con itemFromRight

7) Questo prosegue fino a quando l’indice dell’itemFromLeft è

maggiore dell’indice dell’itemFromRight

8) A questo punto scambia itemFromLeft con il pivot

9) Il pivot scelto inizialmente è ordinato

10) Considero ora la partizione destra rispetto al pivot

11) Scelgo all’interno della partizione un nuovo pivot

12) Sposto il pivot alla fine del sottoarray

13) Individuo itemFromLeft e itemFromRight

14) Scambio itemFromLeft con itemFromRight

15) Questo prosegue fino a quando l’indice dell’itemFromLeft è maggiore dell’indice dell’itemFromRight

16) A questo punto scambia itemFromLeft con il pivot

17) A questo punto anche il secondo pivot è ordinato

18) Considero le altre partizioni rispetto ai pivot facendo il medesimo procedimento

19) Fino a quando l’array non è interamente ordinato

COSTO

Caso peggiore 2 )

() = O(

Caso medio () = Θ( ⋅ lg )

Caso migliore: () = Ω( ⋅ lg ) HEAPSORT

Heap: struttura dati composta da un array che si può considerare come un albero binario in cui ogni nodo

corrisponde ad un elemento dell’array Proprietà dell’heap:

• indica il numero degli elementi

ℎ[]:

nell’array

&bul