Печать страницы - Асимптотические порядки

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 3, 2011, 09:13

Не знаю, как это по-русски называть.

В общем речь о большом О, малом о, омега большая-малая, тета.

Например мне нужно узнать, что больше, $[tex](\lg \lg n)^n[/tex]$ или $[tex]n \lg n[/tex]$ .

Один из способов найти это разделить одно на другое и найти предел при n уходящем в бесконечность. А что будет, если функции равного порядка?

Другой способ через неравенства и константы.

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

Название: Асимптотические порядки
Отправлено: Квас от ноября 3, 2011, 09:30

Цитата: RawonaM от ноября 3, 2011, 09:13
А что будет, если функции равного порядка?

Конечный предел, отличный от 0? :???

Я думаю, приведённых вами способов и смекалки хватит для всего. :)

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 3, 2011, 10:17

Цитата: Квас от ноября 3, 2011, 09:30
Конечный предел, отличный от 0? :???

Или от бесконечности, наверное.

Цитата: Квас от ноября 3, 2011, 09:30
Я думаю, приведённых вами способов и смекалки хватит для всего. :)

Да вот как-то не хватает, я уже даже забыл как пределы вычислять :)

Название: Асимптотические порядки
Отправлено: Квас от ноября 3, 2011, 12:08

Лопиталь наше всё!

В вашем примере можно, впрочем, обойтись без него. Прологарифмируем:
$[tex]a_n = (\lg \lg n)^n, \quad b_n = n \lg n[/tex]$ .
$[tex]\lg a_n = n \lg \lg \lg n, \quad \lg b_n = \lg n + \lg \lg n[/tex]$
$[tex]\lim_{n\to\infty}\frac{\lg b_n}{\lg a_n} = \lim_{n\to\infty}\frac{\lg n + \lg \lg n}{n \lg \lg \lg n} = 0,[/tex]$
потому что n в знаменателе забивает числитель. Это значит, что
$[tex]\frac{\lg b_n}{\lg a_n} = \alpha_n[/tex]$
— бесконечно малая. Отсюда
$[tex] b_n = a_n^{\alpha_n} [/tex]$
$[tex] \frac{b_n}{a_n} = a_n^{\alpha_n-1} \to 0,[/tex]$
так как $[tex]a_n \to \infty[/tex]$ .

Значит,
$[tex]b_n = o(a_n)[/tex]$
Неожиданное решение. :???

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 4, 2011, 09:25

Цитата: Квас от ноября 3, 2011, 12:08
Неожиданное решение. :???

А что такого неожиданного?

Спасибо Квас, с помощью взятия логарифма с обоих сторон почти все можно решить! А я как-то об этом не подумал.

Вопрос такой появился: если допустим f(n)=o(g(n)), то обязательно ли h(f(n))=o(h(g(n))?

А конкретнее так: даны lg lg n и lg lg lg n. Можно ли на основании того, что lg n = o(n) сделать прямой вывод, что lg lg lg n = o(lg lg n)?

Название: Асимптотические порядки
Отправлено: Квас от ноября 4, 2011, 10:47

Цитата: RawonaM от ноября 4, 2011, 09:25
Цитата: Квас от ноября 3, 2011, 12:08Неожиданное решение. :???
А что такого неожиданного?

Я прологарифмировал, чтобы лопиталить было легче, и даже не предполагал, к чему это приведёт. ;D

Цитата: RawonaM от ноября 4, 2011, 09:25
Вопрос такой появился: если допустим f(n)=o(g(n)), то обязательно ли h(f(n))=o(h(g(n))?

Вообще говоря, нет. Например, если h — постоянная, уже рушится.

Цитата: RawonaM от ноября 4, 2011, 09:25
А конкретнее так: даны lg lg n и lg lg lg n. Можно ли на основании того, что lg n = o(n) сделать прямой вывод, что lg lg lg n = o(lg lg n)?

В принципе, можно. Только на основании того, что lg x = o(x), где x — непрерывный аргумент (либо говорить какие-то слова о монотонности или немного преобразовывать — в любом случае пояснения необходимы, потому что в формуле lg n = o(n) участвуют логарифмы только от натуральных чисел). Именно, соотношение lg x = o(x) эквивалентно тому, что lg x = αx, α — бесконечно малая при x → \infty. Тогда
lg lg lg n = α(lg lg n) lg lg n ≡ β(n) lg lg n,
где, очевидно, β(n) → \infty при n → \infty.

Название: Асимптотические порядки
Отправлено: Bhudh от ноября 4, 2011, 10:52

Offtop

[test]
$[tex]\infty[/tex]$
[/test][/tt]

Значит, лень-матушка...

Название: Асимптотические порядки
Отправлено: Ömer от ноября 4, 2011, 10:56

Цитата: RawonaM от ноября 4, 2011, 09:25
А конкретнее так: даны lg lg n и lg lg lg n. Можно ли на основании того, что lg n = o(n) сделать прямой вывод, что lg lg lg n = o(lg lg n)?

В общем случае, f = o(g) => ln(f) = o(ln(g)) - неверно.
Например, n = o(n^2), но ln n и ln (n^2) - функции одного порядка.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 4, 2011, 11:00

Цитата: Bhudh от ноября 4, 2011, 10:52
Значит, лень-матушка...

Просто надо закинуть в кастом карактеры — ∞.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 4, 2011, 11:03

Цитата: svarog от ноября 4, 2011, 10:56
Например, n = o(n^2), но ln n и ln (n^2) - функции одного порядка.

Действительно.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 4, 2011, 11:09

Цитата: Квас от ноября 4, 2011, 10:47
Только на основании того, что lg x = o(x), где x — непрерывный аргумент (либо говорить какие-то слова о монотонности или немного преобразовывать — в любом случае пояснения необходимы, потому что в формуле lg n = o(n) участвуют логарифмы только от натуральных чисел). Именно, соотношение lg x = o(x) эквивалентно тому, что lg x = αx, α — бесконечно малая при x → \infty. Тогда
lg lg lg n = α(lg lg n) lg lg n ≡ β(n) lg lg n,
где, очевидно, β(n) → \infty при n → \infty.

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

Название: Асимптотические порядки
Отправлено: Квас от ноября 4, 2011, 11:59

Offtop

Цитата: Bhudh от ноября 4, 2011, 10:52
Значит, лень-матушка...

Не, ну не в хармап же за бесконечностью лезть. Мне её надо закинуть в кастом символы на клавиатуре своей.

Цитата: RawonaM от ноября 4, 2011, 11:09
Интересно, возможно ли сформулировать при каких условиях наложение функции нарушает порядковое отношение, а при каких оно не меняется.

Да можно, наверно. Однако, я думаю, проще в сомнительных случаях переписать через умножение на бесконечно малую. Там, правда, замена переменной в пределе может получиться, но часто её можно произвести интуитивно-приемлемо.

Название: Асимптотические порядки
Отправлено: Bhudh от ноября 4, 2011, 12:04

Offtop

Цитата: Квас от Не, ну не в хармап же за бесконечностью лезть.

Я имел в виду, лень на кнопу в быстром ответе нажать. Там же есть tex :)
(Главное, 6 символов писать не лень...)

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 4, 2011, 15:44

Цитата: Квас от ноября 3, 2011, 12:08
Отсюда
$[tex] b_n = a_n^{\alpha_n} [/tex]$
$[tex] \frac{b_n}{a_n} = a_n^{\alpha_n-1} \to 0,[/tex]$
так как $[tex]a_n \to \infty[/tex]$ .

Что-то я тут ничего не понял. Можете пояснить?
$[tex] \frac{b_n}{a_n} = a_n^{\alpha_n-1} \to 0,[/tex]$ — это что вообще значит?

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 4, 2011, 16:15

$[tex]\lim_{n\to\infty}n^{1/\lg n}[/tex]$ чему равен?
Даже не получилось нарисовать эту функцию в максиме.

Название: Асимптотические порядки
Отправлено: Bhudh от ноября 4, 2011, 17:32

Простой подстановкой чисел выходит, что он равен $[tex]e[/tex]$ .

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 4, 2011, 17:39

Цитата: Bhudh от ноября 4, 2011, 17:32
Простой подстановкой чисел выходит

Это как?

Название: Асимптотические порядки
Отправлено: Bhudh от ноября 4, 2011, 18:56

Ну вычисли последовательно $[tex]2^{1/\lg 2},\ 3^{1/\lg 3},\ 4^{1/\lg 4}...[/tex]$

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 4, 2011, 19:47

Вроде с горем пополам отсортировал. Нужно также найти классы эквивалентности (т.е. функции равного порядка относятся к одному классу), но мне почему-то кажется, что все тут разные. Посмотрите, может таки где-то я ошибся. Кстати lg тут обозначает log₂, если это имеет значение.

На картинке также Мэпл, с которым я задолбался воевать, никак не хочет ничего считать.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 4, 2011, 20:06

С помощью мэпл вычилил, что таки 2ⁿ сильнее других, ее наверх надо.

Только вот не пойму, можно ли доверять мэплу. Вот откуда он с такой уверенностью взял 0 в первом случае?

Название: Асимптотические порядки
Отправлено: Квас от ноября 4, 2011, 20:07

Цитата: RawonaM от ноября 4, 2011, 15:44
$[tex] \frac{b_n}{a_n} = a_n^{\alpha_n-1} \to 0,[/tex]$ — это что вообще значит?

Просто поделил обе части последнего равенства на a_n. Левая часть стремится к 0, потому что показатель стремится к -1, а основание уходит в бесконечность.

Название: Асимптотические порядки
Отправлено: Квас от ноября 4, 2011, 20:08

Цитата: RawonaM от ноября 4, 2011, 19:47
На картинке также Мэпл, с которым я задолбался воевать, никак не хочет ничего считать.

Команды-то с маленьких букв.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 4, 2011, 20:17

Как в мэпле определить lg=log₂?

Название: Асимптотические порядки
Отправлено: Квас от ноября 4, 2011, 20:23

Цитата: RawonaM от ноября 4, 2011, 20:17
Как в мэпле определить lg=log₂?

lg := x -> log[2](x)

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 4, 2011, 20:30

Спасибо.

Короче это задание меня достало. Я с помощью мэпла перестроил заново всю очередь, только потом обнаружил, что он опять бред выдает :(

Вот в чем разница между первым и вторым?

Название: Асимптотические порядки
Отправлено: Квас от ноября 4, 2011, 20:33

Престранно. Старенькая «шестёрка» даёт в первом случае тоже 0.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 5, 2011, 09:17

Поэксперементировал: если стоит пробел, что между эн в квадрате и скобкой, то считает правильно, если пробела нет, то выдает бесконечность. В чем прикол?

Название: Асимптотические порядки
Отправлено: arseniiv от ноября 5, 2011, 09:48

А вот в Mathematic'е я бы всегда смог посмотреть, как она это дело во внутренний вид распарсила! В Maple есть такая функция?

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 5, 2011, 10:05

Наверное есть, только я не знаю как.

Название: Асимптотические порядки
Отправлено: Квас от ноября 5, 2011, 12:53

Пробел — знак умножения. Наверно, без пробела он интерпретировал n как имя функции.

Насчёт распаршивания я тоже не знаю.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 5, 2011, 12:55

А что он делает с незнакомыми функциями? Почему он не говорит, что такая функция не определена? Он ее за 0 считает что ли?

Название: Асимптотические порядки
Отправлено: Квас от ноября 5, 2011, 12:57

Цитата: RawonaM от ноября 5, 2011, 12:55
А что он делает с незнакомыми функциями? Почему он не говорит, что такая функция не определена? Он ее за 0 считает что ли?

Считает просто за n(), так же как a считает за некоторую величину. Если продифференцировать, например, то получится diff(n(x),x) — логично, собственно.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 5, 2011, 13:01

Не понял. Откуда все-таки взялось ∞ в первом примере?

Название: Асимптотические порядки
Отправлено: Квас от ноября 5, 2011, 13:03

Цитата: RawonaM от ноября 5, 2011, 13:01
Не понял. Откуда все-таки взялось ∞ в первом примере?

Бог его знает. Наверно, он решил, что поскольку числитель уходит в бесконечность, а о знаменателе он ничего сказать не может, то получается бесконечность.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 5, 2011, 13:32

В пицотый раз перестроил порядок. Все-таки задание выглядит глуповатым, да еще и найти классы эквивалентности, когда тут все функции разных порядков. Видимо чего-то я недопонял.

Название: Асимптотические порядки
Отправлено: Квас от ноября 5, 2011, 13:59

Пересчитал: везде пределы получаются как надо.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 5, 2011, 14:07

Спасибо :) У вас тоже все вышли нули/бесконечности, т.е. все разных порядков?

Название: Асимптотические порядки
Отправлено: Квас от ноября 5, 2011, 14:10

Ага, именно так.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 5, 2011, 15:11

Почему-то в гуглдоксе 2 в степени корень логарифма выглядит как 2 умножить на корень.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 19, 2011, 09:09

А если я для определения порядков беру обе стороны в 2^lg(x), порядки же должны сохраниться во всех случаях, неспа? Ведь это та же функция получается для х>0.
Допустим нужно определить f(n) ? g(n), берем в 2^{lg f(n)} ? 2^{lg g(n)}, если определяется отношение, то то же самое можно ставить между f(n) и g(n), верно?

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 19, 2011, 10:24

Мне нужно посчитать асимптотический порядок рекуррентного отношения
$[tex]T(n)=\sqrt n \cdot T(\sqrt n) + n \lg n[/tex]$

У меня получилось $[tex]\Theta(n \lg n)[/tex]$ , причем первая часть $[tex]\sqrt n \cdot T(\sqrt n)=\Theta(1)[/tex]$ , т.е. всегда константа. Может такое быть?

Название: Асимптотические порядки
Отправлено: Квас от ноября 19, 2011, 13:47

Цитата: RawonaM от ноября 19, 2011, 09:09
Ведь это та же функция получается для х>0.
Допустим нужно определить f(n) ? g(n), берем в 2^{lg f(n)} ? 2^{lg g(n)}, если определяется отношение, то то же самое можно ставить между f(n) и g(n), верно?

Без сомнения, потому что написано одно и то же. :yes:

Название: Асимптотические порядки
Отправлено: Квас от ноября 19, 2011, 13:55

Цитата: RawonaM от ноября 19, 2011, 10:24
Мне нужно посчитать асимптотический порядок рекуррентного отношения
$[tex]T(n)=\sqrt n \cdot T(\sqrt n) + n \lg n[/tex]$

А как вы делали? Пока я догадался только поделить на n lg n и получить соотношение между двумя дробями одинакового вида. Однако, кажется, ничто не мешает обеим уходить в бесконечность.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 19, 2011, 14:18

Цитата: Квас от ноября 19, 2011, 13:55
Цитата: RawonaM от ноября 19, 2011, 10:24Мне нужно посчитать асимптотический порядок рекуррентного отношения
$[tex]T(n)=\sqrt n \cdot T(\sqrt n) + n \lg n[/tex]$
А как вы делали? Пока я догадался только поделить на n lg n и получить соотношение между двумя дробями одинакового вида. Однако, кажется, ничто не мешает обеим уходить в бесконечность.

Для уровня на один ниже верхнего:
$[tex]T(\sqrt n)=n^{1/4} \cdot T(n^{1/4}) + n^{1/2} \lg n^{1/2}[/tex]$

Отсюда $[tex]T(n)=n^{1/2}(n^{1/4} \cdot T(n^{1/4}) + n^{1/2} \lg n^{1/2}) + n \lg n[/tex]$ .
...
Для уровня i получается: $[tex]T(n)=\prod_{k=1}^i n^{1/2^k} \cdot T(n^{1/2^i}) + \sum_{k=0}^{i-1} n^{1/2^k} \lg n^{1/2^k}[/tex]$ .

Правое слагаемое $[tex]\Theta(n\lg n)[/tex]$ .

Левое слагаемое:
$[tex]\prod_{k=1}^i n^{1/2^k} \cdot T(n^{1/2^i})=n^{\sum_{k=1}^i 1/2^k} \cdot T(n^{1/2^i})[/tex]$

Определим T(2)=1, возьмем i=lg lg n (чтобы $[tex]n^{1/2^i}=2[/tex]$ ).

Подставим: $[tex]n^{\sum_{k=1}^i 1/2^k} \cdot T(n^{1/2^i})=n^{\sum_{k=1}^{\lg\lg n} 1/2^k}=n^{\frac{1-1/2^{\lg\lg n +1}}{1-1/2}}=n^{2-1/\lg n}=\frac{n^2}{n^{1/lg n}}[/tex]$
$[tex]=\frac{n^2}{2^{\lg n^{1/lg n}}}=\frac{n^2}{2}=\Theta(n^2)[/tex]$ .

Упс, вот и ошибка нашлась. :) Значит все вместе $[tex]\Theta(n^2)[/tex]$ .

Название: Асимптотические порядки
Отправлено: Квас от ноября 19, 2011, 14:31

Блин, высшая математика. :(

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 19, 2011, 14:31

Не, там еще одна ошибка в сумме.

Цитата: RawonaM от ноября 19, 2011, 14:18
Подставим: $[tex]n^{\sum_{k=1}^i 1/2^k} \cdot T(n^{1/2^i})=n^{\sum_{k=1}^{\lg\lg n} 1/2^k}=n^{\frac{1-1/2^{\lg\lg n +1}}{1-1/2}}=n^{2-1/\lg n}=\frac{n^2}{n^{1/lg n}}[/tex]$
$[tex]=\frac{n^2}{2^{\lg n^{1/lg n}}}=\frac{n^2}{2}=\Theta(n^2)[/tex]$ .

Должно быть:

$[tex]n^{\sum_{k=1}^i 1/2^k} \cdot T(n^{1/2^i})=n^{\sum_{k=1}^{\lg\lg n} 1/2^k}=n^{\sum_{k=0}^{\lg\lg n - 1} 1/2^{k+1}}=n^{1/2 \cdot \sum_{k=0}^{\lg\lg n - 1} 1/2^{k}}=[/tex]$

$[tex]=n^{1/2 \cdot \frac{1-1/2^{\lg\lg n}}{1-1/2}}=n^{1-1/\lg n}=\frac{n}{n^{1/\lg n}}=\frac{n}{2}=\Theta(n)[/tex]$ .

Опять таки выходит всего $[tex]\Theta(n \lg n)[/tex]$ .

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 19, 2011, 14:38

Цитата: Квас от ноября 19, 2011, 14:31
Блин, высшая математика. :(

Ага, не низшая точно :(

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 23, 2011, 23:10

$[tex]\Theta(\lg(n-1))[/tex]$ чему равно? Разве не $[tex]\Theta(\lg n)[/tex]$ ?
А то если раскрыть получится деление на ноль. :???

Название: Асимптотические порядки
Отправлено: Квас от ноября 23, 2011, 23:17

Цитата: RawonaM от ноября 23, 2011, 23:10
А то если раскрыть получится деление на ноль. :???

Почему?

$[tex]\lg (n-1) = \lg n \cdot \frac{n-1}n = \lg n + \lg \left( 1-\frac 1n\right)[/tex]$

Последнее слагаемое стремится к 0, поэтому всё нормально.

Название: Асимптотические порядки
Отправлено: RawonaM от ноября 23, 2011, 23:29

Ага, это я напутал. Спасибо :)

Название: Асимптотические порядки
Отправлено: 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 от ноября 3, 2011, 09:13