Большая Тета проблема

Question

У меня есть две функции:

• f (n) = 2;
• g (n) = 10 ^ 100;

У меня естьчтобы обосновать, если f (n) = BigTheta (g (n)) или нет.

Я предполагаю, что f (n) - BigTheta (g (n)), так как обе функции являются константами (что означаетфункции пропорциональны), но мой учитель настаивает на том, что я не прав.

Я прав?Есть ли какой-нибудь способ, которым я мог бы отдохнуть мое дело?Извините, если это звучит как нубский вопрос!Спасибо.

Answer 1

Вы правы.Предполагая, что вы процитировали проблему правильно, и нет никаких недоразумений, ваш учитель ошибается, если они сказали, что они не друг друга.

Вот определение:

http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations

Ясно |100^10|*k1 <= |2| <= |100^2|*k2 для констант k1=1/100^10 и k2=1 (для всех х больше, чем любое подходящее значение отсечения x_cutoff)

Не зная фактического текста задачи экзамена, хотя иточный текст, который вы написали (или обвели), мы не можем узнать в интернете, что нет какого-то неправильного понимания проблемы.Вы также должны заметить, что вы все еще можете ошибаться в своем обосновании, даже если ваш ответ правильный.

Для записи не только f(x) в наборе BigTheta(g(x)), но g(x) вустановить BigTheta(f(x)).Я думаю, что эквивалентное определение состоит в том, что отношение двух функций ограничено как x -> infinity (следует делением определения Википедии на |g(x)|, чтобы получить |f(x)|/|g(x)| < constant мимо некоторой точки отсечения), что может бытьболее простое определение, чтобы думать (и более очевидно, чтобы доказать).Это также подразумевает, что BigTheta является симметричным отношением.

Теперь у вас есть подходящие инструменты, чтобы спросить: «Почему вы думаете, что я неправ?»а затем используйте математику, чтобы определить, кто из вас прав;любое недоразумение должно появиться в математике, если нет, то вы докажете свою точку зрения.

Answer 2

f(n) <= g(n) * 1
2    <= 10^100     for all n >= 0

Таким образом f(n) = O(g(n)).

f(n) >= g(n) * 2/(10^100)
2    >= 10^100 * 2/(10^100) = 2      for all n >= 0

И так f(n) = Ω(g(n)).

И f(n)=O(g(n)), и f(n)=Ω(g(n)) означают f(n) = Θ(g(n)). Да, вы правы.