Qual è la complessità temporale dell'algoritmo GCD di Euclide?
Considera due passi qualsiasi dell'algoritmo.
A un certo punto, hai i numeri [math](a,b)[/math] con [math]a > b[/math]. Dopo il primo passo questi diventano [math](b,c)[/math] con [math]c=a\bmod b[/math], e dopo il secondo passo i due numeri saranno [math](c,d)[/math] con [math]d=b\bmod c[/math]. Poiché [math]d=b\bmod c[/math], sappiamo che [math]b=kc+d[/math] per qualche [math]k > 0[/math]. La possibilità più piccola è [math]k=1[/math], quindi [math]b\geq 1c+d = c+d[/math].
Da questo risultato e da [math]a > b[/math] si ottiene [math]a > c+d[/math]. Se aggiungiamo le ultime due disuguaglianze appena derivate, otteniamo che [math](a+b) > 2(c+d)[/math].
In parole povere, dopo ogni due passi consecutivi la somma dei due numeri diminuisce a meno della metà della sua dimensione originale.
Ora guardate il primissimo passo dell'algoritmo. All'inizio abbiamo dei [math](a,b)[/math] con [math]a > b[/math]. Dopo il primissimo passo abbiamo [math](b,c)[/math] con [math]c=a\bmod b[/math], e chiaramente [math]b > c[/math]. Quindi, dopo il primo passo entrambi i numeri sono al massimo uguali al più piccolo dei due numeri in ingresso.
Mettendo insieme questi due risultati, possiamo concludere che il numero di iterazioni (chiamate ricorsive in altre implementazioni) è al massimo logaritmico nel più piccolo numero in ingresso. In altre parole, il numero di iterazioni è al massimo lineare nel numero di cifre del numero più piccolo in ingresso.
Per vedere che questa analisi è asintoticamente ottimale, prendiamo [math](a,b)=(F_{n+1},F_n)[/math] -- cioè due numeri di Fibonacci consecutivi.
Articoli simili
- L'algoritmo di Dijkstra è un algoritmo greedy o un algoritmo di programmazione dinamica?
- Potete dimostrare che il merge sort ha una complessità temporale [math]O(n \log n)[/math]?
- Cos'è la complessità del modello nell'apprendimento automatico?
- Quali sono i fattori che impediscono al gioco mobile di Apple di raggiungere la grafica e la complessità a livello di console nella storia?