Решить повторение T (n) = T (6n/5) + 1

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


recurrence algorithm master-theorem asymptotic-complexity
person Kioko Key    schedule 13.05.2018    source источник
comment
Кстати, рассмотрите возможность публикации на CS, поскольку вы не спрашиваете о конкретном коде: meta.stackexchange.com/questions/165519/   -  person Mörre    schedule 13.05.2018
comment
@Mörre Спасибо за предложение, я буду иметь это в виду.   -  person Kioko Key    schedule 13.05.2018
comment
@hnefatl Да :) спасибо за объяснение :)   -  person Kioko Key    schedule 13.05.2018

Ответы (1)


arrow_upward
1
arrow_downward

Учитывая только это рекуррентное соотношение (и отсутствие дополнительной информации, такой как 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).

person hnefatl    schedule 13.05.2018
comment
О, я заметил это, но поскольку профессор сказал решить рекуррентность, я предположил, что есть какая-то граница._. Спасибо за вашу помощь! - person Kioko Key; 13.05.2018