Complessità computazionale

Slide tratte dal corso di Programmazione tenutosi nella facoltà di Ingegneria Informatica e Biomedica presso l'Università degli Studi "Magna Graecia" di Catanzaro. Nello specifico viene presentato il concetto di Complessità Computazionale nei suoi aspetti temporale, spaziale, di Input/Output e di trasmissione. Seguono alcuni esempi di calcolo computazionale su linee di codice in Java.

Fonda men ti d i In fo rm atic a - C om ple ss it à co m pu ta ziona le1
C O M PLE SSITÀ C OM PUTAZ IO NALE
CO SA SI I NTE ND E PE R COM PLESS IT À ?
La Com ple ss it à Tem po ra le , S pa zia le , d i Inpu t/Outpu t e
di T ra sm iss ione
C O M PLESS IT À TE M PO RA LE
In in fluen za de lla ve lo cit à de lla m acc hina pe r molt e
im po rtan ti cla ss i di a lgo rit m i
IL MODELL O DI C O STO
qD efin iz ione d i d im en sione de ll'i npu t
qDefin iz ione d i i str u zione d i co sto un it a rio (pa sso
ba se )
qE se m pi d i ca lc o lo de lla co m ple ss it à in nu mero d i
pa ssi ba se
qC om ple ss it à ne l c a so mig lio re , ne l ca so m ed io e ne l
ca so pegg io re
qC om ple ss it à d i p rog ra mm i s tr u tt ura ti
qC om ple ss it à a sin to tic a
Fonda men ti d i In fo rm atic a - C om ple ss it à co m pu ta ziona le2
C O M PLESS IT À TE M PO RALE
Q uan to te m po ric h iede l'e se cu zione d i un a lgo rit m o?
CO M PLESS IT À SPA ZIA LE
Q uan ta o ccupa zione d i m em oria ric h iede l'e se cu zione d i
un algo rit m o?
CO M PLESS IT À DI I/O (IN PU T_O UTP U T)
Q uan to te m po ric h iede la a cqu is iz ione (o il
tr a sfe rim en to ) di i nfo rm azion i da pe rif e ric he? (Mem oria
s e conda ria , ta stie ra , sta m pan te,... )
...

Continua a leggere

Tipologia di contenuto: 
Slide
Facoltà: 
Ingegneria
Materia: 
Corso: 
Informatica

Aggiungi un commento

Accedi o registrati per inserire commenti.