Вычислить временную сложность рекуррентного уравнения

У меня проблемы с вычислением сложности следующего рекуррентного уравнения. введите здесь описание изображения

Мне довольно сложно ее решить. Может ли кто-нибудь помочь мне решить эту проблему? Заранее спасибо.


recurrence algorithm time-complexity big-o
person guapi    schedule 13.10.2020    source источник
comment
Не могли бы вы подтвердить, является ли T(n) сложностью, или вы ищете сложность алгоритма, который будет вычислять T(n)?   -  person Stef    schedule 13.10.2020
comment
@Stef T(n) — это рекуррентное уравнение временной сложности алгоритма. Например, рекуррентное уравнение временной сложности сортировки слиянием равно T(n) = 2T(n/2) + n, тогда мы можем получить T(n) = O(nlogn) .   -  person guapi    schedule 14.10.2020

Ответы (1)


arrow_upward
3
arrow_downward

Это то же самое повторение для средней сложности случая быстрой сортировки с решением

T(n)=O(n log n)

здесь

person Hikmat Farhat    schedule 13.10.2020