Complessità degli algoritmi (R)

La complessità in tempo asintotica si distingue dalla complessità in tempo perché si occupa del comportamento dell'algoritmo per n "molto" grande / trascura costanti e combinazioni lineari scegliendo una sola funzione rappresentativa / descrive chiaramente l'ordine di grandezza del tempo d'esecuzione

Associa alla complessità asintotica corrispondente

1. T(n) = 20n --> O(n)

2. T(n) = 3n^{2 -->} O(n²)

3. T(n) = 300 --> O(1)

4. T(n) = 3n² + 2000n --> O(n²)

5. T(n) = 25log₂n + 300 --> O(log₂n)

6. T(n) = 25log₂n + n² --> O(n²)

L’algoritmo di ricerca sequenziale con sentinella ha, rispetto a quello normale,

1. almeno un vantaggio: è più veloce perché nel while()do ci sono due operazioni elementari in meno
2. e almeno uno svantaggio: è meno comprensibile / necessità di una locazione in più

Individua (e commenta…) la complessità asintotica del miglior algoritmo risolutivo per ciascuno dei seguenti problemi

1. Fusione di 4 vettori ordinati --> O(n): come per la fusione di due vettori
2. Ricerca su un vettore ordinato --> O(log₂n): uso la ricerca binaria
3. Ricerca su un vettore non ordinato --> O(n): uso la ricerca sequenziale
4. Calcolo della media su una matrice quadrata --> O(n²): se n è la dimensione della matrice sono necessari n² passi per sommare n² elementi
5. Input da tastiera di un carattere --> O(1): si può considerare un'operazione "elementare"