[C] Complessità computazionale

[Linusss]

Ragazzi devo dare un esame ma sta cosa non l'ho capita benissimo, sapete mica dove trovare roba al riguardo oppure se potete spiegarmela voi...
In particolare la notazione O e omega.

grazie

[oregon]

Si tratta della cosiddetta "complessita'" di tempo e di spazio.

Non so se in questo forum e' OT (forse un po'), ma, in ogni caso non mi sembra che la spiegazione si possa dare in un forum (ci vuole un buon libro ...) ...

[Andrea1979]

santissimi google e wikipedia fanno schifo?
http://it.wikipedia.org/[/url] e cerca
Teoria della complessità algoritmica

ma come funziona l'università? non avete libri/dispense/publicazioni di varia natura più o meno consigliate dai vostri docenti?

[Linusss]

Si ma nelle dispense è speigato da schifo...

[infinitejustice]

Si chiama complessità asintotica. In effetti anche da noi, all'uni, l'hanno spiegata male. Ma è matematica, nn tanto informatica.

Generalmente il libro consigliato è Introduction to Algorithms (ISBN: 0262531968). Dovresti trovarlo anche in pdf.

[murder eyes]

O grande lo puoi vedere come un limite superiore alla complessità dell'algoritmo in questione.
Omega invece è una limitazione inferiore.

Una definizione che avrai sicuramente trovato sarà del genere:
O(g(n))=f(n) tale che esistono c e m tali che 0<=f(n)<=c*g(n) per ogni n>=m

Omega(g(n))=f(n) tale che esistono c e m tali che 0<=c*g(n)<=f(n) per ogni n>=m

Nel caso di O grande significa che per qualsiasi n maggiore di una quantità prefissata il comportamento della tua funzione(di complessità) è limitata inferiormente da 0 (cioè è positiva) e superiormente da g(n) moltiplicata da una costante c.

Analogamente per Omega.

Avrai anche sentito della notazione Teta

f(n)=Teta(g(n)) se e sole se f(n)=O(g(n)) e f(n)=Omega(g(n))

Dovrei capire da te il significato.



Cmq un buon libro universitario te lo spiega ampiamente e decisamente bene. Cmq se un informatico è spaventato da delle formule matematiche(in questo caso anche semplici) non so quanto possa andare avanti

[Linusss]

Ciao grazie della risposta.
Posso dirti due cose:
1- Nelle dispense è spigato grosso modo come nel tuo post, ovvero senza tanti particolari, tipo come mi ricavo la funzione dell'algoritmo, a cosa mi serve ecc ecc.
2- Non sono un informatico ma studio ing informatica che è diverso.

ciao

[unomichisiada]

Originariamente inviato da Linusss
Ciao grazie della risposta.
Posso dirti due cose:
1- Nelle dispense è spigato grosso modo come nel tuo post, ovvero senza tanti particolari, tipo come mi ricavo la funzione dell'algoritmo, a cosa mi serve ecc ecc.
2- Non sono un informatico ma studio ing informatica che è diverso.

ciao

1) Se mi dai la tua mail via PVT posso inviarti la dispensa del mio corso di Algoritmi e Strutture dati relativa alla complessità. A mio avviso la spiegazione non è molto teorica ed è abbastanza accessibile, io almeno la avevo trovata così. Ti consiglio comunque di vedertela anche su un buon libro (io ad esempio l'ho studiata anche sul Cormen Leiserson oltre che dal libro specifico sul C associato al corso).
2)Sempre via PVT per non uscire OT, gradirei che tu mi speigassi a grandi linee la differenza tra un corso di informatica ed uno di ingegneria informatica.

[byaur]

Originariamente inviato da unomichisiada
2)Sempre via PVT per non uscire OT, gradirei che tu mi speigassi a grandi linee la differenza tra un corso di informatica ed uno di ingegneria informatica.

sono curioso anche io!!!!


VVoVe: VVoVe:

[Linusss]

Visto che siete ben in due a non conoscere l'abissale differenza fra le due figure, vi linko le pagine relative alle due facolta di bologna, ing.informatico e informatico
Se leggendo solo gli obiettivi formativi non riuscite a comprendere la differenza allora guardatevi l'elenco completo degli insegnamenti delle rispettive facoltà,e vedrete come sono diversi gli esami di uno dagli esami dell'altro.

VVoVe: VVoVe: VVoVe:

ciao