Вычислительная сложность алгоритма
Вычислительная сложность алгоритма Евклида изучена полностью.[17] Эта сложность может быть описана произведением количества шагов деления, требуемых алгоритмом, на вычислительную сложность одного шага. Первый известный анализ алгоритма Евклида был предложен Рейнаудом в 1811.[18] Он показал, что число шагов алгоритма для пары чисел (u, v) ограничено v. Позже он улучшил оценку до v/2 + 2. Эмиль Леже, в 1837 году, изучил наихудший случай, когда для вычисления НОД подаются последовательные числа Фибоначчи.[19] Затем, в 1841 году, Пьер Джосеф Финк показал,[20] что количество шагов алгоритма не превышает 2 log2 v + 1. Следовательно алгоритм работает за полиномиальное время от размера меньшего из пары чисел (u, v).[19] Анализ Финка был уточнён Габриэлем Ламе в 1844 году.[21] Он показал, что количество шагов, необходимых для завершения алгоритма, не более чем в пять раз превышает h — количество цифр в десятичном представлении меньшего из пары чисел (u, v).[22][23] Когда НОД вычисляется для чисел, которые вписываются в одно машинное слово, каждый шаг алгоритма занимает постоянное время. В данном случае анализ Ламе предполагает, что вычислительная сложность оценивается как O(h). Однако в модели расчёта, подходящей для вычислений с числами больше одного машинного слова, оценка сложности вычисления одного остатка может быть O(h2).[24] В этом случае общее время для всех этапов алгоритма можно проанализировать с помощью телескопического ряда, показав что это также O(h2). Для ускорения алгоритма Евклида могут быть использованы современные алгоритмические методы, основанные на методе Шёнхаге — Штрассена для быстрого целочисленного умножения . Это приводит к квазиполиномиальному времени.[25] КОЛИЧЕСТВО ШАГОВ Число шагов для вычисления НОД двух натуральных чисел a и b обозначим как T(a, b). Если g — это наибольший общий делитель a и b, тогда a = mg и b = ng для двух взаимно простых чисел m и n. Тогда T(a, b) = T(m, n), что можно заметить, если разделить уравнения, полученные при вычислении НОД для пары (a, b), на g.[26] Используя тот же принцип, число шагов алгоритма остаётся неизменным, если a и b умножаются на общий множитель w, что эквивалентно равенству T(a, b) = T(wa, wb). Следовательно, количество шагов T может сильно различаться между соседними парами чисел, такими как (a, b) и (a, b+1), так как данная величина зависит от НОД. Рекурсивный характер алгоритма Евклида даёт следующее уравнение T(a, b) = 1 + T(b, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1, где T(x, 0) = 0 по предположению.[17]
Slaidy.com
