Асимптотическая верхняя граница

Привет, я решил вопрос с методом дерева рекурсии. Затем я достиг приведенного ниже уравнения. n ∑ 3^(i-1)(n - (i - 1)) i=1

Мне нужно найти асимптотическую верхнюю границу для этого уравнения. Любая помощь будет оценена.


algorithm time-complexity asymptotic-complexity upperbound
person trial    schedule 22.03.2017    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Wolfram Alpha - отличный инструмент для этого: https://www.wolframalpha.com/input/?i=sum(3%5E(i-1)(n+-+i+%2B+1)+for+i+%3D+1..n)

Этот инструмент упрощает сумму до: (-2n + 3^(n+1) - 3)/4.

С точки зрения большого O, это O (3 ^ n).

person Paul Hankin    schedule 22.03.2017
comment
Пол Ханкин: Как вы думаете, это O (3 ^ n) правильно? Не смог проверить методом подстановки. - person trial; 22.03.2017
comment
Если да, то какой член нижнего порядка для 3 ^ n? - person trial; 22.03.2017
comment
Простите, я не понимаю, о чем вы спрашиваете. Я не знаю, что такое метод замены, и что вы подразумеваете под термином более низкого порядка. - person Paul Hankin; 23.03.2017
comment
(3 ^ (n + 1) -3-2n) / 4, безусловно, O (3 ^ n), поскольку сразу становится меньше 3/4 * 3 ^ n, просто отбрасывая отрицательные члены. - person Paul Hankin; 23.03.2017

arrow_upward
0
arrow_downward

Пусть u (n) = 3 ^ (n-1) + 2 * 3 ^ (n-2) + ... + n, тогда
u (n + 1) = (3 ^ n + 3 ^ (n -1) + ... + 1) + 3 ^ (n-1) + 2 * 3 ^ (n-2) + ... + n = (3 ^ (n + 1) -1) / 2 + u (п) = 3 * и (п) + п + 1 и (п) = (3 ^ (п + 1) - 2n - 3) / 4.

person Abstraction    schedule 22.03.2017