Сумма одного ряда

[gkr]

Добрый день.

Подскажите, как вычислить формулу суммы ряда: $1^1 + 2^2 + 3^4 + 4^8 +...+ n^{2^{n-1}}$
Хотелось бы иметь общую формулу, но в итоге мне нужно проверить рост этой суммы на $O(n*log(n))$

PS Я так понимаю, для каждого ряда сумму нужно вычислять свою, однако, есть ли какие общие методы? Если нет, можете ли ткнуть меня в список часто используемых сумм (в алгоритмах программирования)?

С благодароностью, чайник.

[ИСН]

В Вашем ряду последний член настолько больше всех остальных, вместе взятых, что их всё равно что нет.

[EtCetera]

gkr

gkr в сообщении #261201 писал(а):

Подскажите, как вычислить формулу суммы ряда: $1^1 + 2^2 + 3^4 + 4^8 +...+ n^{2^{n-1}}$

Полагаю, Вы имели в виду просто формулу суммы (т.к. ряд в данном случае - расходящийся).

gkr в сообщении #261201 писал(а):

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

Для сумм используются следующие достаточно общие методы:
1. Если подобрана (неважно каким способом) формула суммы, то ее справедливость обычно нетрудно доказать с помощью метода математической индукции.
2. Аналог формулы Ньютона-Лейбница для интегралов: если общий член суммы представим в виде $a_n=F(n+1)-F(n)$, то сумма равна $S_n=F(n+1)-F(1)$.
3. Аналог формулы интегрирования по частям: преобразование Абеля (применимо всегда, но в большинстве случаев сводится к нахождению суммы еще более страшного вида).
Для рядов также можно использовать метод перехода от числового ряда к степенному. Т.е. $S=\sum\limits_{n=1}^{\infty} a_n$, $f(x)=\sum\limits_{n=1}^{\infty}a_n x^n$. Путем нескольких дифференцирований $f(x)$ получают дифференциальное уравнение $F(x,f, f', f'',...,f^{(k)})=0$, которое решают, получают явный вид $f(x)$ и находят $S=f(1)$.

[gkr]

EtCetera, благодарю за полный ответ. Действительно, ищу только формулу суммы.
Решил вот проверить порядок алгоритма HeapSort, а там количество обращений (с учетом n элементов массива) растет по такому закону.

PS Из описанных алгоритмов нахождения суммы применить не удалось. Подскажете?

[EtCetera]

gkr
Собственно, по данной конкретной сумме Вам отличную подсказку дал ИСН. Я лишь решил снабдить Вас информацией по поводу дополнительных вопросов, заданных Вами. Т.е. я и так понимал, что ни один из этих достаточно общих методов здесь не сработает.
Что касается HeapSort, мне кажется, Вы как-то неправильно считаете, т.к. достаточно очевидно, что $n\cdot\log n$ рядом с указанной Вами суммой

ИСН в сообщении #261207 писал(а):

всё равно что нет.

[gkr]

Виноват, нашел ошибку.
На самом деле траты HeapSort происходят по закону: $1+2*2+3*4+4*8+5*16 $, что не может быть больше $n+n*log_2(n)$, что и соответсвует $O(n*log(n))$.

А прежняя сумма (в моих постах ранее),кажется, явно больше $O(n^3)$, так как сумма $1^2+2^2+...+n^2$ уже имеет $O(n^3)$