Merge sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
Nessun oggetto della modifica |
||
Riga 5:
Dato un programma(A,n) su n dati, tale programma giungerà alla riga di codice di un comando if tipo: if(guardia){com1} else {com2} (esempio in java)
una specie di bivio dove uscirà se la guardia non soddisfa, eseguirà altrimenti.
Nel secondo caso il {com2} indicherà di risolvere il problema soddividendolo in sottoproblemi più semplici, intuitivamente da
Programma(A,1....n) a ( Programma(A,1....n/2) Programma(A,n/2+1....n) ) Programma(A,n/2+1....n)▼
e per ogni sottoproblema si troveà una soluzione.
Trovate quindi tutte le soluzioni si fonderanno assieme (merge)dando luogo alla soluzione finale.
Il Mergesort costa in tempo
dato dalla relazione: T(n)=aT(n/b)+f(n)
dato dal "teorema principale" T(n)=Θ(g(n))
T(n)=Θ(n log n)
Si ricorda che la notazione di ordine Teta si impiega per indicare il tempo di un algoritmo, non in secondi perchè questi varia in base al calcolatore più precisamente dalle diverse compilazioni (Linux,Windows,ecc).
Si può studiare (descrivere)il limite inferiore con la notazione di ordine omega del Mergesort
che per il sorting vale Ω(n log n).
Il '''merge sort''' è un [[algoritmo]] [[algoritmo di ordinamento|di ordinamento]] molto intuitivo e abbastanza rapido, che utilizza un processo di risoluzione ricorsivo.
| |||