11-02 Complessità degli algoritmi
Descrivi i passi d’esecuzione (a parole e graficamente) dell’algoritmo MergeSort applicato a un vettore contenente il giorno e il mese del tuo compleanno:,g|g|m|m|.
Dovendo scegliere l’algoritmo di ordinamento da utilizzare, per la risoluzione di un problema, spiega brevemente le caratteristiche di quelli a te noti.
Per ognuna delle funzioni di complessità seguenti indica la complessità asintotica corrispondente e la sua posizione in un’ipotetica classifica:
 | T1= 20nlog2n+10n2 |
| T2= 20log2n+10n |
| T3= 2n+10n2 |
| T4= 200+10000n. |
Per ognuno dei problemi seguenti indica la complessità asintotica, specificando brevemente a quale algoritmo ti riferisci
- Ordinare un vettore
- Eliminare un elemento in un vettore
- Scambiare il contenuto di due variabili.
10-03 Complessità degli algoritmi
Stabilisci una classifica (dal 1° al 6°) □ O(1) □ O(n) □ O(logn) □ O(n2) □ O(nlogn) □ O(2n).
Per ognuna delle funzioni di complessità seguenti indica la complessità asintotica
| T1 = 20nlog2n+100n2 |
| T2 = 20log2n+100n |
| T3 = 20n+100n2 |
| T4 = 20+100n |
| T5 = 20n+100log2n |
| T6 = 20n3+100n |
| T7 = 20+100log10n |
| T8 = 20n+30n4+100. |
La complessità degli algoritmi si occupa □ dell’interfaccia utente □ del tempo d’esecuzione □ dello spazio di memoria occupato □ della comprensibilità.
La sentinella, dell’algoritmo di ricerca corrispondente, viene inserita nel vettore alla posizione □ 0 □ 1 □ n Div 2 □ n □ n+1.
La complessità dell’algoritmo di ricerca sequenziale è □ O(1) □ O(n) □ O(logn) □ O(n2) □ O(nlogn) □ O(2n),
| un ordinamento ingenuo … |
| ricerca binaria … |
| bubbole sort … |
| un ordinamento evoluto … |
| merge sort … |
| un problema intrinsecamente esponenziale … |
| selection sort … |
| merge … |
Il numero di scambi del selection sort è □ 0 □ 1 □ n-1 □ n □ n+1 □ n2,
| ricerca sequenziale … |
| merge sort … |
Per l’algoritmo di ricerca sequenziale il caso in cui l’elemento non appartiene al vettore è □ ottimo □ pessimo □ medio □ indifferente.
Per l’algoritmo Merge Sort il caso in cui il vettore è già ordinato è □ ottimo □ pessimo □ medio □ indifferente.
Un algoritmo è costituito da due blocchi che hanno come misura del tempo d'esecuzione T1(n) = 20n e T2(n) = 30logn.Calcola la complessità in tempo dell’algoritmo nel caso in cui i due blocchi siano consecutivi, T(n) = ….… oppure annidati, T(n) = ….…
22-03 Complessità degli algoritmi
Per ognuna delle funzioni di complessità seguenti indica la complessità asintotica
| T1 = 20n+10n2 |
| T2 = 20log2n+10 |
| T3 = 10n2 2n |
| T4 = 20n*10n2 |
| T5 = 20n+10nlog2n |
| T6 = 20n3+10n |
Inserisci le cifre della tua data di nascita g|g|m|m|a|a|a|a e poi (a parole e graficamente)
| applica una passata del Bubble Sort ... |
| applica una passata del Selection Sort ... |
| descrivi il comportamento della Ricerca Con Sentinella (k=7) ... |
Problemi intrinsecamente esponenziali:
| dai un esempio ... |
| cosa si può dire sui tempi di esecuzione? ... |
Problemi non polinomiali:
| dai un esempio ... |
| cosa si può dire sui tempi di esecuzione? ... |
Quali criteri adotteresti dovendo scegliere un algoritmo di ricerca?