Wie ist die zeitliche Komplexität von gcd Θ (logn)?

Question

Ich war eine Zeitkomplexität Frage auf Interview Bit Lösung, wie im Bild unten gegeben.

Die Antwort gegeben ist Θ(theta)(logn) und ich bin nicht in der Lage zu begreifen, wie die logn Begriff hier in der Zeit Komplexität dieses Programms ankommen.

Kann jemand bitte erklären, wie die Antwort Theta von logn ist?

Answer 1

Dieser Algorithmus erzeugt eine fallende Folge von ganzzahligen (m, n) Paaren. Wir können versuchen zu beweisen, dass eine solche Sequenz schnell genug abklingt.

Angenommen, wir beginnen mit m_1 und n_1 mit m_1 < n_1.

wir n_1 % m_1 Bei jedem Schritt nehmen, die < m_1 ist, und m_2 = n_1 % m_1 und n_2 = m_1 rekursiv auf dem Paar wiederholen.

Jetzt sagen wir n_1 % m_1 = m_1 - p für einige wo 0 < p < m_1. Wir haben max(m_2, n_2) = m_1 - p.

Lassen Sie uns einen weiteren Schritt (m_2, n_2) -> (m_3, n_3) nehmen, können wir leicht sehen, dass max(m_3, n_3) < p, aber es ist auch wahr, dass max(m_3, n_3) < m_1 - p als die Reihenfolge streng abnimmt.

So können wir max(m_3, n_3) < min(m_1 - p, p) schreiben, wo min(m_1 - p, p) = m_1/2. Dieses Ergebnis drückt die Tatsache aus, dass die Sequenz geometrisch abnimmt, damit der Algorithmus höchstens log_2(m_1) Schritte beenden in hat.

Answer 2

Theorem gegeben irgendein x, gcd (n, m), wo n < fib (x) ist rekursiv genannt gleich oder weniger als x mal.

Anmerkung: FIB (x) ist Fibonacci (x), wobei FIB (x) = FIB (x-1) + FIB (x-2)

Beweisen

Basis

jedes n = < FIB (1), gcd (n, m) gcd (1, m) nur einmal rekursiven

Inductive Schritt

annehmen, der Satz für jede Zahl kleiner als x halten ist, was bedeutet:

calls(gcd(n, m)) <= x for every n <= fib(x) 

betrachten n, wobei n < = FIB (x + 1)

wenn m> FIB (x)

calls(gcd(n, m)) 
= calls(gcd(m, (n-m))) + 1 
= calls(gcd(n-m, m%(n-m))) + 2 because n - m <= fib(x-1) 
<= x - 1 + 2 
= x + 1 

wenn m = < FIB (x)

calls(gcd(n, m)) 
= calls(gcd(m, (n%m))) + 1 because m <= fib(x) 
<= x + 1 

Also gilt das Theorem auch für x + 1, als mathematische Induktion gilt das Theorem für jedes x.

Schlussfolgerung

gcd (n, m) ist, Θ (Rückwärts FIB), die Θ (logn) ist