[Algoritmi] Ordinamento di un vettore
Scusate la banalità di questa domanda, è giusto per capire se ho capito bene 
Un ordinamento (assolutamente inefficiente) che in pratica:
Dimensiona un altro vettore vuoto della stessa lunghezza di quello da ordinare
Per ogni componente fa un controllo con ogni altra componente e conta quante di esse sono maggiori (o minori)
Assegna quella componente alla posizione corrispondente al valore di maggiori/minori contato.
Un algoritmo del genere è del tipo \(\displaystyle O(n^2) \) ? Perchè per ogni componente del vettore, ci sono N-1 controlli e c'è l'istruzione che copia nell'altro vettore alla posizione corrispondente, quindi N-1+1=N, poi visto che va fatta questa cosa per ogni elemento, ottengo \(\displaystyle N^2 \), corretto?
Un ordinamento (assolutamente inefficiente) che in pratica:
Dimensiona un altro vettore vuoto della stessa lunghezza di quello da ordinare
Per ogni componente fa un controllo con ogni altra componente e conta quante di esse sono maggiori (o minori)
Assegna quella componente alla posizione corrispondente al valore di maggiori/minori contato.
Un algoritmo del genere è del tipo \(\displaystyle O(n^2) \) ? Perchè per ogni componente del vettore, ci sono N-1 controlli e c'è l'istruzione che copia nell'altro vettore alla posizione corrispondente, quindi N-1+1=N, poi visto che va fatta questa cosa per ogni elemento, ottengo \(\displaystyle N^2 \), corretto?
Risposte
Direi che la complessità è quella.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo