Re: Complessità Computazionale
On Sun, Jan 4, 2009 at 10:06 PM, 1984viking <1984viking@gmail.com> wrote:
> Ciao a tutti della lista.....
> Per necessità di studio, sono alla disperata ricerca d'informazioni riguardo
> la complessità computazionale, soprattutto riguardo la notazione O(.), Theta
> e Omega...
http://www.soe.ucsc.edu/classes/cmps102/Spring04/TantaloAsymp.pdf
l'O(.) grande è una notazione asintotica
in soldoni significa che all'infinito cresce come (.)
Cioè prevale il termine (.)
esempio
e^x+x^5*logx
ad infinito prevale e^x quindi è O(e^x)
devi vedere qual'è il termine più grande ad infinito
poi theta ed omega vengono da soli
> Qualcuno potrebbe gentilmente fornirmi qualche spunto di dove posso trovare
> informazioni dettagliate, (che non sia wikipedia ;-))??Inoltre qualcuno
> potrebbe gentilmente farmi un esempio di come si calcola il caso
> peggiore,medio,migliore di un frammento di codice C?
Quello che dice il mio prof è che, nella maggior parte dei casi, il
metodo peggiore è il più semplice da calcolare (il migliore non lo
considera in quanto non capita mai :-) )
Mentre per il caso medio di solito è richiesta una buona conoscenza di
statistica.
Comunque per valutare il caso peggiore di un frammento di codice devi
prima individuare l'operazione fondamentale.
Nell'ordinamento, per esempio, dovrebbe essere lo swap, e calcolare
quante volte viene effettuata.
Il problema possono essere gli if,
for(...)
if (v[i]<v[i+1]) swap(v[i]<v[i+1]);
in questo caso basta che li consideri sempre presi.
> Vi ringrazio in anticipo...
> Ciao 1984viking
Spero di esserti stato di aiuto
ciao
AG
Reply to: