[Algoritmi] Analisi complessità e ricorrenze

[Riky1993]

Ciao a tutti, fra qualche giorno devo sostenere l'esame di introduzione agli algoritmi, ma continuo ad avere molti problemi ad analizzarli e a risolvere la relazione di ricorrenza usando il metodo di sostituzione... Posto subito un algoritmo che non riesco a risolvere:

Codice:

void f(int A[], int inizio, int fine) {
                  int n = fine - inizio + 1
                  sia B un array di interi
                  if (n > 1) {
                      copia(B, A, inizio, fine)
                      f(A, inizio, inizio + n/3)
                      f(A, inizio + 2n/3 + 1, fine)
                  }
          }
dove copia(B,A,i,j) copia in B il contenuto dell'array A dalla posizione i alla posizione j.


Per quanto riguarda la prima riga (int n =...) ovviamente è un semplice assegnamento, ma poi dentro all'if viene richiamata la funzione iniziale, a quanto equivalgono copia, f e l'ultima f? Non riesco proprio a capirlo... Grazie dell'aiuto!

[vict85]

Direi che si trasforma in una funzione ricorsiva del tipo \(f(N) = O(N)+2f(N/3)\). Supponendo che copia sia lineare.

[Riky1993]

Ti ringrazio della risposta, sapresti spiegarmi passo per passo quello che hai fatto per arrivare a quella soluzione?

[Riky1993]

Poi oltre alla domanda sopra ho provato a svolgere una ricorrenza:
Questa è la ricorrenza: \( T(n) = 2T([n/2]) + n \) e suppongo che la soluzione è \(\ T(n) = O(nlogn) \)
\(\ T(n) <= 2(c(n/2)log(n/2)) + n
<= cn log(n/2) + n
= cnlogn - cnlog2 + n
= cnlogn - cn + n
<= cnlogn
\)

Fino a qui tutto ok (almeno per questa ricorrenza), poi ho provato a leggere il caso base dal libro ma non l'ho capito. Prima di tutto dice che l'unica condizione al contorno della ricorrenza è T(1)=1 e poi fa questo:
per n = 1 il limite T(n) <= cnlogn diventa T(1) <= c1log1 = 0 e va bene, log di 1 è 0
poi dopo prova per n = 2, e fa T(2) = 4 e T(3) = 5. Da dove escono 4 e 5 come risultati? Li ha sostituiti a cnlogn?

[vict85]

Hai \(\displaystyle n = \text{fine} - \text{inizio} +1 \).

L'analisi mi pone a ragionare nel seguente modo:

La creazione dell'array suppongo abbia costo costante \(\displaystyle c \).
La copia ha costo \(\displaystyle n \).
Dopo la copia, la funzione chiama nuovamente \(\displaystyle f \) con un valore \(\displaystyle n_2 = \text{inizio} +n/3 - \text{inizio} +1 = \lfloor n/3 \rfloor + 1 \approx \lceil n/3\rceil \).
Successivamente, richiama la funzione \(\displaystyle f \) con valore \(\displaystyle n_3 = \text{fine} - \text{inizio} - 2\lfloor n/3\rfloor + 1 + 1 = n - 2\lfloor n/3\rfloor + 1 \approx \lceil n/3\rceil \).

Pertanto si ha \(\displaystyle T(n) = 2T(\lceil n/3\rceil) + n + c \). A me sembra un classico esempio di utilizzo del Master Theorem.

[Riky1993]

Grazie della spiegazione, il teorema dell'esperto comunqur non è nel programma e infatti non lo metterà nell'esame... Per quanto riguarda la relazione di ricorrenza sopra invece?

[Riky1993]

Ho provato a fare un'altra ricorrenza ma mi blocco ad un certo punto...
Questa è la ricorrenza:
\[ \left\{

\begin{array}{lcr}
2T(n/2) + \Theta(logn) \ n>=4 \\
\Theta(1) \ other
\end{array}
\right.
\]
Che ho provato a svolgere così (supponendo che \(\ T(n) = O(nlogn))\):

\(\ T(n) <= 2(c(n/2)log(n/2) + dlogn \\
~~~~~~~~~ <= cnlog(n/2) + dlogn
\)

però a questo punto già mi blocco, perché che faccio scrivo \(\ cnlogn + dlogn <= cnlogn \) o non ha senso?

[vict85]

Perché mette diviso 2? È diviso 3. Ti conviene prendere un \(n=3^m\). A questo punto risolvi la ricorsione \(S(m) = 2S(m-1)+3^m\). Per risolverlo potrebbe essere comodo dividere tutto per \(2^m\) e passare alla ricorsione \(\displaystyle P(m) = \frac{S(m)}{2^n}\).

[Riky1993]

Scusami in che senso dici di mettere diviso 3? E' un'altra ricorrenza non quella che stava all'inizio, o forse no ho capito cosa intendi...

[vict85]

Hai messo 2 per sbaglio anche nel tuo terzo messaggio. Stai cercando di usare l'induzione, anche se manca il caso base.

Supponiamo che \(\displaystyle n \) sia sufficientemente grande¹ e che si abbia \(\displaystyle T(n/2) = \Theta(n\log n) \). Allora \begin{align}k_1n \log \frac{n}{2} + c_1\log n & \le T(n) \le k_2n \log \frac{n}{2} + c_2\log n \\
\min(k_1, c_1) \biggl(n\log n - n \log 2 + \log n \biggr) & \le T(n) \le \max(k_2, c_2) \biggl(n \log n - n \log 2 + \log n \biggr) \\ \min(k_1, c_1) \biggl(n\log n - n + \log n \biggr) & \le T(n) \le \max(k_2, c_2) \biggl(n \log n - n + \log n \biggr) \end{align}

Ora è evidente che per \(\displaystyle n \) sufficientemente grossa \(\displaystyle 0 < \log n < n < \varepsilon n\log n \) per un qualche \(\displaystyle 0 < \varepsilon < 1 \). Pertanto si ha che
\begin{align} \min(k_1, c_1) \biggl(n \log n - n + \log n \biggr) & \le T(n) \le \max(k_2, c_2)\biggl(n \log n - n + \log n \biggr) \\ \min(k_1, c_1) \biggl(n \log n - \varepsilon n \log n \biggr) & \le T(n) \le \max(k_2, c_2) \biggl(n \log n + \varepsilon n\log n \biggr) \\ (1-\varepsilon)\min(k_1, c_1) n \log n & \le T(n) \le (1+\varepsilon)\max(k_2, c_2) n \log n \end{align}



Il caso base è un po' tedioso dato che si ha \(\displaystyle \Theta(\log n) \) invece che un più fattibile \(\displaystyle c\log n \).

[edit] Mi ero dimenticato della moltiplicazione per 2.

---

Note

1. Il quanto grande dipende dalla funzione che viene sommata nella ricorsione e dal caso base. ↑