Lezione08 MergeSort Esercizi

MergeSort
Esercizi
22 marzo 2023
Divide et Impera
– Dividi il problema in sottoproblemi
– Risolvi ogni sottoproblema ricorsivamente
– Combina le soluzioni ai sottoproblemi per

ottenere la soluzione al problema
Mergesort
Mergesort.
• Divide array into two halves.
• Recursively sort each half.
• Merge two halves to make sorted whole. Jon von Neumann (1945)
A L G O R I T H M S
A L G O R I T H M S
Recursively sort:
as a black box
A G L O R H I M S T
A G H I L M O R S T
Mergesort
Qui supponiamo che MERGE(A, p, q, r) fonda le sequenze A[p,…, q] e

A[q+1, …, r] in loco. Quindi la divisione dell’array in due metà si fa
semplicemente calcolando q nella linea 2 (con costo costante).
Altrimenti, la divisione avrebbe comportato l’allocazione di due sotto-
array e la copia degli elementi (con costo lineare).
Anche MERGE-SORT sarà in loco, non avrà quindi bisogno di memoria
ausiliaria.
Correttezza di Mergesort
Perché funziona?
Nel caso base (n=1), un array di 1 elemento è già ordinato e l’algoritmo
correttamente non esegue nessuna operazione su di esso.
Nel caso generale di una chiamata principale su n elementi, l’algoritmo

ordina correttamente la porzione di array perché:
• Possiamo supporre per induzione che le due chiamate di MERGE-
SORT su n/2 elementi restituiscano gli array ordinati
• MERGE chiamato su due array ordinati, fonde correttamente i due
array ordinati in un solo array ordinato
Tempo di esecuzione di Mergesort
Sia T(n) il tempo di esecuzione di Mergesort su un array di taglia n.
T(n) = ?
Come si calcola il tempo di esecuzione di un algoritmo ricorsivo?

Tempo di esecuzione di Mergesort
Sia T(n) il tempo di esecuzione di MERGE-SORT su un array di taglia n.

T(n) = ?
C’è 1 confronto nella linea 1: (1). Poi nel caso generale:
un assegnamento (1) e l’esecuzione del MERGE: (n);
per un totale di al più: (1) + (1) + (n) e poi
2 esecuzioni di MERGE-SORT su due array di circa n/2 elementi, cioè?
Non 2 Θ(n/2) !
T(n) = (1) + (1) + (n) + 2 T(n/2)
A Recurrence Relation for Mergesort
Def. T(n) = number of comparisons to mergesort an input of size n.
Mergesort recurrence.
n=2
T(n) =
Solution. T(n) = Θ(n log n).

2
Assorted proofs.
We will describe several ways to prove this recurrence.
First, we will solve a simplified recurrence:
T(n) = 2 T(n/2) + (n) con T(2)= (1) per n=2k
9
Relazioni di ricorrenza per alcuni algoritmi
Divide-et-Impera
Se un algoritmo Divide-et-Impera
• Divide il problema di taglia n in a sotto-problemi di taglia

n/b
• Ricorsione sui sottoproblemi
• Combinazione delle soluzioni
allora
T(n)= tempo di esecuzione su input di taglia n
T(n)= D(n) + a T(n/b) + C(n)

Esercizi dalla piattaforma
(svolti)
Notazioni asintotiche 1
La relazione 3n(n-1) ≤ c n2 è vera per ogni n  n0 con
A. c= 4 e n0 =0 B. c= 2 e n0 =0 C. c= 1/3 e n0 =1
D. Nessuna delle risposte precedenti

A B C D
Numero di
risposte 26 4 4 16
Date due funzioni f(n) e g(n) si ha che f(n) = O(g(n)) se
A. f(n) ≤ g(n) per n che tende ad infinito
B. Per ogni c > 0, f(n) ≤ c g(n) per ogni n  n0
C. Esistono c > 0, n0  0 tali che f(n) ≤ c g(n) per ogni n  n0 D. Nessuna

delle risposte precedenti
A B C D
Numero di
0 0 50 4
risposte
Qual è la corretta successione delle funzioni seguenti affinché compaiano da sinistra
a destra in ordine crescente di crescita asintotica: n2, n (log n)2, 𝒏𝟑 ?
A. 𝒏𝟑 , n2, n (log n)2 C. n (log n)2, n2 , 𝒏𝟑
B. n (log n)2, 𝒏𝟑 , n2 D. Nessuna delle risposte precedenti.
A B C D
Numero di
2 37 0 16
risposte
Tempo di esecuzione 1
Il tempo di esecuzione del seguente frammento di pseudocodice è
for i=1 to n/2

