Я надеюсь, что вернусь к этой проблеме правильно. Он просит, чтобы решить повторения:Решая рекуррентность для T (n-1) + sqrt (n)
T(n) = T(n-1) + sqrt(n)
До сих пор я исследовал и был в состоянии добраться до этой точки:
T(n) = T(n-2) + (n-1) + sqrt(n) T(n) = T(n-3) + (n-2) + (n-1) + sqrt(n) T(n) = T(0) + 1 + 2 + ... + (n-2) + (n-1) + sqrt(n)
У меня возникли проблемы с пониманием того, что картина может быть для решения для 1 + 2 + ... + sqrt (n)
Вторая строка уже неверна.
Если Т (п) = Т (п - 1) + SQRT (п), то Т (п - 1) = Т (п - 2) + SQRT (п - 1), поэтому
Т (n) = T (n - 2) + sqrt (n - 1) + sqrt (n)
T (n) = T (n - 3) + sqrt (n - 2) + sqrt (n - 1)) + SQRT (п)
Т (п) = Т (п - 4) + SQRT (п - 3) + SQRT (п - 2) + SQRT (п - 1) + SQRT (п)
и так далее.
Сумма квадратных корней от 1 до n примерно такая же, как интеграл от sqrt (x) от 1 до n.
Вы начинаете с разворачивания рекурсии, и вы должны получить сумму квадратных корней. Сумма квадратных корней является generalized harmonic number и ваш один может быть аппроксимирована:
Это математический вопрос, а не программирования вопрос. Попробуйте http; // math.stackexchange.com/ Не забывайте упоминать, что вы получили помощь в Интернете, когда включаете свое задание, чтобы не нарушать академическую политику честности вашей школы. –