complessità computazionale

Mer av detta

mindomo

av chiara malafronte

L'ATTIVISMO

av caterina Santarpia

New Map

av Carla De Ponti

METODOLOGIA IVANOVA (CC)

av Chiara Alongi

complessità computazionale

Ramo principale

algoritmo risolutore

è un algoritmo che da una soluzione corretta per ogni istanza

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

istanze

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

funzione T(n)

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

complessità asintotica

notazione o grande

classi di complessita

fattoriale

O(n!)

n^k

O(n^k) bubble sort

esponenziale

O(k^n) algoritimi euristici

logaritmica

O(logn)ricerca binaria

costante

scambio variabili  O(1)

lineare

O(n) ricerca sequenziale

pseudolineare

O(nlogn) quick sort

algebra degli O grandi

teorema della somma e del prodotto

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

istruzione dominante

istruzione eseguita a*n + b volte

caso peggiore

parametri

oggettivi

tempo

tempo necessario per l'esecuzione (complessità temporale)

passi base

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

creazioni v. booleane

i/o da tastiera

accesso ad array

somma algebrica

assegnazione

spazio

utilizzo della memoria centrale e di quella di massa

trasmissione

efficienza I/O rispetto ai dispositivi remoti

input- output

tempo necessario per acquisire e restituire i dati

tempo necessario pre scquisire e restituire dati

soggettivi

qualità di scrittura

accessibilità

semplicità computazionale

grafica