Временная сложность алгоритма ниже gcd

Question

Мне было трудно вычислить временную сложность двоичного алгоритма GCD, также известного как алгоритм Стейна, для которого задано значение O(n^2), где n - это число бит в большем из двух чисел. Разве это не должно быть O(n)? Алгоритм как ниже:

1.gcd (0, v) = v, потому что все делит ноль, а v - наибольшее число, которое делит v. Аналогично, gcd(u, 0) = u. gcd(0, 0) обычно не определяется, но удобно установить gcd (0, 0) = 0.

2. Если u и v оба четные, то gcd(u, v) = 2·gcd(u/2, v/2), потому что 2 - общий делитель.

3. Если u четное и v нечетное, то gcd(u, v) = gcd(u/2, v), потому что 2 не является общим делителем. Аналогично, если u нечетно, а v четно, то gcd (u, v) = gcd (u, v / 2).

4. Если u и v нечетны и u ≥ v, то gcd(u, v) = gcd((u - v)/2, v). Если оба нечетны и u

5. Повторите шаги 2–4, пока u = v, или (еще один шаг), пока u = 0. В любом случае GCD составляет 2 кВ, где k - это число общих множителей 2, найденных на шаге 2.

Answer 1

Том 2 Кнута имеет очень сложный анализ, который, кажется, подтверждает очевидное предположение, что число шагов является наихудшим в линейном отношении числа входных битов. Однако для очень больших n каждое вычитание должно начисляться как O(n) само по себе (например, из-за арифметики с множественной точностью), и в этом случае общий счет составляет O(n^2)