Рекуррентное соотношение

[capt]

Покажите, что решение этого $T(n) = 2T(\lfloor n/2 \rfloor) +n$ рекуррентного соотношения не превосходит $\Omega({n\lg n})$. Здесь имеется в виду $\lg{n} = \log_2 n$.

Цель заключается в том, что при подходящем выборе $c > 0$ будет выполняться $T(n) \leqslant cn \lg n $ (предположение индукции). Предположим справедливость при любом положительном $m < n$, а в частности для $m = \lfloor n/2 \rfloor$:

$$\begin{align}T(n) &\geqslant 2c\lfloor n/2 \rfloor \lg (\lfloor n/2 \rfloor) + n \\ & > 2c(n/2 - 1) \lg (n/2 - 1) + n\\ & = c(n - 2) \lg (n-2) + n - cn + 2c\\ & \geqslant cn \lg n \end{align}$$

Не получается доказать последнюю строчку. Хотя, следуя тому, что я написал, еще не факт, что последняя строчка будет меньше или равна предыдущей.
Подскажите, пожалуйста, что тут можно сделать, а то я застрял

[DeBill]

capt в сообщении #1409186 писал(а):

еще не факт, что последняя строчка будет больше или равна предыдущей.

Но для Вашей цепочки выкладок надо то противоположное (а оно - верно, если только ЦЭ достаточно мало)....
Однако: таким образом Вы докажите, что $T(n)$ НЕ МЕНЬШЕ чем то-то-то. А Вам то надо было - НЕ БОЛЬШЕ!
Так что все оценки надо проводить в другую сторону (ну, и для пущей строгости добавить, что док-во идет по индукции, предположение индукции указать, и т.п.)

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);


Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

-- 08.08.2019, 00:10 --

capt
Оно у нас \par не понимает. Сделайте иначе, через align или наподобие того. Функции типа логарифм - не забывайте слэш впереди.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[capt]

DeBill
Я по случайности не так написал, уже исправил.

[capt]

Решил сменить гипотезу индукции на $T(n) \geqslant c(n + d) \lg (n + d)$. Пусть неравенство выполняется при любом $m < n$, в частности для $m = \lfloor n/2 \rfloor$. Тогда $T(\lfloor n/2 \rfloor) \geqslant c (\lfloor n/2 \rfloor + d) \lg (\lfloor n/2 \rfloor + d)$.
Подставим все в реккурентное соотношение:

$$\begin{align} T(n) & \geqslant 2c (\lfloor n/2 \rfloor + d) \lg (\lfloor n/2 \rfloor + d) + n\\ & > 2c (n/2 + d - 1) \lg (n/2 + d - 1) + n\\ & = c (n + d + d - 2) \lg (n + d + d - 2) - c (n + 2d - 2) + n\\ & = c (n + d + d - 2) \lg (n + d + d - 2) + n - cn + 2c - 2cd\\ & \geqslant c(n + d) \lg (n + d) \end{align}$$

Чтобы это неравенство выполнялось, к примеру при $d = 2$, цэ должно зависеть от $n$.
В общем так у меня тоже не получается. Жду спасательный круг

-- 08.08.2019, 01:54 --

capt в сообщении #1409186 писал(а):

Цель заключается в том, что при подходящем выборе $c > 0$ будет выполняться $T(n) \leqslant cn \lg n $ (предположение индукции).

Я тут имел в виду $T(n) \geqslant cn \lg n$

[DeBill]

capt в сообщении #1409211 писал(а):

Последний раз редактировалось capt
08.08.2019, 02:54, всего редактировалось 2 раз(а).


Решил сменить гипотезу индукции

Ну, от этого стало только хуже.
Итак , Вы упорно пытаетесь доказывать, противоположное обещанному

capt в сообщении #1409186 писал(а):

не превосходит $\Omega({n\lg n})$

