Questa risposta si basa sulle risposte all'interno della domanda SO La complessità dell'algoritmo con l'input è di dimensioni fisse
La prima cosa da fare è riscrivere questo come pseudo codice con i numeri di riga in modo che possiamo parlare di loop specifici.
1) def GCD(x, y):
2) while x != y:
3) if x < y:
4) x, y = y - x, x
5) else:
6) x, y = x - y, x
7) return x
Questa è una forma della chiamata basata sulla sottrazione dell ' algoritmo euclideo piuttosto che della forma / modulo modulo ricorsivo (che la domanda allude a). Quello per completezza è (numerazione diversa in modo che i due non siano confusi):
a) def GCD(x, y):
b) if y = 0
c) return x
d) else
e) return GCD(y, x % y)
Per il metodo sottrattivo, il caso peggiore è dove i due numeri sono coprime che ha la proprietà di GCD (x , y) = 1. Un esempio di interi coprimi è 15 e 8.
Nessuna delle istruzioni delle righe 2 .. 6 è diversa da O (1). Non ci sono loop multipli. La domanda è una delle cose che conta il ciclo.
Per ogni chiamata gcd(n,1) , questo richiederà n-1 loops. Ogni passo, il percorso sarà 1, 2, 5, 6. La linea 6 diminuirà di 1, fino a n = 1. Come detto, questo è n-1 cicli. Poiché questo è il caso peggiore, uno ha gcd (n, 1) = O (n).
Quindi, per GCD (15,1), ci sono 14 loop. Questa è anche una funzione molto noiosa che ha solo una variabile. Cosa succede se lo rendiamo interessante facendo, come richiesto, GCD (x, y) dove sono coprimi?
Come detto sopra, GCD (15,8) = 1. Quanti loop fa allora?
GCD(15,8)
x = 15, y = 8
x, y = 15 - 8, 8
x = 7, y = 8
x, y = 8 - 7, 8
x = 1, y = 8
(7 more steps)
La cosa importante da notare qui è che si tratta di più passi di 8. Il caso peggiore asintotico è legato al massimo dei due parametri. Il tempo di esecuzione effettivo può avere altri fattori mescolati - GCD (15,2) è due volte più veloce di GCD (15,1), ma questo è un fattore costante che si mantiene a O (n).
Il caso peggiore asintotico per questa forma di GCD (x, y) è O (max (x, y)).
Ma aspetta, tu dici ... l'altra forma di GCD, quella ricorsiva ... GCD (15,1) è il caso migliore, ottieni GCD (1, 15% 1 = 0) dopo un passo.
Quest'area ha un posto speciale nella storia del calcolo. Nel 1844 fu pubblicata una prova di Gabriel Lamé sul tempo di esecuzione dell'algoritmo euclideo. Questo segna l'inizio della teoria della complessità computazionale. Per questo, il caso peggiore sono coppie di numeri di Fibonacci e funziona in non più di 5k passi dove k = log 10 (min (x, y)). Questo è noto come Teorema di Lamé . In realtà, il 5 è una semplificazione - il numero effettivo è ln (10) / lnφ ≈ 4.785 dove φ è la sezione aurea . E sì, la matematica per questo mi sta venendo in testa.
Qualche lettura sul Teorema di Lamé:
Leggi quello di Math.SE - non c'è modo di ottenere tutto questo qui per spiegare quella parte.
Basti dire che questa forma di GCD (x, y) è O (log (min (x, y)))
Di nota speciale, c'è anche una forma binaria di GCD che funziona con manipolazioni di bit. Leggilo su Algoritmo GCD binario su wikipedia. Funziona potenzialmente un po 'più veloce sui computer perché le operazioni sono tutte bit a bit che si eseguono più rapidamente della sottrazione o della divisione. Questo è O (n 2 ) dove n è il numero di bit nel più grande dei due numeri - si noti la variazione nella definizione di n tra questa e le forme precedenti dell'analisi. Nonostante l'O più grande, è tra il 15% e il 60% più veloce (Knuth 1998 - TAOCP vol 2, 3a edizione) a seconda dell'architettura a causa delle istruzioni più semplici (se ho letto bene).