Лингвофорум

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

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

Например мне нужно узнать, что больше, или .

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

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

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

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

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

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

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

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

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

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

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

В вашем примере можно, впрочем, обойтись без него. Прологарифмируем:
.


потому что n в знаменателе забивает числитель. Это значит, что

— бесконечно малая. Отсюда


так как .

Значит,

Неожиданное решение.

Цитата: Квас от ноября  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)?

Цитата: RawonaM от ноября  4, 2011, 09:25

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

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

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

Цитата: 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.

Цитата: 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) - функции одного порядка.

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

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

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

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

Цитата: Квас от ноября  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.

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

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

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

Цитата: Квас от ноября  3, 2011, 12:08
Отсюда


так как .

Что-то я тут ничего не понял. Можете пояснить?
— это что вообще значит?

чему равен?
Даже не получилось нарисовать эту функцию в максиме.

Простой подстановкой чисел выходит, что он равен .

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

Это как?

Ну вычисли последовательно

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

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

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

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

Цитата: RawonaM от ноября  4, 2011, 15:44
— это что вообще значит?

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

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

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

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

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

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

Спасибо.

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

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