if i > 0 then A. O(log n)
x=2x B. Ɵ(n log n)
return x C. Ɵ (n^2)
A B C D
Numero di
3 1 1 48
risposte
for i=1 to n/2

for j=1 to logn A. O(log n)
x=i*j B. o(n log n)
A B C D
Numero di
1 9 0 41
risposte
Calcolare il tempo di esecuzione del seguente algoritmo
A. Ɵ (n2)
B. ω (n 2)
C. Ɵ (n)
A B C D
Numero di
4 1 0 0
risposte
Analisi for (linee 3-6)
i = 1, j = n, n-1, … , 2, quindi (n-1) volte
………
i = n-1, j = n, quindi 1 volta
i = n, quindi 0 volte
Primo modo:
Cominciamo dall’analisi del while (5-6):
Ripete due istruzioni di tempo costante (6) un numero di volte
variabile, ma ≤ n-1, quindi prende tempo O(n).
Il for itera n volte blocco 4-6
Blocco 4-6 prende tempo O(1)+O(n) = O(n).
Quindi il for prende tempo O(n n) = O(n2).
Analisi for (linee 3-6)
………
i = n-1, j = n, quindi 1 volta
i = n, quindi 0 volte
Secondo modo:
Quante volte in tutto è ripetuta ciascuna istruzione di tempo
costante, all’interno del for?
Numero ripetizioni (6) = (n-1) + (n-2) + … + 2 + 1 =
= 1 + 2 + … + (n-1) =
=(n-1) n/2 = (n2 – n)/2 = (n2).
Analogamente il test j > i è eseguito n + (n-1) + … + 2 + 1 = (n2) volte.
L’assegnamento (4) è eseguito n volte.
In totale, il tempo di esecuzione del for è (n2).
for i=1 to logn

for j=1 to logn A. O(log n)
x=i*j B. O(n log n), ma non Ɵ (n log n)
A B C D
Numero di
4 21 1 23
risposte
Merge
Quanti confronti effettua l’algoritmo MERGE per
la fusione dei due array ordinati
[1,5,6,7] e [2,3,4]?
A. 4 B. 6 C. 12
D. Nessuna delle precedenti
A B C D
Numero di
22 0 0 0
risposte
Funzioni da ordinare (KT3)
Es. n. 3 pag. 67 del libro [KT].
Indicare la corretta successione delle funzioni seguenti
affinché compaiano da sinistra a destra in ordine crescente
di crescita asintotica, motivando adeguatamente la
successione proposta:

Lezione08 MergeSort Esercizi

Caricato da

Copyright:

Formati disponibili

Lezione08 MergeSort Esercizi

Caricato da

Informazioni sul documento

Titolo originale

Copyright

Formati disponibili

Condividi questo documento

Condividi o incorpora il documento

Opzioni di condivisione

Hai trovato utile questo documento?

Questo contenuto è inappropriato?

Copyright:

Formati disponibili

Lezione08 MergeSort Esercizi

Caricato da

Copyright:

Formati disponibili

MergeSort

– Risolvi ogni sottoproblema ricorsivamente

– Combina le soluzioni ai sottoproblemi per

Qui supponiamo che MERGE(A, p, q, r) fonda le sequenze A[p,…, q] e

Nel caso generale di una chiamata principale su n elementi, l’algoritmo

Sia T(n) il tempo di esecuzione di Mergesort su un array di taglia n.

Come si calcola il tempo di esecuzione di un algoritmo ricorsivo?

Sia T(n) il tempo di esecuzione di MERGE-SORT su un array di taglia n.

Solution. T(n) = Θ(n log n).

• Divide il problema di taglia n in a sotto-problemi di taglia

T(n)= D(n) + a T(n/b) + C(n)

D. Nessuna delle risposte precedenti

A. f(n) ≤ g(n) per n che tende ad infinito

B. Per ogni c > 0, f(n) ≤ c g(n) per ogni n  n0

C. Esistono c > 0, n0  0 tali che f(n) ≤ c g(n) per ogni n  n0 D. Nessuna

A. 𝒏𝟑 , n2, n (log n)2 C. n (log n)2, n2 , 𝒏𝟑

B. n (log n)2, 𝒏𝟑 , n2 D. Nessuna delle risposte precedenti.

for i=1 to n/2

for i=1 to n/2

for i=1 to logn

Potrebbero piacerti anche