Algoritmi - Complessità

Forum - Algoritmi - Complessità

BugliL (Member)
Pro

Messaggi: 135
Iscritto: 09/08/2009

Postato alle 13:33
Mercoledì, 10/02/2010

Qualcuno conosce un metodo semplice per capire la complessità di un'algoritmo?

Trovo che Cn = log2(n) come complessità di una ricerca binaria non sia molto intuitiva come cosa...

Ultima modifica effettuata da BugliL il 11/02/2010 alle 12:43

netarrow (Admin)
Guru^2

Messaggi: 2502
Iscritto: 12/05/2004

Postato alle 16:23
Mercoledì, 10/02/2010

se il problema è la notazione in se, non ne conosco altre.

se il problema è invece il calcolo della complessità nelle funzioni ricorsive, se rispettano una certa forma puoi usare il teorema master: http://it.wikipedia.org/wiki/Teorema_principale_(informatica)

Ultima modifica effettuata da netarrow il 10/02/2010 alle 16:23

nessuno (Normal User)
Guru^2

Messaggi: 6402
Iscritto: 03/01/2010

Postato alle 17:24
Mercoledì, 10/02/2010

Testo quotato

Postato originariamente da BugliL:

Qualcuno conosce un metodo semplice per capire la complessità di un'algoritmo?

Trovo che O(N) = log2(N) come complessità di una ricerca binaria non sia molto intuitiva come cosa...

Non mi pare che deve essere intuitivo o meno ... è così.

Neanche la celebre e=mc^2 è intuitiva .... ma è così.

Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti ( uno dei padri fondatori del moderno Calcolo delle probabilità ) chiamava il gioco del Lotto Tassa sulla stupidità.

TheKaneB (Member)
Guru^2

Messaggi: 1792
Iscritto: 26/06/2009

Postato alle 1:46
Giovedì, 11/02/2010

la formula corretta della funzione O per la ricerca dicotomica (o binaria, se vuoi chiamarla così), è O( log2( n ))
Attento a non confonderti. L'equazione che hai scritto tu, cioè O(N) = log2(N), è priva di ogni significato matematico.

BugliL (Member)
Pro

Messaggi: 135
Iscritto: 09/08/2009

Postato alle 12:42
Giovedì, 11/02/2010

Testo quotato

Postato originariamente da TheKaneB:

la formula corretta della funzione O per la ricerca dicotomica (o binaria, se vuoi chiamarla così), è O( log2( n ))
Attento a non confonderti. L'equazione che hai scritto tu, cioè O(N) = log2(N), è priva di ogni significato matematico.

Sì scusatemi perfettamente ragione volevo scrivere Cn = log2(n)....
dopo 2 ore di studio do i numeri....

BugliL (Member)
Pro

Messaggi: 135
Iscritto: 09/08/2009

Postato alle 12:45
Giovedì, 11/02/2010

Testo quotato

Postato originariamente da nessuno:
Non mi pare che deve essere intuitivo o meno ... è così.
Neanche la celebre e=mc^2 è intuitiva .... ma è così.

Mi sono spiegato male.... il mio problema è come arrivare a log2(n) non la funzione in se stessò. Il risultato mi è chiaro, è il procedimento con cui arrivarci che mi risulta difficoltoso...

Ultima modifica effettuata da BugliL il 11/02/2010 alle 12:49

netarrow (Admin)
Guru^2

Messaggi: 2502
Iscritto: 12/05/2004

Postato alle 12:52
Giovedì, 11/02/2010

per arrivare a quel risultato o usi il teorema master (però non ricordo la formula di ricorrenza della ricerca dicotomica quindi non sono sicuro si possa usare) o devi costruirti l'albero delle ricorrenze e sfruttando le proprietà degli alberi calcolarti una serie che risolta ti darà il risultato finale.

ah dimenticavo c'è anche il metodo per sostituzione dove mano a mano sostituisci nella formula di ricorrenza i vari passi, ma è più facile incasinarsi li.

Ultima modifica effettuata da netarrow il 11/02/2010 alle 12:54

pierotofy (Admin)
Guru^2

Messaggi: 6230
Iscritto: 04/12/2003

Postato alle 18:58
Giovedì, 11/02/2010

Un altro metodo che puoi utilizzare se la funzione e' abbastanza semplice e' attraverso l'osservazione del sorgente... ad esempio un algoritmo che per fare i suoi calcoli impiega due cicli for nidificati da 0 a N (e questa e' la parte piu' pensante dell'algoritmo) sai subito che e' O(N^2)...

Il mio blog: https://piero.dev