Анализ времени выполнения программы

Чтобы проанализировать время выполнения этого алгоритма, необходимо определить, насколько быстро убывает переменная A. Так как функция останавливается, когда A доходит до значения 1, то скорость уменьшения A дает верхнюю границу оценки времени выполнения алгоритма. Оказывается, при каждом втором вызове функции GCD, параметр A уменьшается, по крайней мере, в 2 раза.

Допустим, A < B. Это условие всегда выполняется при первом вызове функции GCD. Если B Mod A <= A/2, то при следующем вызове функции GCD первый параметр уменьшится, по крайней мере, в 2 раза, и доказательство закончено.

Предположим обратное. Допустим, B Mod A > A / 2. Первым рекурсивным вызовом функции GCD будет GCD(B Mod A, A).

Подстановка в функцию значения B Mod A и A вместо A и B дает следующий рекурсивный вызов GCD(B Mod A, A).

Но мы предположили, что B Mod A > A / 2. Тогда B Mod A разделится на A только один раз, с остатком A – (B Mod A). Так как B Mod A больше, чем A / 2, то A – (B Mod A) должно быть меньше, чем A / 2. Значит, первый параметр второго рекурсивного вызова функции GCD меньше, чем A / 2, что и требовалось доказать.

Предположим теперь, что N — это исходное значение параметра A. После двух вызовов функции GCD, значение параметра A должно уменьшится, по крайней мере, до N / 2. После четырех вызовов, это значение будет не больше, чем (N / 2) / 2 = N / 4. После шести вызовов, значение не будет превосходить (N / 4) / 2 = N / 8. В общем случае, после 2 * K вызовов функции GCD, значение параметра A будет не больше, чем N / 2^K.

Поскольку алгоритм должен остановиться, когда значение параметра A дойдет до 1, он может продолжать работу только до тех, пока не выполняется равенство N/2^K=1. Это происходит, когда N=2^K или когда K=log₂(N). Так как алгоритм выполняется за 2*K шагов это означает, что алгоритм остановится не более, чем через 2*log₂(N) шагов. С точностью до постоянного множителя, это означает, что алгоритм выполняется за время порядка O(log(N)).

=======85

Этот алгоритм — один из множества рекурсивных алгоритмов, которые выполняются за время порядка O(log(N)). При выполнении фиксированного числа шагов, в данном случае 2, размер задачи уменьшается вдвое. В общем случае, если размер задачи уменьшается, по меньшей мере, в D раз после каждых S шагов, то задача потребует S*log_D(N) шагов.

Поскольку при оценке по порядку величины можно игнорировать постоянные множители и основания логарифмов, то любой алгоритм, который выполняется за время S*log_D(N), будет алгоритмом порядка O(log(N)). Это не обязательно означает, что этими постоянными можно полностью пренебречь при реализации алгоритма. Алгоритм, который уменьшает размер задачи при каждом шаге в 10 раз, вероятно, будет быстрее, чем алгоритм, который уменьшает размер задачи вдвое через каждые 5 шагов. Тем не менее, оба эти алгоритма имеют время выполнения порядка O(log(N)).

Алгоритмы порядка O(log(N)) обычно выполняются очень быстро, и алгоритм нахождения наибольшего общего делителя не является исключением из этого правила. Например, чтобы найти, что наибольший общий делитель чисел 1.736.751.235 и 2.135.723.523 равен 71, функция вызывается всего 17 раз. Фактически, алгоритм практически мгновенно вычисляет значения, не превышающие максимального значения числа в формате long — 2.147.483.647. Функция Visual Basic Mod не может оперировать значениями, большими этого, поэтому это практический предел для данной реализации алгоритма.

Программа GCD использует этот алгоритм для рекурсивного вычисления наибольшего общего делителя. Введите значения для A и B, затем нажмите на кнопку Go, и программа вычислит наибольший общий делитель этих двух чисел.