|
Даны два рекуррентных соотношения с параметром:
Попытка решения примера [1]: $%\eqalign{ & T(n) = T(n - 1) + {n^c} \cr & \,\,\,\,\,\,\,\,\,\,\, = T(n - 2) + {(n - 1)^c} + {n^c} \cr & \,\,\,\,\,\,\,\,\,\,\, = T(n - 3) + {(n - 2)^c} + {(n - 1)^c} + {n^c} \cr & \cdots \cr & \,\,\,\,\,\,\,\,\,\,\, = T(n - k) + \sum\limits_{i = 0}^{k - 1} {{{(n - i)}^c}} \cr} $% Подставляя базовый случай, находим $%n - k = 1 \Leftrightarrow n = k + 1 \Leftrightarrow k = n - 1$%. Проблеммы создает $%\sum\limits_{i = 0}^{k - 1} {{{(n - i)}^c}} = {n^c} + {(n - 1)^c} + \ldots + {(n - k + 1)^c}$%. Нужно как-то преобразовать $%T(n) = T(n - k) + \sum\limits_{i = 0}^{k - 1} {{{(n - i)}^c}} = 1 + \sum\limits_{i = 0}^{n - 2} {{{(n - i)}^c} \in {\rm O}(?)} $% и дать оценку сверху через большое O. Попытка решения примера [2]: $%\eqalign{ & T(n) = T(n - 1) + {c^{n - 1}} \cr & \,\,\,\,\,\,\,\,\,\,\, = T(n - 2) + {c^{n - 2}} + {c^{n - 1}} \cr & \,\,\,\,\,\,\,\,\,\,\, = T(n - 3) + {c^{n - 3}} + {c^{n - 2}} + {c^{n - 1}} \cr & \cdots \cr & \,\,\,\,\,\,\,\,\,\,\, = T(n - k) + \sum\limits_{i = 1}^k {{c^{n - i}}} = 1 + \sum\limits_{i = 1}^{n - 1} {{c^{n - i}}} \in {\rm O}(?) \cr} $% Алгоритм решения в этом примере тот же, что и в предыдущем. Опять все упирается в сумму, которую надо выразить через $%n$% и параметр $%c$%. Тогда можно будет написать выражение для большого О. Собственно, суть обоих примеров решить рекуррентное соотношение и на основе этого дать верхную оценку для большого О. задан 27 Сен '14 23:44 
night-raven |
|
Я так понимаю, речь идёт о суммах вида $%T_n=1^c+2^c+\cdots+n^c$%. Для натуральных значений $%c$% формулы суммирования хорошо известны. Для прочих значений можно указать приближённое значение, равное $%\frac{n^{c+1}}{c+1}$%. При больших $%n$% оно эквивалентно $%T_n$%, то есть предел отношения стремится к единице. Можно получить оценки в виде неравенств, из которых всё следует. Для этого рассмотрим функцию $%f(x)=x^c$%, заданную при $%x\ge0$%. Она монотонно возрастает. Геометрический смысл величины $%T_n$% -- площадь ступенчатой фигуры, состоящей из прямоугольников. Ясно, что такая фигура содержится в криволинейной трапеции в пределах от $%1$% до $%n+1$%, а также она покрывает криволинейную трапецию в пределах от $%0$% до $%n$%. Отсюда $$\frac{n^{c+1}}{c+1}=\int\limits_{0}^{n}x^c\,dx < T_n < \int\limits_{1}^{n+1}x^c\,dx=\frac{(n+1)^{c+1}}{c+1}-1,$$ откуда всё следует: после деления на приближённое значение, обе части в пределе будут равны единице. отвечен 28 Сен '14 0:05 
falcao Так чему будет равна сумма $%\sum\limits_{i = 0}^{n - 2} {{{(n - i)}^c}} $% при натуральных $%c$%?
(28 Сен '14 0:14)
night-raven
1
Точное значение равно самому этому выражению, и его никак не упростить. А асимптотическое значение равно $%n^{c+1}/(c+1)$%. Суммируем мы от 0 до n, или от 2 до n, или как-то ещё -- это роли не играет.
(28 Сен '14 0:28)
falcao
|
Решение для второй части я не рассматривал, так как там получается сумма членов геометрической прогрессии. Это формула из школьного учебника.
Да, вы правы, я не заметил, что вторая сумма выражается легко через геометрическую прогрессию...