Временная сложность алгоритма Евклида

В этой статье мы обсудим временную сложность алгоритма Евклида, которая составляет O (log (min (a, b)) и достигается.

Алгоритм Евклида : это эффективный метод нахождения НОД (наибольшего общего делителя) двух целых чисел. Временная сложность этого алгоритма O(log(min(a, b)) , Рекурсивно это может быть выражено как:

gcd(a, b) = gcd(b, a%b), 
where, a and b are two integers.

Доказательство. Предположим, что a и b — два целых числа, такие что a > b , тогда в соответствии с алгоритмом Евклида:

gcd(a, b) = gcd(b, a%b)

Используйте приведенную выше формулу несколько раз, пока не достигнете шага, на котором b равно 0 . На этом шаге результатом будет НОД двух целых чисел , который будет равен a . Таким образом, после тщательного наблюдения можно сказать, что временная сложность этого алгоритма будет пропорциональна количеству шагов, необходимых для уменьшения b до 0 .

Предположим, что количество шагов, необходимых для уменьшения b до 0 с помощью этого алгоритма, равно N .

gcd(a, b) ------> N steps

Теперь, если алгоритм Евклида для двух чисел a и b сокращается за N шагов, тогда a должно быть не менее f _{(N + 2)} , а b должно быть не менее f _{(N + 1)} .

gcd(a, b) ——> N steps
Then, a >= f_{(N + 2)} and b >= f_{(N + 1)}
where, f_N is the N^th term in the Fibonacci series(0, 1, 1, 2, 3, …) and N >= 0.

Чтобы доказать приведенное выше утверждение, используя принцип математической индукции (PMI):

• Базовый вариант:
  • Предположим, что a = 2 и b = 1 . Тогда gcd(2, 1) уменьшится до gcd(1, 0) за 1 шаг, т. е. N = 1 .
  • Это означает, что 2 должно быть как минимум f ₃ и 1 должно быть как минимум f ₂ и f ₃ = 2 и f ₂ = 1 .
  • Это означает, что a по крайней мере f _{(N + 2)} и b по крайней мере f _{(N + 1)} .
  • Можно сделать вывод, что утверждение верно для базового случая.
    
• Индуктивный шаг: Предположим, что утверждение верно для (N – 1) ^-го шага . Итак, ниже приведены шаги, чтобы доказать это для N ^-го шага :

gcd(b, a%b) ——> (N – 1) steps
Then,  
b >= f_{(N – 1 + 2)} i.e., b >= f_{(N + 1)}
a%b >= f_{(N – 1 + 1)} i.e., a%b >= f_N

• Это также может быть записано как:

a = floor(a/b)*b + a%b

floor(a/b)*b означает наибольшее число, ближайшее к b.

пример - пол (5/2) * 2 = 4. Если мы затем добавим 5% 2 = 1, мы получим (= 5) обратно.

• Теперь (a/b) всегда будет больше 1 (так как a >= b). Итак, из приведенного выше результата следует, что:

a >= b + (a%b)
This implies, a >= f_{(N + 1)} + f_N

• Известно, что каждое число является суммой двух предыдущих членов ряда Фибоначчи. Отсюда следует, что f _{(N + 2)} = f _{(N + 1)} + f _N .

a >= f_{(N + 2)} and b >= f_{(N + 1)}

• Поскольку приведенное выше утверждение справедливо и для индукционного шага. Это доказывает правильность утверждения.
• Прежде чем продолжить, посмотрите на формулу Бине :

Формула Бине:

f_N = {((1 + √5)/2)^N – ((1 – √5)/2)^N}/√5
          or
f_N ≈ ∅^N

• где ∅ известно как золотое сечение (∅≈1,618) , а f _N — N-е число Фибоначчи.
• Теперь уже установлено, что временная сложность будет пропорциональна N, т. е. количеству шагов, необходимых для уменьшения b до 0 .
• Итак, для доказательства временной сложности известно, что:

f_N ≈ ∅^N
N ≈ log_∅(f_N)

Теперь из приведенного выше утверждения доказано, что, используя принцип математической индукции, можно сказать, что если алгоритм Евклида для двух чисел a и b сокращается за N шагов , то a должно быть не менее f _{(N + 2)} и b должно быть не менее f _{(N + 1)} .

Из двух приведенных выше результатов можно сделать вывод, что:

=> f_N+1 ≈ min(a, b)
=> N+1 ≈ log_∅min(a, b)

=> O(N) = O(N+1) =  log(min(a, b))