Разница между грубой силой и евклидовыми алгоритмами для поиска GCD

Question

Почему последовательный алгоритм целочисленной проверки для поиска GCD считается грубой силой, но алгоритм Евклида нет? Я просто смущен. Это потому, что мы проверяем один за другим?

Answer 1

Поиски грубой силы предполагают попытку любой (разумной) возможности. Алгоритм Евклида проверяет очень малое подмножество этих возможностей.

Answer 2

Алгоритмы Brute-force используют каждое возможное решение, которое можно попробовать, посмотреть, какой из них подходит, и вернуть его результаты в качестве ответа. Например, алгоритм GCD с грубой силой начнется с меньшего из двух чисел и продолжит работу до 1, изучая каждую возможность, один за другим, по пути вниз.

Напротив, алгоритм Евклида не идет один за другим: он совершает прыжки, иногда довольно значительные. Более того, он не проверяет каждое возможное число как решение проблемы GCD на каждом шаге: его конечное условие довольно отличается от типичного решения грубой силы, которое заключается в проверке того, является ли текущий кандидат решением проблемы, и остановитесь, когда ответ «да». Евклидова алгоритм проверяет другое условие, а именно b != 0, чтобы решить, продолжать или нет.

Эти два различия (большие шаги и другое условие остановки) делают алгоритм Евклида отличным от алгоритмов грубой силы.