1) 1 не большая O (1/х)
Чтобы показать, что 1 не O (1/x), мы должны показать, что для любой постоянной c, нет x_0 такой, что 1 <= c*1/x для всех x >= x_0. Предположим, что 1 является большим O из 1/x. Мы принимаем c = c_0 > 0, константу. Тогда у нас должно быть 1 <= c_0*1/x для x >= x_0. Предполагая x > 0, мы можем решить и получить x <= c_0. Это не может быть справедливо для всех x >= x_0 (для первого номера больше или равно max(x_0, c_0)), поэтому наше предположение было неправильным и первое не было большим О второго. не
2) е^х не O (х^5) Big O
Чтобы показать, что e^x не O (x^5), мы должны показать, что для любой константы c, нет x_0 такой, что для всех x >= x_0, e^x <= c*x^5. Предположим, e^x большой O x^5. Мы принимаем c = c_0 > 0, константу. Тогда у нас должно быть e^x <= c_0*x^5 для x >= x_0. Мы можем изменить это, чтобы получить e^x/x^5 <= c_0 для всех x >= x_0. Однако предел e^x/x^5 как x -> +inf имеет тенденцию к +inf; мы можем увидеть это итерация правила Лопиталя:
e^x e^x e^x
lim --- = lim --- = ... = lim --- = +inf
x->+inf x^5 x->+inf 5x^4 x->+inf 120
Это противоречие, так как нет постоянной c_0 больше или равен бесконечности. Поэтому наше предположение было неправильным, и первое не было большим О второго.
Примечание: Я пишу lim = +inf, чтобы означать нечто вроде «значение выражения растет без ограничений».
Если вы находитесь в дискретном классе математики, они учат вас этому. Сделайте домашнее задание, задайте вопросы профессору, и вы узнаете, как это работает. Просить интернет о готовом решении, как правило, не соответствует стандартам академической этики. Как отмечается в вашем учебнике, трюк состоит в том, чтобы определить две функции: одну, которая является «нижней границей», а другая - «верхней границей». Если эти ограничивающие функции имеют одинаковую Большую О, то и ограниченная функция. Все дело в игнорировании констант и сосредоточении внимания на том, как функция растет с очень большим x. –
Это звучит так, как будто вы просите о помощи в домашней работе ... –
@ChuckWalbourn Я в весенней школе, а занятия еще не начались. У меня есть некоторые предыдущие знания о дискретной математике, но я знаю, что большой O - одна из основных концепций, поэтому я пытаюсь ее полностью понять.Я занимаюсь практическими вопросами из учебника и просматриваю веб-страницы, но не нашел ничего, что помогло мне понять шаги. Если вы не отвечаете на мой вопрос, не беспокойтесь о публикации или комментировании темы. Этот сайт создан, чтобы помогать друг другу, и для этого я здесь. – Newbie