Т (п) = Т (п-1) + 10/п

Question

То, что я сделал до сих пор является:

T(n-1) + 10/n 

T((n-1)-1) + 10/(n-1) + 10/n =    T(n-2) + 10/(n+1) + 10/n 

T((n-2)-1) + 10/(n+2) + 10/(n+1) + 10/n = T(n-3) + 10/(n+2) + 10/(n+1) + 10/n 

Предположим n-k = 1,

Итак ... Я теряюсь здесь,

T(n-k) + ?? 

Answer 1

хорошо, что я понимаю, это:

Т (п) = Т (п-1) + 10/п

Т (п-1) = Т (п-2) + 10/(п-1)

Т (п-2) = Т (п-3) + 10/(п-2)

Т (п) = Т (п-2) + 10/(N-1) + 10/п

Т (п) = Т (п-3) + 10/(п-2) + 10/(N-1) + 10/п

аналогично,

Т (п) = Т (п) + 10/(пк) + 10/(п + 1) + 10/(n-k + 2) + ......... + 10/п

для пк = 1:

Т (п) = Т (1) + 10 * (1/1 + 1/2 + 1/3 + ................ 1/n)

so, (1/1 + 1/2 + 1/3 + ... ............. 1/n) является гармонической прогрессией, ее сумма не может быть найдена вполне, но пропорциональна log (n).

так, T (n) имеет порядок log (n).

sum of harmonic progression:click here

Answer 2

Давайте предположим, что граничное условие T(1)=1, в противном случае рецидива не определена.

Вы можете написать рецидивы из:

T(n) = T(n-1) + 10/n = T(n-2) + 10/(n-1) + 10/n 
    = ... 
    = 10 * (1/n + 1/(n-1) + ... + 1) 
    = 10 * H_n, 

где H_n является п-й Harmonic number. Очень хорошо известно, что H_n=Theta(log n). (Вы можете это доказать, отметив это log n = integral from 1 to n 1/n dn и что сумма 1 + 1/2 + ... + 1/n ограничена сверху этим интегралом.)

Отсюда T(n) = Theta(log n).