Разработка алгоритма с постоянным временем для функции

Question

Этот вопрос только что у меня над головой:

Функция G(m) определяется следующим образом:

а) Если m <= 100, то G(m) = G(G(m + 11))

б) если m > 100, то G(m) = m - 10

Согласно вышеупомянутому вопросу, как мне разработать алгоритм с постоянным временем, который вычисляет G(m)?

Answer 1

Часть (b), очевидно, может быть вычислена за постоянное время, предполагая, m помещается в целочисленную переменную.

Хитрая часть, которую проблема требует доказать, состоит в том, что (а) часть постоянна. Тогда O(1) время следует Это можно сделать с помощью математической индукции или другим способом.

Индуктивное доказательство следует.

Сначала заметьте, что G(101) равен 101 - 10 = 91 по определению.

За 90 <= n <= 100 он считает, что G(n) = G(G(n + 11)), где n + 11 > 100, Следовательно G(n) это равно G(n + 11 - 10) = G(n+1), что составляет 91.

Отсюда и десять уравнений G(91 - 1) = 91, G(91 - (1 - 1)) = 91,..., G(91 - (1 - 10)) = 91 все верно. Это основа для общей индукции.

Шаг индукции: предположим, что G(91 - i) = 91, G(91 - (i - 1)) = 91,..., G(91 - (i - 10)) = 91 верно для всех чисел i от 1 до определенной границы.

затем G(91 - (i + 1)) = G(G(91 - i - 1 + 11)) = G(G(91 - (i - 10))), Из базового шага мы знаем, что G(91 - (i - 10)) = 91, Подставив это в уравнение выше, мы получим G(91)который также уже известен как 91. Из этого следует, что предположение верно для i+1 также.

Как следствие, G(91 - n) равен 91 для всех n >= 1, Индукция доказана.

Пример алгоритма постоянного времени для вычислений G в Python:

def G(m):
   if m > 100:
      return m - 10
   else:
      return 91