Tempo logaritmico

[ybor4]

Salve a tutti!

Io ho ben chiaro cos'è un logaritmo ma non ho proprio la cognizione di tempo logaritmico o polinomiale o esponenziale.

Qualcuno potrebbe fare chiarezza in parole semplici magari con un esempio grazie

[Rggb1]

Forse intendi la "complessità temporale" di un algoritmo usando la notazione asintotica (aka $O()$)?

[ybor4]

Sinceramente spesso sento dire ha una crescita esponenziale o polinomiale, intuitivamente credo che sia un concetto di funzione

ad esempio y:= log x ;

[hamming_burst]

Nell'analisi degli algoritmi si misurano le caratteristiche di un algoritmo con unità di misura prese dall'analisi matematica e dalla teoria della complessità, la complessità asintotica.
Di solito nei vari metodi di calcolo della complessità si usa la O() (O-grande) come ha detto Rggb, o la Theta.
Di solito si calcolano le quantità di risorse occupate (S()) e il tempo impiegato (T()), tempo non in cicli di cpu ecc, ma tempo algoritmico.

esempio:

- "tempo lineare" -> $O(n)$
- "tempo polinomiale -> $O(n^2)$
- " tempo esponenziale" -> $O(2^n)$

Va precisato che O() è un esempio di funzione e tutte hanno una definizione ben formata.

[edge1]

Per esempio, supponiamo di avere una lista di elementi:

struct elem
{
        int a;
        elem*pun;
}; elem*testa;

Supponiamo di voler trovare l'elemento (unico) della lista con il campo intero uguale a 4.
Un metodo sarebbe quello di scorrere la lista dalla testa alla fine,avremo allora una complessità O(N).
Supponiamo adesso di effettuare inserimenti ordinati in lista.
Sicuramente avremo una complessità maggiore nell'inserimento stesso,da un O(1) inserimento in testa ad un O(n) per inserimento ordinato.
Va da se però che l'estrazione invece a questo punto può essere ottimizzata,mediante l'uso dell'algoritmo della ricerca Binaria, con complessità Logaritmica.
Conosci quest'ultimo Algoritmo?

[ybor4]

Si si ora inizio a capire!

[edge1]

Bene,devi dare l'esame di Algoritmi e Strutture dati?

[ybor4]

No già dato.

[dzcosimo]

"ybor4":No già dato.

eh allora il tuo dubbio assume le dimensioni di un problema di non poco conto
dove studi?
con quanto hai passato l'esame?

[Pietro_Bonf]

"dzcosimo":[quote="ybor4"]No già dato.

eh allora il tuo dubbio assume le dimensioni di un problema di non poco conto
dove studi?
con quanto hai passato l'esame?[/quote]

In effetti la definizione della complessità dovrebbe essere una nozione di base in qualsiasi corso di algoritmica