[Algoritmi] Calcolo della Complessità

[JoKeRxbLaCk93]

Ciao a tutti ragazzi, ho un esame di algoritmi a breve e non riesco a capire come svolgere questi due esercizi:

Si analizzi la complessità dei seguenti algoritmi. Per ciascuno di essi, detto T(n) il running time, si determini una funzione f(n) tale che T(n) = $ theta $(f(n)).

1) ALGO1(A[1..n])
j <- n/100
while j >= 1 do
----k<-1
----while k <= j do
--------output A[k]
--------k<-2k
----end while
----for i = 1 to sqrt(j) do
---------output A
----end for
----j <- j - 1
end while

2)ALGO2(A[1...n])
j <- n/100
while j >= 1 do
----k<-1
----while k <= j do
--------output A[k]
--------k <- 2k
----end while
----j <- j/2
end while

----------------------------------------------
Non saprei proprio come iniziare, ovvero so che tutte le operazioni semplici valgo O(1), mentre quando ci sono i cicli (for, while) dipende da quante volte viene svolto tale ciclo.Se i cicli sono annidati si moltiplicano le complessità mentre se sono sullo stesso piano si sommano.
Qualcuno saprebbe darmi una mano a capire come si svolgono esercizi del genere?
Grazie mille,

[apatriarca]

I metodi da te descritti funzionano se i cicli sono indipendenti e il costo delle iterazioni costante, ma se non ci troviamo in queste condizioni è necessario usare una strategia diversa. Il costo di un ciclo è uguale alla somma dei costi di ogni singola iterazione. Per cui si ha nel primo algoritmo è prima di tutto necessario osservare che c'è un ciclo infinito (quello che dipende da \(k\)). Il valore di \(k\) viene infatti inizializzato ma mai cambiato. Siccome sappiamo che \( j \geq 1\) e che \( k = 1\) sappiamo che la condizione \( k \leq j \) sarà sempre vera. Suppongo quindi che sia un errore e che l'intenzione fosse di avere un ciclo che viene eseguito \(j\) volte. Il costo a questo punto diventa (C è il costo costante dell'operazione di output):
\[ \sum_{i=1}^{n/100} ( j\,C + \sqrt{j}\,C ) \]

[JoKeRxbLaCk93]

"apatriarca":I metodi da te descritti funzionano se i cicli sono indipendenti e il costo delle iterazioni costante, ma se non ci troviamo in queste condizioni è necessario usare una strategia diversa. Il costo di un ciclo è uguale alla somma dei costi di ogni singola iterazione. Per cui si ha nel primo algoritmo è prima di tutto necessario osservare che c'è un ciclo infinito (quello che dipende da \(k\)). Il valore di \(k\) viene infatti inizializzato ma mai cambiato. Siccome sappiamo che \( j \geq 1\) e che \( k = 1\) sappiamo che la condizione \( k \leq j \) sarà sempre vera. Suppongo quindi che sia un errore e che l'intenzione fosse di avere un ciclo che viene eseguito \(j\) volte. Il costo a questo punto diventa (C è il costo costante dell'operazione di output):
\[ \sum_{i=1}^{n/100} ( j\,C + \sqrt{j}\,C ) \]

Infatti vi è un errore e me ne scuso, nel primo algoritmo k<-2k

Però non riesco comunque a capire qual è il procedimento generale che mi porti a trovare una funzione f(n) tale che possa esprimere il running time come theta di n... Inoltre, come faccio a sapere se posso esprimere questa funzione con theta di n oppure solo con big-O di n? Dalla teoria so che theta di n vuole che la funzione sia contemporaneamente big-O che omega di n, ma come lo dimostro tramite calcoli?

Grazie mille,


EDIT: nel secondo algoritmo quindi sarebbe corretta una soluzione del genere?
\[ \sum_{j=1}^{n/100} ( j\,C logj ) \]

Come esprimo questa sommatoria come funzione f(n)? E come faccio a capire se è valida per theta di n oppure solo per big-O di n?

[apatriarca]

Quello che ho scritto non era un valore approssimato, [strike]anche se è necessario dividere per due il costo del ciclo di \(k\) vista la correzione[/strike]. A quel punto è necessario ancora calcolare il valore di quella sommatoria o iniziare ad usare le definizioni o proprietà dei vari theta, omega..

EDIT: Ok, ero sul cellulare e non avevo letto con particolare attenzione. \(k\) assume i valori \(1, 2, 4, \dots\) ed è quindi chiaro che il ciclo viene eseguito \( \log\,j \) volte. Quindi nel primo algoritmo avremo
\[ C\,\sum_{i=1}^{n/100} ( \log j + \sqrt{j} ). \]
A questo punto possiamo osservare che \( 0 \leq \log j < \sqrt{j} \) nell'intervallo che ci interessa per cui avremo certamente che
\[ \sum_{i=1}^{n/100} \sqrt{j} < \sum_{i=1}^{n/100} ( \log j + \sqrt{j} ) < 2\,\sum_{i=1}^{n/100} \sqrt{j} \]
A questo punto si potrebbe passare agli integrali o altro metodo per verificare che la complessità dovrebbe essere \( \Theta(n^{3/2}). \)

[apatriarca]

Per dimostrare la parte sopra ho usato il fatto che
\[ \int_1^m \sqrt{x-1}\,dx \leq \sum_{i=1}^{m} \sqrt{j} \leq \int_1^m \sqrt{x}\,dx \]
in cui gli integrali possono essere risolti ottenendo che
\[ (2/3)\,(x - 1)^{3/2} \leq \sum_{i=1}^{m} \sqrt{j} \leq (2/3)\,x^{3/2} \]
da cui appare chiaro che la sommatoria appartiene a \( \Theta(n^{3/2}) \) e di conseguenza anche il tuo algoritmo originale.

Il secondo algoritmo non è corretto. Osserva come il ciclo esterno sia eseguito solo \( \log\,(n/100) \) volte.. Quindi hai la seguente sommatoria (dove \(j = 2^d\) e quindi il ciclo interno è eseguito \(d\) volte):
\[ C\,\sum_{d=1}^{\log\,(n/100)} d. \]
A questo punto devi solo ricordarti come si risolvono questo tipo di serie.

[JoKeRxbLaCk93]

Ti ringrazio, c'è un link dove posso guardare come risolvere questo tipo di serie?

[apatriarca]

Si tratta semplicemente della somma dei primi interi positivi: un numero triangolare. Il mio consiglio è quello di guardarti/ripassarti come si risolvono le serie (e memorizzarti le principali come serie aritmetiche, geometriche..).

[JoKeRxbLaCk93]

Infatti, mi sa che il problema è proprio questo. Grazie mille!