Мне попалась следующая задача: Пусть $%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))$%. Для первой части, наверно, можно решить так: из определения немонотонной функции, для каждых $%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 paulpaul1076 |
Непонятен смысл равенства $%O(f)=O(g)$%. Если мы пишем $%f=O(g)$%, то это имеет понятный смысл ($%|f| \le C|g|$% для некоторой константы), а что означает равенство с двумя "$%O$%" -- непонятно.
Означает, что обе функции ограничены одним полиномом. То есть $%f = O(g)$% и $%g = O(f)$%.
Только что заметил, что для немонотонных до этого написал $%O(f) = O(g)$%, а надо $%O(f) != O(g)$%, исправил.
В общем, я думаю, что мой препод, как и всегда, задал бредовый вопрос, который не имеет смысла... Только баллы терять из-за таких.