Efficienza dell'algoritmo...

[kioccolatino90]

buon pomeriggio mi stavo chiedendo se un algoritmo rappresentato da una funzione che oscilla tra due valori, a livello pratico l'algoritmo è instabile? cioè non è buono... gisto?

[hamming_burst]

Spiegati meglio, perchè la domanda è un po' vaga...a me non dice nulla di concreto.

cosa intendi per funzione dell'algoritmo? l'equazione di ricorrenza?

[kioccolatino90]

Intendo l'andamento dell'algotirmo, ad esempio un algoritmo può può avere un andamento del tipo $an^2+bn+c$....

[vict85]

"domy90":buon pomeriggio mi stavo chiedendo se un algoritmo rappresentato da una funzione che oscilla tra due valori, a livello pratico l'algoritmo è instabile? cioè non è buono... gisto?

Ma intendi dire tipo nel caso in cui la funzione avesse complessità $c + senN$? Beh... sarebbe una funzione o(1) quindi un sogno...

[hamming_burst]

"vict85":[quote="domy90"]buon pomeriggio mi stavo chiedendo se un algoritmo rappresentato da una funzione che oscilla tra due valori, a livello pratico l'algoritmo è instabile? cioè non è buono... gisto?

Ma intendi dire tipo nel caso in cui la funzione avesse complessità $c + senN$? Beh... sarebbe una funzione o(1) quindi un sogno...[/quote]

bhe dai non è sogno, ci sono algoritmi molti elaborati che hanno una meravigliosa complessità nel caso medio $Theta(1)$ (es. strutture Merge-Find), o anche se si guarda solo una struttura dati come una coda, le sue funzioni hanno complessità $O(1)$.

Invece una funzione di costo oscillante quella è un sogno, se prendiamo questa fantasiosa funzione oscillante $f(n) = c + sin(n)$ e facciamo un'analisi:

Il seno è compreso fra $-1$ e $1$; se prendiamo $c>1$, il valore può essere limitato superiormente e inferiormente da una una costante, e la complessità è $Theta(1)$.
Ma la questione non si pone, un algoritmo vero con questa funzione, a quanto conosco, non esiste.

[kioccolatino90]

ma quindi se ammettiamo che esista, il fatto che essa oscilla vuol dire che è un ottimo programma oppure che è un programma che non serve a niente??? suppongo la prima....perchè significa che qualunque input che riceve il programma esso non esce al di fuori di quei valori ed esegue tutto in un certo tempo alla perfezione.....o no???

[hamming_burst]

Direi invece che non è stabile.

Informalmente parlando (efficenza/inefficenza è un qualcosa di astratto):

Dipende dall'intervallo di oscillazione, se è [-1,1] (ricordandoti che le complessità asintotiche sono sempre positive ed intere) sei una classe costante.
Se invece se su [0, 10000000000000000000000000000000000] ed è oscillante, non puoi far affidamento ad un algoritmo del genere, hai un'altalena costante-superpolinomiale.
Un algoritmo di questo tipo è super-polinomiale oscillante (mi sono inventato la classe al momento) e vedi te cosa fartene di una cosa del genere.

[kioccolatino90]

se ho capito bene vuol dire che se l'intervallo si oscillazione è ad esempio $[1;2]$ è buono perchè è intero positivo...????

[hamming_burst]

[1,2] è costante, perciò è nella classe $Theta(1)$, classe costante. Perciò, se vuoi usare questo termine, sì è buono (con tutti i limiti di algoritmica del caso).
Ma non perchè è intero positivo, tutte le funzioni di costo sono sugli interi positivi (una classe negativa la hai mai vista?), ma perchè l'intervallo è limitato.

PS: domanda, dove hai trovato una funzione di costo di un algoritmo, con queste proprietà?

[apatriarca]

La constante di un algoritmo di complessità costante può essere grande a piacere. Per cui una funzione che oscilla in $[0, 10000000000000000000000000000000000]$ può comunque essere maggiorata da una funzione costante e quindi, anche esistesse un algoritmo con un comportamento del genere, sarebbe pur sempre di complessità costante. Spesso nell'analisi degli algoritmi si ignorano queste costanti che possono essere comunque importanti per stabilire il miglior algoritmo da utilizzare in una specifica situazione. Il metodo di Cramer per l'inversione di una matrice ha ad esempio una complessità di $O(n!)$ ma su un computer moderno è il miglior algoritmo per piccole matrici (fino all'ordine 6 circa) anche se esistono algoritmi con complessità molto inferiore.

@domy90: se fai queste domande è chiaro che non hai compreso del tutto il significato di complessità asintotica. Supponi che la il tuo algoritmo venga eseguito in $g(n) = (100*cos(n) + 300)n*log(n)$. In questo caso avrai che $g(n) <= 400*n*log(n)$ per cui sarà $O(n*log(n))$.

[hamming_burst]

"apatriarca":La constante di un algoritmo di complessità costante può essere grande a piacere. Per cui una funzione che oscilla in $[0, 10000000000000000000000000000000000]$ può comunque essere maggiorata da una funzione costante e quindi, anche esistesse un algoritmo con un comportamento del genere, sarebbe pur sempre di complessità costante. Spesso nell'analisi degli algoritmi si ignorano queste costanti che possono essere comunque importanti per stabilire il miglior algoritmo da utilizzare in una specifica situazione. Il metodo di Cramer per l'inversione di una matrice ha ad esempio una complessità di $O(n!)$ ma su un computer moderno è il miglior algoritmo per piccole matrici (fino all'ordine 6 circa) anche se esistono algoritmi con complessità molto inferiore. .

ci metti sempre na pezza hai miei post

Ma hai ragione, lo ho dato un po' per scontato. Ma dipende sempre dall'istanza del problema.

[kioccolatino90]

"ham_burst":
PS: domanda, dove hai trovato una funzione di costo di un algoritmo, con queste proprietà?

non l'ho preso ho pensato soltando che esistesse.....

"apatriarca":se fai queste domande è chiaro che non hai compreso del tutto il significato di complessità asintotica

si perchè io ancora non le ho studiate, me le ha messe in testa un amico, e io devo capire perchè se no ci penso la notte e non dormo....