Решить рецидив T (n) = T (6n / 5) + 1

Question

Итак, я готовлюсь к экзамену по Алгоритмам и не знаю, как решить эту проблему T(n) = T(6n/5) + 1, поскольку b = 5/6 < 1 и основная теорема не могут быть применены.Я надеюсь, что кто-то может дать мне подсказку о том, как решить эту проблему.:)

Answer 1

Учитывая только это рекуррентное отношение (и никакой дополнительной информации, такой как T(x) = 1, когда x > 100), алгоритм со сложностью по времени, как описано в этом отношении, никогда не завершится, так как объем работы увеличивается при каждом вызове.

T(n) = T(6n/5) + 1
     = T(36n/25) + 2
     = T(216n/125) + 3
     = ...

Вы можете видеть, что объем работы увеличивается с каждым звонком, и что он не будет иметь ограничения в отношении того, насколько он увеличивается.В результате, нет ограничений на временную сложность функции.

---

Мы можем даже (неофициально) утверждать, что такой алгоритм не может существовать - увеличивая размерввод 1.2 раз, каждый вызов требует как минимум 0.2n работы, что явно O(n) - но фактическая стоимость на каждом шаге, как утверждается, составляет 1, O(1), поэтому это невозможно для алгоритма, описываемогоэто точное повторение, чтобы существовать (но хорошо для алгоритмов с повторением, например. T(n) = T(6n/5) + n).