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

Question

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

1.gcd (0, v) = V, потому что все делит нулю, а v является наибольшим числом, которое делит V Аналогично, НОД (и, 0) = и. 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 не является общим делителем. Аналогично, если и нечетно и v четно, то gcd (u, v) = gcd (u, v/2).

4. Если u и v оба нечетные, а u ≥ v, то gcd (u, v) = gcd ((u - v)/2, v). Если оба нечетны и u < v, то gcd (u, v) = gcd ((v - u)/2, u). Это комбинации одного шага простого евклидова алгоритма, который использует вычитание на каждом шаге и применение вышеописанного шага 3. Деление на 2 приводит к целому числу, поскольку разность двух нечетных чисел является четной. [3]

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

Answer 1

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