Асимптотические порядки

RawonaM · декабря 31, 2011, 18:29

Известно что $[tex]\lg n! = \Theta(n\lg n)[/tex]$ . Как доказывается понятия не имею.
Верно ли, что $[tex]\lg (n-k)! = \Theta(k \lg n) [/tex]$ ?

RawonaM · января 1, 2012, 10:38

Вот тут я нигде не ошибся?

Fobee · января 1, 2012, 11:03

На k какие ограничения? А то при k=0 уже вторая формула неправильная.
Если $[tex]0<k \leq n[/tex]$ , то можно гарантировать, что $[tex]\lg (n-k)! = O(n \lg n)[/tex]$

RawonaM · января 1, 2012, 11:04

0<k<=n

RawonaM · января 1, 2012, 11:06

Тьфу, во втором я не то написал, что имел в виду. Щас перепишу.

RawonaM · января 1, 2012, 11:09

Вот, исправил. Все остальное не изменилось.

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]$

Мне нужно Омегу, а не О. Минимум нужно.

Квас · января 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, 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 — переменная?

Обе переменные.
Мне важна нижняя граница, верхняя не имеет значения в данном случае.

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: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: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, 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, 23:14

Конечная версия. Отправляю задание, до полуночи нужно сдать, да спать надо.

Лингвофорум

Асимптотические порядки

RawonaM

RawonaM

Fobee

RawonaM

RawonaM

RawonaM

RawonaM

Квас

RawonaM

RawonaM

RawonaM

RawonaM

RawonaM

RawonaM

Быстрый ответ