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

Функции факториала требуется единственный аргумент: число, факториал от которого требуется вычислить. Анализ вычислительной сложности алгоритма обычно исследует зависимость времени выполнения программы как функции от размерности (size) задачи или числа входных значений (number of inputs). Поскольку в данном случае входное значение всего одно, такие расчеты могли бы показаться немного странными.

========83

Поэтому, алгоритмы с единственным входным параметром обычно оцениваются через число битов, необходимых для хранения входного значения, а не число входных значений. В некотором смысле, это и есть размер входа, так как столько бит требуется для того, чтобы записать входное значение. Тем не менее, это не очень наглядный способ представления этой задачи. Кроме того, теоретически компьютер мог бы записать входное значение N в log₂(N) бит, но в действительности вероятнее всего N занимает фиксированное число битов. Например, все числа формата long занимают 32 бита.

Поэтому в этой главе алгоритмы этого типа анализируются на основе значения входа, а не его размерности. Если вы хотите переписать результаты в терминах размерности входа, вы можете это сделать, воспользовавшись тем, что N=2^M, где М — число битов, необходимое для записи N. Если время выполнения алгоритма порядка O(N²) в терминах входного значения N, то оно составит порядка O((2^2M)²) = O(2^2*M) = O((2²)^M) = O(4^M) в терминах размерности входа M.

Функции порядка O(N) растут довольно медленно, поэтому можно ожидать от этого алгоритма хорошей производительности. Так оно и есть. Эта функция приводит к проблемам только при переполнении стека после множества рекурсивных вызовов, или когда значение N! становится слишком большим и не помещается в формат целого числа, вызывая ошибку переполнения.

Так как N! растет очень быстро, переполнение наступает раньше, если только стек не используется интенсивно для других целей. При использовании данных целого типа, переполнение наступает для 8!, поскольку 8! = 40.320, что больше, чем наибольшее целое число 32.767. Для того чтобы программа могла вычислять приближенные значения факториала больших чисел, можно изменить функцию, используя вместо целых чисел значения типа double. Тогда максимальное число, которое сможет вычислить алгоритм, будет равно 170! = 7,257E+306.

Программа Facto демонстрирует рекурсивную функцию факториала. Введите значение и нажмите на кнопку Go, чтобы вычислить его факториал.

Рекурсивное вычисление наибольшего общего делителя

Наибольшим общим делителем (greatest common divisor, GCD) двух чисел называется наибольшее целое, на которое делятся два числа без остатка. Например, наибольший общий делитель чисел 12 и 9 равен 3. Два числа называются взаимно простыми (relatively prime), если их наибольший общий делитель равен 1.

Математик Эйлер, живший в восемнадцатом веке, обнаружил интересный факт:

Если A нацело делится на B, то GCD(A, B) = A.

Иначе GCD(A, B) = GCD(B Mod A, A).

Этот факт можно использовать для быстрого вычисления наибольшего общего делителя. Например:

GCD(9, 12) = GCD(12 Mod 9, 9)

= GCD(3, 9)

= 3

========84

На каждом шаге числа становятся все меньше, так как 1<=B Mod A<A, если A не делится на B нацело. По мере уменьшения аргументов, в конце концов, A примет значение 1. Так как любое число делится на 1 нацело, на этом шаге рекурсия остановится. Таким образом, в какой то момент B разделится на A нацело, и работа процедуры завершится.

Открытие Эйлера закономерным образом приводит к рекурсивному алгоритму вычисления наибольшего общего делителя:

public Function GCD(A As Integer, B As Integer) As Integer

If B Mod A = 0 Then ' Делится ли B на A нацело?

GCD = A ' Да. Процедура завершена.

Else

GCD = GCD(B Mod A, A) ' Нет. Рекурсия.

End If

End Function