Ciao, volevo proporre un esercizio teorico sulla complessità asintotica degli ordinamenti: devo cercare di dimostrare qual è il limite inferiore alla complessità asintotica di caso peggiore per gli algoritmi di ordinamento basati su confronto.
Io studiando un pò, so che non si può trovare un algoritmo per confronto che nel caso peggiore si comporti meglio di "NlogN", ma non riesco a dimostrarlo.
Se qualcuno sa qualcosa in più lo ringrazio!
Ciao,
è corretto quello che dici, cioè effettivamente il limite asintotico inferiore per gli algoritmi di ordinamento basati su confronti è nlogn. Altri algoritmi di ordinamento non basati su confronti (come il Counting sort o il Radix sort) riescono a raggiungere anche complessità lineari ma questo soltanto a condizioni particolari che ne limitano abbastanza il campo di applicabilità (è proprio questo il loro svantaggio, se non ce l'avessero sarebbero preferibili a quelli a complessità nlogn).
In ogni caso la dimostrazione del teorema sulla complessità asintotica inferiore degli algoritmi di ordinamento basati su confronto non è proprio semplice. Ti posso consigliare questo pdf:
http://cvprlab.uniparthenope.it/staf...2009/ASD-8.pdf
nelle cui prime 28 pagine viene dimostrato il teorema (si tratta di appunti di lezione del corso di "Algoritmi e Strutture Dati" della Parthenope di Napoli, principalmente sono riassunti del libro "Introduzione agli algoritmi e strutture dati" che è eccellente per lo studio della materia http://www.catalogo.mcgraw-hill.it/c...p?item_id=1920 ).
Spero ti possa essere d'aiuto...
ehi, ti ringrazio moltissimo, è quelle diapositive sono state do grande aiuto, avevo trovato qualcosa su wikipedia ma non mi piaceva come era stato spiegato, invece sulle tue diapositive viene spiegato molto bene aiutando a capire anche con qualche esempio che secondo me sono fondamentali per capire queste cose!
grazie ancora
ciao
Permessi di invio
Rispondi quotando