complessità computazionale

algoritmo risolutore

r

è un algoritmo che da una soluzione corretta per ogni istanza

parametri

soggettivi

grafica

semplicità computazionale

accessibilità

qualità di scrittura

oggettivi

input- output

r

tempo necessario per acquisire e restituire i dati

tempo necessario pre scquisire e restituire dati

trasmissione

efficienza I/O rispetto ai dispositivi remoti

spazio

r

utilizzo della memoria centrale e di quella di massa

utilizzo della memoria centrale e di quella di massa

tempo

r

tempo necessario per l'esecuzione (complessità temporale)

passi base

r

istruzione elementare che ha un costo unitario (non dipende ne dal valore ne dal tipo di variabile)

assegnazione

somma algebrica

accesso ad array

i/o da tastiera

creazioni v. booleane

tempo necessario per l'esecuzione (complessità temporale)

istanze

r

https://it.wikipedia.org/wiki/Oggetto_(informatica

a

caso peggiore

funzione T(n)

r

https://it.wikipedia.org/wiki/Complessit%C3%A0_temporale

complessità asintotica

notazione o grande

istruzione dominante

istruzione eseguita a*n + b volte

algebra degli O grandi

teorema della somma e del prodotto

r

teorema della somma = in un blocca di istruzioni formato da blocchi la complessitò sarà uguale a quella del blocco più complesso teorema del prodotto = in un blocco formato da blocchi annidati la complessità è data dal prodotto delle complessità di ogni blocco

classi di complessita

pseudolineare

O(nlogn) quick sort

lineare

O(n) ricerca sequenziale

costante

scambio variabili  O(1)

logaritmica

O(logn)ricerca binaria

esponenziale

O(k^n) algoritimi euristici

n^k

O(n^k) bubble sort

fattoriale

O(n!)

è un algoritmo che da una  soluzione corretta ad ogni istanza del problema

Ramo principale