C помощью приведенной теоремы пытаюсь найти $%f(n)$% и $%g(n)$% в примере ниже, но у меня получается лишь получить выражение вида $%K = O(w(n))$%, как теперь это превратить в $%f(n)$% $%+$% $%O(g(n))$%?

alt text

alt text

задан 12 Мар '17 18:14

@HSEstore, тут явно желателен какой-то контекст.

(12 Мар '17 19:06) cartesius

@cartesius, честно говоря его нету, просто требуется $%K$% представить в виде $%f(n) + O(g(n))$% и в ВУЗе мне сказали применить указанную выше теорему.

(12 Мар '17 19:15) HSEstore

@HSEstore: если требуется применить какую-то теорему, то из неё должно что-то прямо следовать. Здесь из одной верхней оценки вроде бы ничего не выводится. Кроме того, запись вида f(n)+O(g(n)) имеет совершенно неопределённый вид. Я могу взять f(n)=0, g(n)=n^n, и всё будет верно.

Асимптотику для сумм биномиальных коэффициентов нетрудно получить хотя бы вероятностями методами. Не вижу смысла использовать учебное пособие, вызывающее так много вопросов.

(12 Мар '17 21:19) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×27

задан
12 Мар '17 18:14

показан
442 раза

обновлен
12 Мар '17 21:19

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

по почте:

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

по RSS:

Ответы

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

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