Даны два рекуррентных соотношения с параметром:

  1. $%T(n) = T(n - 1) + {n^c}$%, где $%c \geqslant 1$% некая константа и $%T(1) = 1$%.
  2. $%T(n) = T(n - 1) + {c^{n - 1}}$%, где $%c > 1$% некая константа и $%T(1) = 1$%.

Попытка решения примера [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

изменен 28 Сен '14 11:17

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

1

Решение для второй части я не рассматривал, так как там получается сумма членов геометрической прогрессии. Это формула из школьного учебника.

(28 Сен '14 0:06) falcao

Да, вы правы, я не заметил, что вторая сумма выражается легко через геометрическую прогрессию...

(28 Сен '14 0:16) night-raven
10|600 символов нужно символов осталось
1

Я так понимаю, речь идёт о суммах вида $%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

Так чему будет равна сумма $%\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
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×76
×49

задан
27 Сен '14 23:44

показан
895 раз

обновлен
28 Сен '14 0:28

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru