Главное меню
Мы солидарны с Украиной. Узнайте здесь, как можно поддержать Украину.

Ответ

Обратите внимание: данное сообщение не будет отображаться, пока модератор не одобрит его.
Ограничения: максимум вложений в сообщении — 3 (3 осталось), максимальный размер всех файлов — 300 КБ, максимальный размер одного файла — 100 КБ
Снимите пометку с вложений, которые необходимо удалить
Перетащите файлы сюда или используйте кнопку для добавления файлов
(Удалить вложения)
Вложения и другие параметры
Проверка:
Оставьте это поле пустым:
Наберите символы, которые изображены на картинке
Прослушать / Запросить другое изображение

Наберите символы, которые изображены на картинке:

√36:
ALT+S — отправить
ALT+P — предварительный просмотр

Сообщения в этой теме

Автор RawonaM
 - января 1, 2012, 23:14
Конечная версия. Отправляю задание, до полуночи нужно сдать, да спать надо.
Автор RawonaM
 - января 1, 2012, 23:04
Цитата: Квас от января  1, 2012, 19:05
Цитата: RawonaM от января  1, 2012, 11:040<k<=n
При этом k постоянная, а n — переменная?
Все-таки выходит наверное что так. Иначе если они две переменные то ничего не получается.
С другой стороны, если k постоянная, то [tex]\Omega(k\lg n)=\Omega(\lg n)[/tex]. Почему тогда так не сформулировали?
Автор RawonaM
 - января 1, 2012, 22:22
Цитата: RawonaM от января  1, 2012, 22:20
Цитата: RawonaM от декабря 31, 2011, 18:29Известно что [tex]\lg n! = \Theta(n\lg n)[/tex].
Отсюда:
[tex]\lg (n-k)! = \Theta((n-k)\lg (n-k))=\Theta((n-k)(\lg n+\lg(1-k/n)))=\Theta(n\lg(n))[/tex]
Верно же?
Нет, что-то тут не так. Если k = n то не сходится.
Автор RawonaM
 - января 1, 2012, 22:20
Цитата: Квас от января  1, 2012, 19:05
Цитата: RawonaM от декабря 31, 2011, 18:29Верно ли, что [tex]\lg (n-k)! = \Theta(k \lg n) [/tex] ?
Вообще, это очень странно, учитывая, что чем k больше, тем левая часть меньше, а правая — больше.
Я вообще тут не то написал, что надо, но ради спортивного интереса:
Цитата: RawonaM от декабря 31, 2011, 18:29
Известно что [tex]\lg n! = \Theta(n\lg n)[/tex].
Отсюда:
[tex]\lg (n-k)! = \Theta((n-k)\lg (n-k))=\Theta((n-k)(\lg n+\lg(1-k/n)))=\Theta(n\lg(n))[/tex]
Верно же?

Автор RawonaM
 - января 1, 2012, 22:11
Цитата: Квас от января  1, 2012, 19:05
Цитата: RawonaM от декабря 31, 2011, 18:29Верно ли, что [tex]\lg (n-k)! = \Theta(k \lg n) [/tex] ?
Вообще, это очень странно, учитывая, что чем k больше, тем левая часть меньше, а правая — больше.
Но кто сказал что больше на порядок? Вот тут есть ошибки:
Spoiler ⇓⇓⇓
?
Автор RawonaM
 - января 1, 2012, 22:09
Цитата: Квас от января  1, 2012, 19:05
Омегу, а не фиту? Вообще запутался. Просмотрев тему, определения фиты не нашёл.
Тета определяется как Омега и Омикрон большой одновременно.
[tex]f(n) = \Theta(g(n)) \Leftrightarrow f(n)=O(g(n)),f(n)=\Omega(g(n))[/tex]

Цитата: Квас от января  1, 2012, 19:05
Цитата: RawonaM от января  1, 2012, 11:040<k<=n
При этом k постоянная, а n — переменная?
Обе переменные.
Мне важна нижняя граница, верхняя не имеет значения в данном случае.
Автор Квас
 - января 1, 2012, 19:05
Цитата: RawonaM от декабря 31, 2011, 18:29
Верно ли, что [tex]\lg (n-k)! = \Theta(k \lg n) [/tex] ?

Вообще, это очень странно, учитывая, что чем k больше, тем левая часть меньше, а правая — больше.

Цитата: RawonaM от января  1, 2012, 11:04
0<k<=n

При этом k постоянная, а n — переменная?

Цитата: RawonaM от января  1, 2012, 15:55
Цитата: Fobee от января  1, 2012, 11:03Если [tex]0<k \leq n[/tex], то можно гарантировать, что [tex]\lg (n-k)! = O(n \lg n)[/tex]
Мне нужно Омегу, а не О. Минимум нужно.

Омегу, а не фиту? Вообще запутался. Просмотрев тему, определения фиты не нашёл.
Автор RawonaM
 - января 1, 2012, 15:55
Цитата: Fobee от января  1, 2012, 11:03
Если [tex]0<k \leq n[/tex], то можно гарантировать, что [tex]\lg (n-k)! = O(n \lg n)[/tex]
Мне нужно Омегу, а не О. Минимум нужно.
Автор RawonaM
 - января 1, 2012, 11:09
Вот, исправил. Все остальное не изменилось.
Автор RawonaM
 - января 1, 2012, 11:06
Тьфу, во втором я не то написал, что имел в виду. Щас перепишу.