Мне попалась следующая задача:

Пусть $%f(n)$% и $%g(n)$% - это две неубывающие функции, ограниченные полиномами. Предположим, что для некоторой геометрической прогрессии $%n_1 < n_2 < n_3 < ... < n_i < ...$% имеет место соотношение $%O(f(n_i)) = O(g(n_i))$%.

1) Доказать, что тогда $%O(f(n)) = O(g(n))$%.
2) Показать, что это утверждение неверно для немонотонных функций.

Для первой части, наверно, можно решить так: из определения немонотонной функции, для каждых $%x$% и $%y$%, где $%x < y$%, мы имеем $%f(x) < f(y)$%, $%g(x) < g(y)$%, т.к. это выполняется для геометрической прогрессии, оно так же выполняется для любой другой неубывающей последовательности, следовательно $%O(f(n)) = O(g(n))$%.

Вторую часть задания я абсолютно не понял, как можно доказать, что $%O(f(n)) \neq O(g(n))$% для немонотонных $%f(n)$% и $%g(n)$%?

Допустим $%g(n)$% немонотонна, следовательно, если, например, $%f(n) = 1 + g(n)$%, то $%O(f(n)) = O(g(n))$%.

Как тут быть?

задан 4 Июн '15 18:39

изменен 5 Июн '15 1:19

Непонятен смысл равенства $%O(f)=O(g)$%. Если мы пишем $%f=O(g)$%, то это имеет понятный смысл ($%|f| \le C|g|$% для некоторой константы), а что означает равенство с двумя "$%O$%" -- непонятно.

(4 Июн '15 20:24) falcao

Означает, что обе функции ограничены одним полиномом. То есть $%f = O(g)$% и $%g = O(f)$%.

(4 Июн '15 20:31) paulpaul1076

Только что заметил, что для немонотонных до этого написал $%O(f) = O(g)$%, а надо $%O(f) != O(g)$%, исправил.

(4 Июн '15 20:35) paulpaul1076

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

(4 Июн '15 21:02) paulpaul1076
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×4,466
×1,002
×780
×152
×151

задан
4 Июн '15 18:39

показан
1365 раз

обновлен
5 Июн '15 1:19

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru