# Informatica 5 Liceo Scientifico Scienze Applicate/Algoritmi Complessità computazionale

Informatica 5 Liceo Scientifico Scienze Applicate
Copertina Tutti i moduli · Sviluppo
    CopertinaInformatica 5 Liceo Scientifico Scienze Applicate/Copertina
* OctaveInformatica 5 Liceo Scientifico Scienze Applicate/Octave
* MatriciInformatica 5 Liceo Scientifico Scienze Applicate/Matrici
* Sistema di equazioni lineariInformatica 5 Liceo Scientifico Scienze Applicate/Sistema di equazioni lineari
* LatexInformatica 5 Liceo Scientifico Scienze Applicate/Latex
* Istruzioni Programmazione OctaveInformatica 5 Liceo Scientifico Scienze Applicate/Istruzioni Programmazione Octave
** EserciziInformatica 5 Liceo Scientifico Scienze Applicate/Istruzioni Programmazione Octave/Esercizi
* Gauss Risoluzione Sistemi LineariInformatica 5 Liceo Scientifico Scienze Applicate/Gauss Risoluzione Sistemi Lineari
* Jacobi Risoluzione Sistemi LineariInformatica 5 Liceo Scientifico Scienze Applicate/Jacobi Risoluzione Sistemi Lineari
* Calcolare Numericamente un IntegraleInformatica 5 Liceo Scientifico Scienze Applicate/Calcolare Numericamente un Integrale
** AreaInformatica 5 Liceo Scientifico Scienze Applicate/Area
* Risolvere Numericamente una equazione differenzialeInformatica 5 Liceo Scientifico Scienze Applicate/Risolvere Numericamente una equazione differenziale
** Decadimento RadioattivoInformatica 5 Liceo Scientifico Scienze Applicate/Decadimento Radioattivo
* Grafici in OctaveInformatica 5 Liceo Scientifico Scienze Applicate/Grafici in Octave
* Metodo di BisezioneInformatica 5 Liceo Scientifico Scienze Applicate/Metodo di Bisezione
* FrattaliInformatica 5 Liceo Scientifico Scienze Applicate/Frattali
* Problemi legati al Calcolo NumericoInformatica 5 Liceo Scientifico Scienze Applicate/Problemi legati al Calcolo Numerico
* Tecnica di MontecarloInformatica 5 Liceo Scientifico Scienze Applicate/Tecnica di Montecarlo
* AlgoritmiInformatica 5 Liceo Scientifico Scienze Applicate/Algoritmi
* Algoritmi Complessità computazionaleInformatica 5 Liceo Scientifico Scienze Applicate/Algoritmi Complessità computazionale
* Modelli e SimulazioneInformatica 5 Liceo Scientifico Scienze Applicate/Modelli e Simulazione
** Modelli e SistemiInformatica 5 Liceo Scientifico Scienze Applicate/Modelli e Sistemi
** Tipi di Modello
** Diagrammi a blocchiInformatica 5 Liceo Scientifico Scienze Applicate/Diagrammi a blocchi
** Sistemi a microprocessoreInformatica 5 Liceo Scientifico Scienze Applicate/Sistemi a microprocessore
** Blocchi di condizionamento e Teorema di ShannonInformatica 5 Liceo Scientifico Scienze Applicate/Blocchi di condizionamento e Teorema di Shannon
** Un po' di elettronicaInformatica 5 Liceo Scientifico Scienze Applicate/Un po' di elettronica
** Esempi applicativi μP-μCInformatica 5 Liceo Scientifico Scienze Applicate/Esempi applicativi μP-μC
** AutomiInformatica 5 Liceo Scientifico Scienze Applicate/Automi
** Distributore BibiteInformatica 5 Liceo Scientifico Scienze Applicate/Distributore Bibite
** Sistemi Lineari e RetroazionatiInformatica 5 Liceo Scientifico Scienze Applicate/Sistemi Lineari e Retroazionati
** Simulazione Sistema Retroazionato
** Esempio Lancio del PesoInformatica 5 Liceo Scientifico Scienze Applicate/Esempio Lancio del Peso
Modifica il sommario

## 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. Più in generale un algoritmo viene valutato non solo in termini di istruzioni necessarie ma anche per l'utilizzo della memoria.
La lettera O (si legge o grande) indica il grado di complessità, e dopo questo simbolo racchiuso fra parentesi si indica il numero o l'espressione che ci permette di calcolarne il grado.Se si scrive O(3) si intende che il numero di operazioni per eseguire l'algoritmo e' pari a 3, se si scrive O(n) ,con n si intende di solito il numero di elementi caricati in un vettore che devono essere analizzati, si intende che il numero di operazioni è proporzionale alla dimensione del vettore (cioe' al numero di elementi contenuti nel vettpre) se si scrive O(4n) e' come nel caso O(n) ma si e' individuata anche la costante di proporzionalità (4) rispetto al numero di elementi del vettore, se trovate O(n$^2$ )te vuol dire che il numero di operazioni segue una legge quadratica rispetto al numero di elementi contenuti nel vettore di dimensione n. Qualche volta il calcolo e' meno precisa se trovate O(1) se i dati sono contenuti in un vettore indica che le operazioni da eseguirsi sono indipendenti dal numero di elementi in un vettore O(log$_2$n) che le operazioni da eseguirsi seguono una legge logaritmica rispetto al numero di elementi del vettore O(n) operazioni sono proporzionali al numero di elementi contenuti nel vettore
Se gli elementi del vettore sono n un algoritmo molto veloce ha O(k) con k= costante, uno veloce ha un andamento logaritmico, uno normale ha complessita' lineare O(n) oppure O(kn), le cose vanno male se O(nlog$_2$n) e vanno molto male se le leggi diventano quadratiche o di grado superiore O(n$^2$) O(n$^3$) .
Naturalmente il confronto deve essere fatto su algoritmi diversi che risolvono la stessa classe di problemi. Nella pratica qualche volta è semplice individuare l'ordine di complessità altre volte no, in alcuni casi l'ordine di complessità dipende dai particolari valori contenuti nel vettore, in questo caso si fornisce l'ordine di complessità nel caso peggiore, in una situazione media e nella situazione migliore, in alcuni casi il calcolo diventa difficile e si utilizzano programmi software detti profiler che analizzano i nostri algoritmi in casi reali fornendo informazioni sull'uso della CPU della memoria RAM e del numero di chiamate alle diverse funzioni.State attenti che istruzioni diverse fra loro di un programma richiedono tempi di esecuzione diversi, incrementare una variabile richiede magari un ciclo della cpu, moltiplicare 2 numeri in virgola mobile richiede 100 cicli della cpu. Riassumendo l'ordine di complessita' ci fornisce un parametro sintetico della velocita' di esecuzione dello stesso in funzione del numero di dati da elaborare, se non ci basta l'ordine della complessita' o questo non e' di facile calcolo perché dipende anche dai valori assunti dai dati allora bisogna usare un profiler applicato a specifici casi.
E' possibile trovare il grado di complessità anche su algoritmi quali il bubble sort, la ricerca dicotomica, la somma...etc
La tabella imdica il numero di operazioni da eseguirsi in funzione della dimensione n del vettore e dell'ordine di complessita+
| n | O_(1) | O(log$_2$ n) | O(n) | O(nlog$_2$ n) | O(n$^2$) |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 5 | 1 | 2 | 5 | 10 | 25 |
| 10 | 1 | 3 | 10 | 30 | 100 |
| 100 | 1 | 7 | 100 | 730 | 10000 |
| 1000 | 1 | 10 | 1000 | 10000 | 1000000 |
Molte volte il grado di complessità è semplice da trovare, ecco alcuni esempi:
1° esempio
In un algoritmo dove sono presenti solo queste tre operazioni il grado di complessità sarà 3, cioe' O(3)
2° esempio
il ciclo for ripete per n volte l'istruzione, l'ordine di complessità sarà pari ad O(n) .
3° esempio
In questo caso l'ordine di complessità sarà 2n, in quanto ci sono due cicli for separati, non nidificati e quindi ciascuno ripete per n volte la propria istruzione O(2n).
4° esempio
Invece in questo caso i cicli for si presentano nidificati e quindi l'ordine di complessità risulterà essere O(3n$^2$).
5° esempio Per quanto riguarda il BubbleSort l'ordine di complessità è un po' più complicato e risulta essere $O({\frac {n^{2}}{2}})$.
Vediamo insieme di giustificarne il valore:
Si può notare come ci siano due for nidificati dove si procederà moltiplicando il numero di ripetizioni del primo ciclo con quelle del secondo.
Nel primo for le iterazioni sono n-1 che però se pensiamo a numeri molto grandi può essere approssimato ad n; il secondo for invece numero di iterazioni che varia ( se il vettore ha 10 elementi, il ciclo for interno ripete l'istruzione if prima per 9 volte, poi per 8, poi per 7, ..., infine per 1) ma che mediamente vale n/2 perché se pensiamo ad una serie di numeri come questa
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à $O({\frac {n^{2}}{2}})$.
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 $O({\frac {n}{2}})$. 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 $O(n)$. 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.