асимптотической сложности Т (п) = Т (п-1) + 1/п

Question

Существует алгоритм, который имеет временную сложность

T(n)=T(n-1)+1/n if n>1 
     =1   otherwise 

Я решения для его асимптотической сложности, и получить заказ как ' n ', но ответом является «log n». Правильно ли это? Если это log n, то почему?

Answer 1

Легко видеть (или доказано формально с индукцией), что T (n) является суммой 1/k для значений k от 1 до n. Это n th harmonic number, H _n = 1 + 1/2 + 1/3 + ... + 1/n.

Асимптотически, гармонические числа растут порядка log (n). Это связано с тем, что сумма близка по величине к интегралу от 1/x от 1 до n, что равно натуральному логарифму n. Действительно, H _n = ln (n) + γ + O (1/n), где γ - постоянная. Отсюда легко показать, что T (n) = Θ (log (n)).

Answer 2

Для получения более подробной информации:

С H(N) = 1 + 1/2 + 1/3 + ... + 1/N

функция x :-> 1/x убывающая функция так:

Подводим из 1 to N левой части и правой части мы суммируем от 2 to N и добавим 1, получаем:

Затем мы вычисляем левую и правую части: ln(N+1) <= H(N) <= 1 + ln(N)

это подразумевает H(N)/ln(N) -> 1 поэтому H(N)=Θ(log(N))

(от http://fr.wikipedia.org/wiki/S%C3%A9rie_harmonique#.C3.89quivalent_de_Hn)