Informatica 5 Liceo Scientifico Scienze Applicate/Algoritmi Complessità computazionale: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
Nessun oggetto della modifica |
||
Riga 1:
{{Informatica 5 Liceo Scientifico Scienze Applicate}}
==Complessità computazionale==
In informatica per risolvere i problemi si utilizzano degli algoritmi, dei pezzi di codice che risolvono in modo efficiente una particolare classe di problemi, si parla ad esempio dell'algoritmo dell'ordinamento oppure dell'algoritmo della ricerca dicotomica etc. Quando si va a valutare l'efficienza di un algoritmo la si sintetizza mediante un indice detto ordine della complessità computazionale dell'algoritmo che identifica il numero di operazioni necessarie per risolvere un problema generico con quel particolare algoritmo.
Line 11 ⟶ 12:
[[File:Complessitacomputazionale.png|
Naturalmente il confronto deve essere fatto su algoritmi diversi che risolvono la stessa classe di problemi.
Line 86 ⟶ 87:
Invece in questo caso i cicli for si presentano nidificati e quindi l'ordine di complessità risulterà essere O(3n<sup>2</sup>).
5° esempio
Per quanto riguarda il
Vediamo insieme di giustificarne il valore:<br />
▲Per quanto riguarda il Bubble sort l'ordine di complessità è un po' più complicato e risulta essere <math>O(\frac{n^{2}} {2})</math>.
Line 113 ⟶ 114:
la media vale 5 e la potete calcolare velocemente osservando che la media del primo elemento con l'ultimo vale 5 , del secondo con il penultimo vale 5 , del terzo con il terzultimo vale 5 e cosi facendo risulterà sempre la stessa, cioè 5.
Quindi per concludere se moltiplichiamo le n iterazioni del primo for con le n/2 medie del secondo for il grado totale dell'algoritmo sarà <math>O(\frac{n^{2}} {2})</math>.<br />
6° esempio
Pensando alla ricerca esaustiva , dove si ricerca un elemento in un vettore non ordinato, bisogna scorrere tutto il vettore una cella alla volta finchè non troviamo l'elemento da ricercare.
Se quello che cerchiamo è presente nel vettore possiamo essere fortunati e trovarlo nella prima posizione del vettore o possiamo essere sfortunati e trovarlo nella'ultima posizione, mediamente (in senso probabilistico) lo troveremo dopo aver analizzato il 50% del vettore, l'ordine di complessità vale allora <math>O(\frac{n} {2})</math>.<br />
Se invece non è presente dovremo passare in rassegna tutti gli elementi del vettore per essere sicuri che non è presente, in questo caso l'ordine di complessità vale allora <math>O(n)</math>.<br /> Quindi la complessità computazionale spesso è legata ai dati contenuti nel vettore e a certe condizione assunte, l'ordine di complessità può avere un valore max che esprime la situazione peggiore e un valore medio.
{{Avanzamento|100%|15 giugno 2015}}
[[Categoria:Informatica 5 Liceo Scientifico Scienze Applicate|Algoritmi Complessità computazionale]]
| |||