[Algoritmi e strutture dati] Notazioni asintotiche ( O,OMEGA E THETA) x complessità

[marco vee]

Ciao a tutti!
ragazzi per favore mi potete aiutare a capire i concetti e la funzionalità delle notazioni asintotiche ( O, Ω e Θ ) per il calcolo della complessità di un algoritmo?

[YuYevon]

Non sono concetti semplici da poter trattare per intero su un forum. Diverso è se hai dubbi specifici. Si tratta di notazioni matematiche che servono ad indicare (rispettivamente) il limite superiore, inferiore e stretto della complessità temporale asintotica di un algoritmo. Detto in maniera davvero molto superficiale, dire ad esempio che un algoritmo abbia complessità T(n) = O(n^2) significa dire che il suo tempo di esecuzione, al variare di n (che indica la taglia dell'input), non crescerà mai "più velocelemente" del quadrato di n; Ω(n^2), specularmente, significa che il tempo di esecuzione non crescerà mai "più lentamente" del quadrato di n, mentre la notazione Θ indica un limite stretto, e si ha quando una complessità temporale risulta essere sia O che Ω di una tale funzione, quindi ad esempio se l'algoritmo X ha sia complessità O(n^2) che Ω(n^2), si può dire in definitiva che esso sia anche Θ(n^2).

[marco vee]

Quindi ogni specifico algoritmo ha una determinata complessità???
Cioè [U]ad es[U/]
- tutti gli algoritmi di ordinamento hanno complessità O (n) ??
- tutti gli algoritmi di inserimento hanno complessità Ω (log n) ??

e poi come scegliere tra Ω, O oppure Θ?in base a quali criteri?? :master:

[YuYevon]

Originariamente inviato da marco vee
Quindi ogni specifico algoritmo ha una determinata complessità???

Per essere precisi, per ogni algoritmo si parla di complessità di tempo e di spazio che non hanno nulla a che vedere con O, omega e teta, i quali introducono il concetto di complessità *asintotica*, cioè al crescere di n. In ogni caso sì, tutti gli algoritmi hanno una certa complessità.

Originariamente inviato da marco vee
- tutti gli algoritmi di ordinamento hanno complessità O (n) ??

Questo non è vero, anzi: gli algoritmi di ordinamento a complessità O(n) sono solo quelli non basati su confronti, come il Bucket Sort o il Radix Sort, e sono abbastanza rari rispetto ai più noti algoritmi basati su confronti per i quali (si dimostra pure) non sarebbe possibile avere una complessità asintotica migliore di O(nlogn), e a questa categoria appartengono i famosissimi Quick Sort, Merge Sort e Heap Sort. Ci sono poi quelli che oltre ad essere basati su confronti non sfruttano nemmeno la tecnica del divide et impera (come quelli appena citati) e per questo motivo sono a complessità asintotica O(n^2), come Insertion Sort, Selection Sort o Bubble (Exchange) Sort, perché di fatto non sono altro che due cicli iterativi innestati.

Originariamente inviato da marco vee
- tutti gli algoritmi di inserimento hanno complessità Ω (log n) ??

Non esiste un generico "algoritmo di inserimento". Gli algoritmi di inserimento variano a seconda della struttura dati in cui si effettua l'inserimento, e ovviamente varia anche la complessità asintotica relativa.

Originariamente inviato da marco vee
e poi come scegliere tra Ω, O oppure Θ?in base a quali criteri?? :master:

Non è che devi "scegliere". Per ogni algoritmo con relativa complessità, è possibile definire un limite superiore e inferiore e, nel caso questi coincidano, un limite stretto. Comunque in generale la notazione più ricorrente è senz'altro O, anche perché per valutare le prestazioni di un algoritmo spesso si è interessati ad analizzarne i casi peggiori e non quelli migliori.

[marco vee]

Non è che devi "scegliere". Per ogni algoritmo con relativa complessità, è possibile definire un limite superiore e inferiore e, nel caso questi coincidano, un limite stretto. Comunque in generale la notazione più ricorrente è senz'altro O, anche perché per valutare le prestazioni di un algoritmo spesso si è interessati ad analizzarne i casi peggiori e non quelli migliori.

quindi la notazione O è riferita ai casi peggiori e omega ai casi migliori?

[YuYevon]

Originariamente inviato da marco vee
quindi la notazione O è riferita ai casi peggiori e omega ai casi migliori?

In *pratica*, sì. Dire che la complessità di un algoritmo sia O(f(n)), dove f(n) è una generica funzione in n (come proprio n o n^2 o nlogn) significa che essa non crescerà mai "più rapidamente" di f(n), quindi appunto che l'algoritmo ha un tempo di esecuzione che è al massimo proporzionale a f(n) (quindi nel caso peggiore). Similmente, se la complessità è Ω(f(n)) si sta dicendo che questa non crescerà mai "più lentamente" di f(n), quindi che anche nel migliore dei casi il tempo di esecuzione dell'algoritmo non potrebbe essere più "lento" di f(n), dove chiaramente, visto che stiamo parlando di funzioni, i concetti di rapidità e lentezza indicano come crescono le funzioni stesse al variare di n.

Comunque non accontentarti di queste spiegazioni superficiali, studia da un libro.

[marco vee]

si infatti era quella l'idea...perchè è molto importante per un esame che devo sostenere...
cmq, visto che sei abbastanza competente, sapresti spiegarmi, almeno per capire, le tecniche Hash e i loro funzionamenti, tipo a conctaenamento, hashing doppio, quadratico...???

[YuYevon]

Stai andando su tutto un altro capitolo, anche questo non banale, vasto e impossibile da trattare su un forum. Da dove dovrei cominciare? Tra l'altro è OT rispetto all'argomento del thread, ma prima di iniziare un'altra discussione ti consiglio caldamente di tentare di studiare questi argomenti da solo per poi porre magari domande su aspetti particolari.

Le tavole hash sono strutture dati impiegate per implementare dizionari, cioè strutture che consentono solo le operazioni di inserimento, cancellazione e ricerca. Le operazioni di inserimento e cancellazione introducono una caterva di problemi: come trovare una funzione hash decente che possa evitare le collisioni quanto più possibile, cercando cioè di distribuire gli elementi in maniera quanto più uniforme possibile tra le varie entry? E, in caso di collisioni, come gestirle? 'nzomma, vedi sopra :°D

[alka]

Siamo già andati oltremodo off topic: questo è un'area dedicata alla programmazione, e si propone di risolvere problemi strettamente legati a questo argomento, oltreché all'uso di linguaggi, compilatori e ambienti di sviluppo.

Le domande che sono state riportate trovano risposta leggendo libri, documentazione e manuali, o facendo ricerche su Google: è inutile farsi riportare e spiegare qui tutto ciò che può essere benissimo trovato e approfondito altrove, senza addentrarsi nella trattazione di un problema ben specifico.