Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 13 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Рекуррентное соотношение
СообщениеДобавлено: 27 апр 2015, 12:43 
Не в сети
Начинающий
Зарегистрирован:
27 апр 2015, 12:40
Сообщений: 9
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Решение соотношения T(n)=T(n-1)+logn совершенно ясно. Оно Тета(nlogn)

log(1) + log(2) + log(3) + ... log(n) = log(n!) = Тета(nlogn)

Но что если дано соотношение T(n)=T(n-1)+nlogn ?

Я могу записать - T(n)=T(n-2)+nlog(n)+(n-1)log(n-1) и так далее ..... выходит выражение 1log(1) + 2log(2) + 3log(3) + ... ...+ nlog(n) Не понимаю к чему могу это привести. Интуитивно решение похоже на Тета(n*nlogn)

Буду очень благодарен за помощь.


Последний раз редактировалось Micaver 27 апр 2015, 13:28, всего редактировалось 2 раз(а).
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Рекуррентное соотношение
СообщениеДобавлено: 27 апр 2015, 12:47 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Формулы наберите тегом math, приведите попытки решения, тогда подскажу :O:

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Рекуррентное соотношение
СообщениеДобавлено: 27 апр 2015, 13:36 
Не в сети
Начинающий
Зарегистрирован:
27 апр 2015, 12:40
Сообщений: 9
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Изображение

Так хорошо ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Рекуррентное соотношение
СообщениеДобавлено: 27 апр 2015, 13:50 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Нет, надо например так: [math]O(n\ln n)[/math] :O:

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Рекуррентное соотношение
СообщениеДобавлено: 27 апр 2015, 14:15 
Не в сети
Начинающий
Зарегистрирован:
27 апр 2015, 12:40
Сообщений: 9
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Извените, я не понял в чем разница ?

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

[math]\log_{2}{(1*2^2*3^3*4^4*........*n^n)}[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Рекуррентное соотношение
СообщениеДобавлено: 27 апр 2015, 14:22 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Юзайте это:
https://ru.wikipedia.org/wiki/%D0%A4%D0 ... 0%BD%D0%B0
Можно также юзать формулу суммирования по частям - дискретный аналог формулы интегрирования по частям (оно же преобразование Абеля).

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Рекуррентное соотношение
СообщениеДобавлено: 27 апр 2015, 14:50 
Не в сети
Начинающий
Зарегистрирован:
27 апр 2015, 12:40
Сообщений: 9
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Спасибо за помощь. Я пытаюсь сообразить но не выходит. Честно говоря я не математик, просто учу Рекуррентные соотношения. Можно попросить дополнительную помощь ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Рекуррентное соотношение
СообщениеДобавлено: 27 апр 2015, 16:02 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Micaver, Вы матанализ в каком объеме знаете?
Взятие интеграла [math]\int x\ln x dx[/math] затруднения вызывает?
Приведенные методы применить получилось или нет? В чем конкретно затруднение?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Рекуррентное соотношение
СообщениеДобавлено: 27 апр 2015, 16:56 
Не в сети
Начинающий
Зарегистрирован:
27 апр 2015, 12:40
Сообщений: 9
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
То есть сам ряд \log_{2}{(1*2^2*3^3*4^4*........*n^n)} = \int x\ln x dx ?

Матанализ я учил лет 15 назад. Сейчас просто взял курс базы данных.

Решение интеграла (( [math]\boldsymbol{x}[/math] [math]^{2}[/math]) [math]\div 2[/math]) [math]\cdot[/math] ([math]\ln{ \boldsymbol{x} }[/math]) - [math]\!\!\not{\phantom{1|2}}\,[/math] [math]+[/math] [math]\boldsymbol{C}[/math]


Изображение

Но чем мне это помогает ? :fool: Судя по решению, если оно правильно, асимптотическое ограничение равно Q(n^2lnn)


Последний раз редактировалось Micaver 27 апр 2015, 17:05, всего редактировалось 2 раз(а).
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Рекуррентное соотношение
СообщениеДобавлено: 27 апр 2015, 17:01 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Micaver писал(а):
То есть сам ряд \log_{2}{(1*2^2*3^3*4^4*........*n^n)} = \int x\ln x dx ?
Нет, просто похоже, в том числе идейно.

Micaver писал(а):
Матанализ я учил лет 15 назад. Сейчас просто взял курс базы данных.
А я 12 лет назад, но все хорошо помню.
Тогда берите формулу Эйлера-Маклорена или формулу Абеля и подставляйте туда Вашу сумму и будет Вам счастье. :O:
С другой стороны, доказывать это самостоятельно для теории БД необязательно.
Вы же себе доказываете утверждение, не преподу?
Можете просто взять верный ответ и проверить правилом Лопиталя теоремой Штольца.
Правильный ответ имеет вид: [math]\sum\limits_{k=1}^n k\ln k = \frac{n^2}{2}\ln n + \Theta (n\ln n)[/math] (вообще можно сумму до константы вычислить)

Micaver писал(а):
Решение интеграла (( [math]\boldsymbol{x}[/math] [math]^{2}[/math]) [math]\div 2[/math]) [math]\cdot[/math] ([math]\ln{ \boldsymbol{x} }[/math]) - [math]\!\!\not{\phantom{1|2}}\,[/math] [math]+[/math] [math]\boldsymbol{C}[/math]
Набрано отвратительно. Дробь пишется \frac{A}{B} [math]\frac{A}{B}[/math]
Но взятие этого интеграла - это в каком-то смысле часть задачи.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2  След.  Страница 1 из 2 [ Сообщений: 13 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Рекуррентное соотношение

в форуме Дискретная математика, Теория множеств и Логика

mrGaus

2

471

03 апр 2014, 11:51

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

в форуме Пределы числовых последовательностей и функций, Исследования функций

JustForStudy

5

388

22 ноя 2015, 11:40

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

в форуме Дискретная математика, Теория множеств и Логика

Nikejke

1

381

19 дек 2016, 22:04

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

в форуме Дискретная математика, Теория множеств и Логика

exponenta98

1

177

04 дек 2019, 22:20

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

в форуме Дискретная математика, Теория множеств и Логика

Toker

5

814

10 сен 2014, 10:33

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

в форуме Дискретная математика, Теория множеств и Логика

tiar_frv

3

446

17 май 2016, 22:59

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

в форуме Дискретная математика, Теория множеств и Логика

UndeadUser3

3

279

21 апр 2019, 18:59

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

в форуме Дискретная математика, Теория множеств и Логика

dissable1

3

377

05 дек 2014, 17:55

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

в форуме Ряды

ChpokHead

5

387

14 окт 2018, 17:35

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

в форуме Дискретная математика, Теория множеств и Логика

Serg63

0

131

04 фев 2022, 23:01


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 18


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved