CTX - 03 - Complessità Computazionale

Procediamo per induzione su \(n \in \mathbb{N}\).

• Passo base: Per \(n = 1\) e \(n = 2\) si può verificare a mano che la relazione è vera.

• Passo Induttivo: Sia quindi \(n > 2\). Assumiamo come ipotesi induttiva generalizzata che la relazione vale per ogni \(h \leq n\) e dimostriamo che vale anche per \(n+1\).

  \[\begin{split} F_{n} = F_{n-1} + F_{n-2} &= \frac{\alpha^{n-1} - \alpha'^{n-1}}{\sqrt{5}} + \frac{\alpha^{n-2} -\alpha'^{n-2}}{\sqrt{5}} \\ &= \frac{1}{\sqrt{5}}\alpha^{n-2}(\alpha + 1) - \frac{1}{\sqrt{5}}\alpha'^{n-2}(\alpha' + 1) \\ &= \frac{1}{\sqrt{5}}\alpha^{n-2}(\alpha^2) - \frac{1}{\sqrt{5}}\alpha'^{n-2}(\alpha'^2) \\ &= \frac{\alpha^n - \alpha'^n}{\sqrt{5}} \end{split}\]

Procediamo per induzione su \(n \in \mathbb{N}\).

• Passo base: Per \(n = 3\) abbiamo \(F_3 = 2\) e \(\alpha^{3-2} = \alpha \approx 1.61803\). Per \(n = 4\) abbiamo \(F_4 = 3\) e \(\alpha^{4-2} = \alpha^2 = \alpha + 1 \approx 2.61803\).

• Passo Induttivo: Sia quindi \(n > 4\). Assumiamo la relazione per ogni \(h < n\), e dimostriamola per \(n\).

  \[\begin{split} F_n = F_{n-1} + F_{n-2} &> \alpha^{n-3} + \alpha^{n-4} \\ &= \alpha^{n-4}(\alpha + 1) \\ &= \alpha^{n-4}(\alpha^2) \\ &= \alpha^{n-2} \end{split}\]

Applicando l'algoritmo delle divisioni successive ai \(F_{n+1}\) e \(F_{n+2}\) otteniamo:

\[\begin{align*} &F_{n+2} = 1 \cdot F_{n+1} + F_{n}, \quad \quad 0 \leq F_{n} < F_{n+1} \\ &F_{n+1} = 1 \cdot F_{n} + F_{n-1}, \quad \quad 0 \leq F_{n-1} < F_{n} \\ &F_{n} = 1 \cdot F_{n-1} + F_{n-2}, \quad \quad 0 \leq F_{n-2} < F_{n-1} \\ &. \\ &. \\ &. \\ &F_{4} = 1 \cdot F_{3} + F_{2}, \quad \quad 0 \leq F_{2} < F_{3} \\ &F_{3} = 2 \cdot F_{2} + 0, \end{align*}\]

Troviamo quindi \(MCD(F_{n+1}, F_{n+2}) = F_{2} = 1\). Osserviamo inoltre chel'algoritmo, su questa instanza, necessità di \(n-1\) divisioni successive.

Procediamo per induzione su \(n \in \mathbb{N}\).

• Passo base: Per \(n = 2\) troviamo \(alpha^2 = \alpha + 1\), che è vera per come \(\alpha\) è stato definito.

• Passo induttivo: Sia quindi \(n > 2\). Assumiamo come ipotesi induttiva che la relazione vale per ogni \(h < n\), e dimostriamola per \(n\).

  \[\begin{split} \alpha^n &= \alpha^{n-1}\alpha \\ &= (F_{n-1} \alpha + F_{n-2}) \alpha \\ &= F_{n-1}\alpha^2 + F_{n-2}\alpha \\ &= F_{n-1}(\alpha + 1) + F_{n-2}\alpha \\ &= (F_{n-1} + F_{n-2})\alpha + F_{n-1} \\ &= F_{n}\alpha + F_{n-1} \end{split}\]

In particolare, applicando l'ultimo risultato al caso \(n = 5\) ottengo

\[\alpha^5 = F_5 \cdot \alpha + F_4 = 5 \frac{1+\sqrt{5}}{2} + 3 > 10\]

ovvero,

\[\log_{10}{\alpha} > \frac{1}{5}\]

Per calcolare la complessità del massimo comun divisore \(MCD(a, b)\) è importante il seguente risultato.

Teorema(Di Lamé): Sia \(div(a, b)\) il numero di divisioni effettuate per calcolare il \(MCD(a, b)\) utilizzando l'algoritmo euclideo, con \(a, b\) interi tali che \(b \leq a\). Allora, se \(w_{10}(b)\) indica il numero di cifre decimali per rappresentare il numero \(b\), abbiamo che

\[div(a, b) \leq 5 \cdot w_{10}(b) + 1\]

Dimostrazione: Applicando l'algoritmo euclideo ad \(a := r_0\) e \(b := r_1\) otteniamo:

\[\begin{align*} &r_0 = q_1 \cdot r_1 + r_2, \quad \quad &0 \leq r_2 < r_1 \\ &r_1 = q_2 \cdot r_2 + r_3, \quad \quad &0 \leq r_3 < r_2 \\ &. &\\ &. &\\ &. &\\ &r_{n-2} = q_{n-1} \cdot r_{n-1} + r_n, \quad \quad &0 \leq r_n < r_{n-1} \\ &r_{n-1} = q_{n} \cdot r_n + 0& \end{align*}\]

L'algoritmo termina dopo \(n\) passi e otteniamo \(r_n = MCD(a, b)\). Osserviamo poi che

\[\begin{align*} &r_{n} \geq 1 = f_2 \\ &r_{n-1} = q_nr_n \geq 2r_n = 2f_2 = f_3 \\ &r_{n-2} = q_{n-1}r_{n-1} + r_n \geq r_{n-1} + r_{n} \geq f_3 + f_2 = f_4 \\ &r_{n-3} = q_{n-2}r_{n-2} + r_{n-1} \geq r_{n-2} + r_{n-1} \geq f_4 + f_3 = f_5 \\ &. \\ &. \\ &. \\ &r_{2} = q_{3}r_{3} + r_{4} \geq r_{3} + r_{4} \geq f_{n-1} + f_{n-2} = f_{n} \\ &r_{1} = q_{2}r_{2} + r_{3} \geq r_{2} + r_{3} \geq f_{n} + f_{n-1} = f_{n+1} \end{align*}\]

troviamo quindi che \(b = r_{1} \geq f_{n+1}\).

Sapendo inoltre che \(f_n > \alpha^{n-2}\), troviamo che \(b \geq f_{n+1} > \alpha^{n-1}\), e, prendendo il logaritmo in entrambi i lati, otteniamo:

\[\log_{10} {b} > (n-1)\log_{10}{\alpha} \iff n < \frac{\log_{10}{b}}{\log_{10}{\alpha}} + 1\]

Infine, utilizzando il fatto che \(\log_{10}{\alpha} > \frac{1}{5}\), otteniamo

\[div(a, b) = n < 5\log_{10}{b} + 1 = 5w_{10}(b) + 1\]

ovvero il numero di divisioni effettuate dall'algoritmo euclideo per il calcolo di \(MCD(a, b)\) è limitato superiormente da \(w_{10}(b)\).

\[\tag*{$\blacksquare$}\]

Siamo ora in grado di calcolare la complessità del calcolo di \(MCD(a, b)\), con \(n \geq a \geq b\). Infatti, dato che il costo per ogni singola divisione è \(O(\log^2 n)\), e dato che effettiamo al massimo \(O(\log b) = O(\log n)\), otteniamo una complessità totale di

\[O(\log n) \cdot (\log^2 n) = O(\log^3 n)\]

Sia \(n \in \mathbb{N}\), e consideriamo la funzione fattoriale definita nel seguente modo:

\[n! := \begin{cases} (n-1)! \cdot n & n > 1 \\ 1 & n = 1 \end{cases}\]

Andiamo adesso a stimare il numero di operazioni elementari necessarie per calcolare \(n!\).

Utilizzando la definizione appena data possiamo notare che, per calcolare \(n!\), mi devo prima calcolare \((j+1)!\) per \(j\) che va da \(1\) a \(n-1\). Voglio quindi stimare il numero di operazioni necessari per calcolare il seguente prodotto:

\[(j+1)! = j! \cdot (j+1) \,\,\,\,, \,\,\,\, j \in \{ 1,..., n-1\}\]

Possiamo stimare la lunghezza di \(j+1\) con quella di \(n\). Infatti \(j+1 \leq n\) e quindi \(\log (j+1) \leq \log n\). Per quanto riguarda la lunghezza di \(j!\) invece, notiamo che se effettuiamo il prodotto di due numeri di lunghezza \(n_1\) e \(n_2\), otteniamo un numero di lunghezza \(n_1 + n_2\). Sapendo poi che

\[j! = 1 \cdot 2 \cdot ... \cdot (j-1) \cdot j \leq \underbrace{n \cdot n \cdot ... \cdot n \cdot n}_\text{$j$ volte} = n^j\]

possiamo limitare la lunghezza di \(j!\) con la lunghezza di \(n^j\), che è \(O(j \cdot \log{n})\).

Mettendo tutto insieme possiamo stimare il calcolo di \((j+1)!\) tramite

\[(j \cdot \log{n}) \cdot \log{n} = j \cdot \log^2{n}\]

Il costo totale risulta quindi essere: \(c(n!) = n \cdot O(n\log^2{n}) = O(n^2 \log^2{n})\), che notiamo è esponenziale rispetto alla dimensione dell'input.

Ricordiamo che l'algoritmo standard per moltiplicare due interi \(a, b\) con \(a \leq b\) ha una complessità dell'ordine di \(O(\log{a} \cdot \log{b})\). Se poi \(n\) è un intero tale che \(n \geq a, b\), otteniamo una complessità di \(O(\log^2{n})\).

Siamo quindi portati a pensare che non esiste un algoritmo in grado di moltiplicare due interi che sia asintoticamente migliore rispetto a quello che impariamo alle scuole elementari. In realtà, anche se sembra molto strana come cosa, questo non è vero: esiste infatti un algoritmo, l'algoritmo di Karatsuba, che riesce a moltiplicare due interi \(a, b\) in tempo \(O(\log^{\log_2 3} n)\). Notando che che \(\log_2 3 < 2\) possiamo affermare che l'algoritmo di Karatsuba è asintoticamente più veloce rispetto l'algoritmo standard per la moltiplicazione di due interi.

Successivamente alla scoperta da parte di Karatsuba del suo particolare algoritmo per moltiplicare due interi, sono stati scoperti tutta una serie di miglioramenti, arrivando ad ottenere una complessita di \(O(\log^{1 + \epsilon} n)\), \(\forall \epsilon > 0\).

Questo risultato ci dice che moltiplicare due costa poco più che scrivere i numeri in memoria.

Siano \(f(x)\) e \(g(x)\) due polinomi a coefficienti interi di grado \(n_1\) e \(n_2\) rispettivamente, con \(n_1 \geq n_2\). Sia \(n\) un intero che maggiora i coefficienti di entrambi i polinomi. Il prodotto di \(f(x)\) per \(g(x)\) viene definito nel seguente modo

\[[f \cdot g](x) := \sum_{l = 0}^{n_1 + n_2} {\sum_{i + j = l} {a_ih_j}x^l}\]

Iniziamo notando che la complessità di ogni prodotto della forma \(a_ih_j\) può essere stimata con \(O(\log^2 {n})\). Per il calcolo del coefficiente relativo a \(x^l\) dobbiamo, come prima cosa, calcolarci tutti i termini della forma \(a_ih_j\), e questi possono essere al più \(n_2 + 1\), ottenendo una complessità di \(O(n_2\log^2 n)\). Una volta calcolati tutti i termini poi, li dobbiamo sommare tra loro, eseguendo al più \(n_2\) somme. Il costo di ciascuna somma varia a seconda della lunghezza degli addendi. Iniziando però con addendi di lunghezza \(O(\log n)\), ed effettuando al più \(n_2\) somme, possiamo stimare la lunghezza massima raggiungibile con \(O(\log n + \log {n_2})\). Il costo per sommare i vari prodotti è quindi \(O(n_2(\log n + \log n_2))\). Il costo totale per calcolare il coefficiente del termine \(x^l\) è quindi stimato da \(O(n_2(\log^2 n) + n_2(\log n + \log n_2))\) = \(O(n_2(\log^2 n + \log n_2))\). Infine, dovendo ripetere tale procedimento per ogni \(l = 0, ..., n_1 + n_2\), otteniamo una complessità totale

\[O(\underbrace{(n_1 + n_2)}_{l = 0,...,n_1 + n_2} \cdot \underbrace{n_2(\log^2n + \log n_2)}_{\text{calcolo coefficiente $x^l$}})\]

Una volta che ci siamo calcolati il \(MCD(a, b)\), per trovare l'identità di Bézut non dobbiamo far altro che eseguire \(O(\log b)\) volte una moltiplicazione e una divisione, ottenendo una complessità totale di

\[\underbrace{ O(\log^3 n)}_{\text{calcolo MCD(a, b)}} + \underbrace{O(\log^3 n)}_{\text{calcolo identità Bézut}} = O(\log^3 n)\]

Notiamo poi che esistono infinte identità di Bézut. Infatti, fissati \(a, b \in \mathbb{Z}\) abbiamo che partendo da una identità ne possiamo sempre costruire un'altra nel seguente modo

\[\begin{split} MCD(a, b) &= \alpha a + \beta b \\ &= \alpha a + \beta b + 0 \\ &= \alpha a + \beta b + c(ab - ba) \\ &= (\alpha - cb) a + (\beta + ca) \\ \end{split}\]