Complessità degli algoritmi
La complessità in tempo asintotica si distingue dalla complessità in tempo perché …
Associa alla complessità asintotica corrispondente
 | T1(n)=20n, T2(n)=3n2, T3(n)=300, T4(n)=3n2+2000n, T5(n)=25log2n+300, T6(n)=25log2n+n2 |
| O(log2n), O(n), O(1), O(n2), O(n3) |
L’algoritmo di ricerca sequenziale con sentinella ha, rispetto a quello normale,
| almeno un vantaggio: |
| e almeno uno svantaggio: |
Individua (e commenta…) la complessità asintotica del miglior algoritmo risolutivo per ciascuno dei seguenti problemi
| Fusione di 4 vettori ordinati |
| Ricerca su un vettore ordinato |
| Ricerca su un vettore non ordinato |
| Calcolo della media su una matrice quadrata |
| Input da tastiera di un carattere |
Nel calcolo della complessità di un algoritmo si considera come più significativo il caso medio perché …