Известно, что f(n) = O(n^2), g(n) = Ω(1), g(n) = O(n). Положим h(n) = f(n)/g(n). 1. Возможно ли, что а) h(n) = Θ(nlogn); б) h(n) = Θ(n^3)? 2. Приведите наилучшие (из возможных) верхние и нижние оценки на функцию h(n) и приведите пример функций f(n) и g(n) для которых ваши оценки на h(n) достигаются.

задан 10 Фев 23:13

а) Если f(n)=n^2, g(n)=n/log n, то всё выполняется.

б) f(n)<=Cn^2, g(n)>=K => f(n)/g(n) растёт не более чем квадратично, и кубического роста быть не может.

h(n)->max, если f(n)->max b g(n)->min. Оценка квадратичная, достигается при f(n)=n^2, g(n)=1.

h(n)->min, если взять f(n) как можно меньше, а оценка O(n^2) действует только сверху. Если значения функций не равны нулю, то берём f(n)=1 и g(n)=n, получая 1/n.

Серия вопросов довольно "беззубая".

(11 Фев 2:48) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×237
×150
×71

задан
10 Фев 23:13

показан
96 раз

обновлен
11 Фев 2:48

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

по почте:

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

по RSS:

Ответы

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

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