323
ность алгоритма полностью следует из предположения B.6.
Что касается длительно-
сти его работы, то далее мы покажем, что на входе (a, b) алгоритм делает менее 2 • «b»
рекурсивных вызовов. Поскольку проверка,
делит ли b a и вычисление
АЛГОРИТМ B.7
Алгоритм Эвклида для наибольшего общего делителя
Вход:
Целые числа a, b при a ≥ b > 0
Выход: Наибольший общий делитель для a и b, если b делит a возвращает b в
противном случае, возвращает GCD(b, [a mod b])
o[admb] могут быть сделаны в течение полиномиального времени в «a» и «b»,
это означает что весь алгоритм действует в течение полиномиального времени.
Достарыңызбен бөлісу: