Сложность алгоритма грубой силы GCD

Question

Для выполнения задачи: найдите gcd (a, b) для целых чисел a> b> 0

Рассмотрим алгоритм, который проверяет все числа до b и отслеживает максимальное число, которое делит a иб.Он будет использовать оператор% дважды за проверку (для a и b).Какова будет сложность этого алгоритма?

Я еще не посещал формальные курсы по КС по теории сложности (скоро), поэтому я просто ищу быстрый ответ.

Answer 1

Операция по модулю реализована аппаратно, и она псевдо O(1).Строго говоря, оно не является постоянным, но зависит от количества битов a и b.Однако даже тогда число битов одинаково для всех входных размеров, поэтому мы обычно игнорируем этот коэффициент.

Наихудшая сложность грубой силы GCD - просто O(n) (также O(a), O(b) или O(min(a,b)); они все одинаковые), и это происходит, когда GCD имеет значение 1, a или b.