Analisi complessità algoritmo

[g0t3nk5]

Ho problemi a capire come si debba procedere per l'analisi della complessità degli algoritmi... :muro:

http://img715.imageshack.us/img715/3137/complessita.png

Per il momento mi fermo al primo quesito...

Per quale motivo per n <= 44 il tempo richiesto è una costante (che non dipende quindi da n) quando invece il ciclo for j:= 1 to n ... viene eseguito sempre a prescindere dalla dimensione di n? :rolleyes:

Grazie in anticipo. ;)

[gugoXX]

Secondo me hanno invertito i 2 temini n>=44 e n<44 nella definizione di T(N)
Comunque direi anche io O(N) per n>44. Avranno dimenticato un nc2 per questo termine.

[tuccio`]

da com'è fatta l'equazione di ricorrenza direi che hanno interpretato, sbagliando ovviamente, il for dentro l'if

[g0t3nk5]

OK, passiamo ad un altro esercizio sperando la soluzione non sia errata anche questa...

[ESERCIZIO 1]
http://www.cs.unibo.it/~vassura/ASD/Compito_ASD_Feb_03.pdf
http://www.cs.unibo.it/~vassura/ASD/svolgimento2.pdf

Perchè la condizione n tra 2 e 10 non viene considerata?

[tuccio`]

ora che ci penso non è sbagliata.. se n <= 44 anche il ciclo di prima si può dire che è O(44) (il for i = 1 to n)

sono entrambe corrette, il motivo è lo stesso.. se c'è una limitazione superiore dell'input (cioè ti metti nel caso n <= k dove k è costante) allora qualcosa che è lineare in n diventa lineare in k.. e O(k) = O(1)

pardon per la cazzata di prima :E

[gugoXX]

Vabbe'.
Pero' allora una definizione tipo:


BubbleSort(array) =
{
n = params.length;
for j = 1 to n-1
for k = 1 to j
if array[k]<array[k+1]
swap(array[j],array[j+1];

if n<100000000000 then
BubbleSort = BubbleSort.Var();
else
BubbleSort = 15
}


Cosa diciamo?
Che se le la lunghezza dell'array e' >100000000000 allora e' O(c1) +O(n^2) = O(N^2) ,
mentre se e' <=100000000000 diciamo che e' O(N) ,
ovvero la varianza di tutti i valori dopo averli ordinati, che si puo' calcolare appunto in O(N), ignorando la prima parte data per costante perche' pari a O(100000000000 * 100000000000 /2)?

[marco.r]

Cosa diciamo?
Che se le la lunghezza dell'array e' >100000000000 allora e' O(c1) +O(n^2) = O(N^2) ,
mentre se e' <=100000000000 diciamo che e' O(N) ,
ovvero la varianza di tutti i valori dopo averli ordinati, che si puo' calcolare appunto in O(N), ignorando la prima parte data per costante perche' pari a O(100000000000 * 100000000000 /2)?

La complessita' e' asintotica, non ha quindi senso parlare di O(1) "per n <= K"
Ha piu' senso parlare (come fa l'esercizio) di T(n) per n <= 44, perche' ti serve per costruire il caso base, e la maggiorazione n <= c_1 aiuta a semplificare il ragionamento.

[tuccio`]

Vabbe'.
Pero' allora una definizione tipo:


BubbleSort(array) =
{
n = params.length;
for j = 1 to n-1
for k = 1 to j
if array[k]<array[k+1]
swap(array[j],array[j+1];

if n<100000000000 then
BubbleSort = BubbleSort.Var();
else
BubbleSort = 15
}


Cosa diciamo?
Che se le la lunghezza dell'array e' >100000000000 allora e' O(c1) +O(n^2) = O(N^2) ,
mentre se e' <=100000000000 diciamo che e' O(N) ,
ovvero la varianza di tutti i valori dopo averli ordinati, che si puo' calcolare appunto in O(N), ignorando la prima parte data per costante perche' pari a O(100000000000 * 100000000000 /2)?semplicemente se non ti rendi conto che per n <= 44 puoi maggiorare il tempo con una costante, la tua analisi di quella ricorrenza può risultare molto meno raffinata... magari potrebbe venirti qualcosa in più di O(n^2) che di per sé non è sbagliato, ma poco preciso

le costanti non contano asintoticamente, puoi aggiungere o togliere tutti gli zeri che vuoi da quei numeri, non cambia niente

[gugoXX]

Quindi abbiamo un comodo metodo per trasformare tutti gli algoritmi che conosciamo in O(1) :asd:

[tuccio`]

fammi un esempio allora

[gugoXX]

Quello di prima.
BubbleSort modificato tale per cui se il numero di valori da ordinare e' inferiore a
100000000000
se c'è una limitazione superiore dell'input (cioè ti metti nel caso n <= k dove k è costante) allora qualcosa che è lineare in n diventa lineare in k.. e O(k) = O(1)

allora la compessita' e' maggiorata da O(100000000000 * 100000000000 /2) = O(1)

[tuccio`]

di solito si studia il caso pessimo |:

[DanieleC88]

Quello di prima.
BubbleSort modificato tale per cui se il numero di valori da ordinare e' inferiore a
100000000000 allora la compessita' e' maggiorata da O(100000000000 * 100000000000 /2) = O(1)

La notazione O grande nasconde la costante, che può essere più o meno grande a seconda dell'algoritmo. Nessuno ti vieta di impostare la costante ad un valore esageratamente grande, se sai di non superarlo mai. Se tu sapessi che il bubble sort dopo un certo numero n di elementi in input non aumenta la sua complessità, allora potresti dire senza sbagliare che la sua complessità è O(1), ovvero che non supera mai un certo valore costante.

La definizione è:

http://operaez.net/mimetex/f(n)%20%5Cin%20O(g(n))%5C:%5CLongleftrightarrow%5C:%5Cexists%20c,%20n_0%20%5Cin%20%5Cmathbb{N}:%5C:f(n)%20%5Cle%20c%20%5Ccdot%20g(n),%5C:%5Cforall%20n%20%5Cgt%20n_0

In questo caso ci rientri benissimo, visto che ti basta scegliere - spero di non commettere errori - c = n+1, n0 = n+1, g(n) = 1. La condizione è sempre vera, ed il tempo è asintoticamente "costante" - ossia, da un certo punto in poi non cambia mai. Ciò però ci dice che al più ci metterà sempre lo stesso tempo, ma non ci dice niente riguardo alla "bontà" di questo algoritmo in termini di tempo umano. Nel nostro caso la costante è così assurdamente grande che sarebbe un'aberrazione dire che quella complessità è "buona" per affrontare il problema.
Ma resta costante.

ciao ;)

P.S.: le (basse) costanti nascoste sono anche parte del motivo per cui il Quicksort (che nominalmente sarebbe quadratico, se guardiamo alla notazione in O grande) spesso è più performante di altri algoritmi come Heap sort e Merge sort, che invece sono n·log(n), per cui non c'è da stupirsi che vengano fuori risultati come questo! :)