Algoritmi - Complessità

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...

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: it.wikipedia.org/wiki/…

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

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

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....

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...

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.

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)...