(для справки - "не превосходит" - означает "меньше").
Ну да ладно, это - тоже верно, и, доказав это, можно аналогично доказывать и нужное.
Все проблемы у Вас - с матаном (который компьютерщики не любят, и игнорируют).
Конкретно (к первому посту): разделите желаемое неравенство на ЭН, и сосчитайте проедел (при $n \to \infty$): Вы обнаружите, что получилось верное неравенство (ну, если $c < \frac{1}{2}$, например). Коль некое неравенство (строгое) в пределе верно, то оно верно и при всех $n$, достаточно больших (больших некоторого $N$). Ну вот теперь индукция и пошла (только еще надо - базу индукции проверить, и в качестве такой базы взять выполнение неравенства про всех $n<N$). А выполнение базовых предположений - обеспечить за счет подходящего уменьшения $c$...

[SiberianSemion]

capt, насколько я знаю, этот значок $\Omega(n)$ означает асимп. "не больше" $n$. В таком случае условие "не превосходит" теряет смысл, так как везде можно подставить нуль.

Может, вы имели ввиду "не меньше, чем"?

[Red_Herring]

SiberianSemion в сообщении #1409216 писал(а):

насколько я знаю, этот значок $\Omega(n)$ означает асимп. "не больше" $n$

Вы путаете $O(.)$ и $\Omega(.)$ они обратны https://en.wikipedia.org/wiki/Big_O_notation

[DeBill]

Red_Herring
Упс...А я то думал - непропечатка там...

-- 08.08.2019, 10:27 --

Но тогда утверждение ТС становится бессодержательным:
Ясно, что $n^7 = \Omega (n\ln n)$, а $T(n)$ явно меньше....
(А честное утверждение на самом деле такое: $T(n) \sim n \ln n$)

[capt]

DeBill
В пределе у меня получилось, что $c \leqslant 1$, т. е.

$$\lim_{n\to \infty}( c\lg n + c \lg (1 - 2/n) - \frac{2c \lg (n-2)}{n} + 1 - c + 2c/n) =\lim_{n\to \infty} (c \lg n + 1 - c)\geqslant \lim_{n\to \infty} c\lg n $$

В качестве базы индукции возьму $n = 1$, тогда $T(1) = 1 \geqslant c 1 \lg 1 = 0$.
Проверим для $n = 2$, $T(2) = 4 \geqslant 2c \lg 2 = 2c$, а учитывая, что $c \leqslant 1$, то неравенство выполняется.
Надеюсь сделал правильно.

[DeBill]

capt в сообщении #1409236 писал(а):

Надеюсь сделал правильно.

Нет.
1.И слева, и справа пределы - бесконечны, потому схема не работает.
2. Нужно $c<1$ - строго, иначе схема не работает
3.Из неравенства пределов следует неравество для функций, но лишь для больших ЭН
4. Такая база не прокатит в силу 3)
Ну я ж все писал!

[SiberianSemion]

capt, у Кормена это рекур. соотношение разобрано в общем виде. Сводку результатов по вычислениям руками этого соотношения обычно объединяют под названием master theorem. Можете глянуть.

[ELVY]

DeBill

DeBill в сообщении #1409213 писал(а):

Коль некое неравенство (строгое) в пределе верно, то оно верно и при всех $n$, достаточно больших (больших некоторого $N$). Ну вот теперь индукция и пошла (только еще надо - базу индукции проверить, и в качестве такой базы взять выполнение неравенства про всех $n<N$). А выполнение базовых предположений - обеспечить за счет подходящего уменьшения $c$...

Вы говорите проверить базу для $n < N$, а потом говорите, что такая база не прокатит, так как $n > N$. Я не понимаю, что вы имеете в виду.

-- 08.08.2019, 19:01 --

SiberianSemion
У Кормена про master theorem написано, только написано чуть позже.

[DeBill]

ELVY в сообщении #1409270 писал(а):

говорите, что такая база не прокатит, так как $n > N$.

Не было такого. "не прокатит" относилось к

capt в сообщении #1409236 писал(а):

В качестве базы индукции возьму $n = 1$,

А надо - повторяю - в качестве базы взять выполнение неравенства для всех $n<N$.
Напомню: мы сейчас хотим показать выполнение неравенства $T(n)>cn\ln n$ при некотором $c$ для всех $n$. Выполнение такого неравенства для малых $n$ (например, при всех $n<10000$) можно заведомо обеспечить , выбрав $c$ достаточно маленьким