Расчет верхней и нижней границы

Question

Предположим, есть функция f (x) = 19n ^ 2 / 5n + 1-n
Я хочу вычислить верхнюю и нижнюю границу.Но у меня было это замешательство, что я должен рассчитывать в терминах п ^ 2?Поскольку доминирующий член равен n ^ 2

или Если я решу приведенное выше уравнение как f (x) = 19n / 5 + 1-n (отмена n в 1-м сроке) тогда что?Тогда я должен рассчитать с1 и с2 в терминах п?потому что это будет доминирующий термин.

Итак, пожалуйста, скажите мне, в каком сроке я должен вычислить c1 и c2, т.е. n или n ^ 2 ??Могу ли я отменить n в 19n ^ 2 / 5n или нет?Какова будет ее асимптотическая форма? f (n) ∈Θ (n ^ 2) или f (n) ∈Θ (n) ?

Answer 1

Хорошо, если у вас есть

f(n) = 19n^2 / (5n) - n + 1

, вы можете, с целью нахождения асимптотических границ, действительно отменить n, чтобы получить

f(n) = (19/5)n - n + 1 = (14/5)n + 1

Простой способдля этого необходимо отметить, что (14/5)n является здесь доминирующим термином, поэтому +1 можно игнорировать, а 14/5 является (положительной) константой, которая, следовательно, также может игнорироваться.

Следовательно, мы имеемf(n) ∈ Θ(n).

В терминах коэффициентов нижней и верхней границы c1 и c2 это может быть мотивировано тем фактом, что вы можете найти два таких коэффициента (больше нуля!), Таких что c1 * n асимптотически меньше f(n), тогда как c2 * n асимптотически больше f(n).Например, рассмотрим c1 = 1 и c2 = 3.