Меня попросили проанализировать асимптотическую временную сложность следующей функции рекурсии:
for-all k ≥ 1:
T(n) = n + T(n/2) + T(n/4) + T(n/8) + .... + T(n/2^k)
Мне удалось доказать, что:T(n) = O(n⋅log n) и T(n) = Ω(n),
но я ищу более тесную границу (Большое тета).
Прежде всего:
я понимаю "для всех k >= 1" следующим образом: от k = 1 до k = m, где 2m-1 ≤ n ≤ 2m.
Таким образом, в основном выполняется m = log₂(n).
Посмотрите на мой расчет:
T(n) = n + Σk=1,...,m T(n/2k)
= n + T(n/2) + Σk=2,...,m T(n/2k)
= n + n/2 + 2⋅Σk=2,...,m T(n/2k)
= ...
= n + Σk=1,...,m k⋅n/2k
= n + n⋅Σk=1,...,m k/2k
= n + n⋅(2 - 2-mm - 21-m)
≤ n + 2⋅n
= 3n
So T(n) is in Θ(n).
Примечание:
Вы также можете аппроксимировать Σk=1,...,m k/2k интегралом s(m) = ∫1m k/2k dk.
И здесь также выполняется limm → ∞s(m) = 2.
Tбесконечно — это правильно? - person Ordous schedule 12.11.2014T(n/2^k). - person user111893 schedule 12.11.2014kне ограничено, как вы сами написали: для всех k ›= 1 - person Ordous schedule 12.11.2014n*log(n)для k->inf,2n-1для k = 1), однако я не могу найти ничего для промежуточных сумм. Wolfram и Matlab тоже ничего не дают. Судя по результатам, которые мне удалось получить, он ни линейный, ни логлинейный. Возможно, вам больше повезет с Mathematics.SE — этот вопрос на самом деле не о программировании. - person Ordous schedule 12.11.2014