[C++] Calcolo del costo di un algoritmo

[vale_stella84]

salve,non ho mai capito cosa si intede per "costo di un algoritmo o complessità di temp" etc..
so che c'è un modo per calcolarlo,qualcuno potrebbe spiegarmelo casomai con qualche esempio di codice?
grazie mille

[programmerscafe]

Ciao, non sono un accademico, comunque in genere per "costo di un algoritmo" o "complessita' di tempo" si intende meramente quanto ci vuole a far girare il tuo algoritmo. Semplicemente quanto tempo ci vuole. Nota che questa e' una definizione estremamente aleatoria, e poco utile, dato che il tempo necessario a far girare un programma e' affetto evidentemente da variabili come potenza CPU, velocita di IO e non dice un gran che dell'algoritmo che si sta usando etc.

La complessita di un algoritmo invece (quella che trovi con la notazione stile O(n), O(n^2) etc. nei libri di testo ) indica in un certo qual modo l'efficienza di un algoritmo, quante operazioni deve fare l'algoritmo al crescere dell'input (lo so e' una definizione estremamente schifosa).

I due tipici esempi sono:
1) Ricerca lineare in un array ordinato = complessita' O(n), ovvero lineare, il programma cerca dall'inizio alla fine finche non trova quello che cerca.
2) Ricerca per bisezione in un array ordinato complessita O(log2(n)), che e' molto meglio. (l'algoritmo e' molto semplice ma spiegarlo qui non e' il caso)

Il due algoritmi fanno la stessa cosa ma il secondo e' molto piu' "sveglio" e questa cosa e' espressa in termini di "complessita'" nel modo che ti ho esposto sopr, quindi meno e' complesso e piu' l'algoritmo e' "furbo" (nota log2(n)<n, se n=100, log2(100) = 10)

Spero di non averti creato ulteriore confusione
ciao

[vale_stella84]

ti ringrazio molto per avermi chiarito le idee,userò un libro per entrare nello specifico