как вы доказываете, что большая тета серии является ее основным термином?

Question

, если f (x) = (An) x ^ n + (An-1) x ^ (n-1) + ... + (A1) x + (A0) как вы можете доказать, что f (x) - это большая тета (x ^ n).

Я думал об этом, и это можно сделать, доказав, что f (x) большой O (x ^ n) и x ^ n большой O (f (x)). Я нашел доказательство для первого (используя неравенство треугольника), но не мог понять, как это сделать.

В качестве альтернативы можно доказать, что f (x) - большая омега (x ^ n).

Я застрял в этом вопросе, и любые подсказки или подсказки, которые вы могли бы дать мне, очень помогли бы.

Answer 1

Рассмотрим | An x ^ n + A (n-1) x ^ (n-1) + ... | / | x ^ n |as x -> oo.

Выражение очень близко к | An |и если An не равно нулю, то для достаточно большого x выражение будет не меньше | An | /2.

Answer 2

Чтобы доказать, что f (x) - это O (x ^ n), обратите внимание, что для x> = 1 каждый 0 <= x ^ 0, x ^ 2, ... x ^ n <= x ^ n. </p>

Следовательно, f (x) <= (n + 1) * max (A_0 ... A_n) * x ^ n </p>

Но (n + 1) * max (A_0 ... A_n) является константой относительно x, поэтому мы имеем нашу оценку [*]

Доказать, что x ^ n - это O (f (x)), на самом деле довольно сложно, поскольку это не так , если только A_n! = 0. Но если A_n! = 0, требуется доказать:

x^n is O(An x^n + ... + A0 x^0)

По некоторым теоремам об ограничениях, о которых я не могу утверждать, это верно, если

(1/An) x^n is O(x^n + ... + (A0/An) x^0)

что верно, если

(1/An) x^n - ... - (A0/An) x^0 is O(x^n) [**]

Но теперь LHS - это многочлен вида, который мы только что доказали, это O (x ^ n) в первой части. Что и требовалось доказать.

Однако на практике вы фактически доказываете некоторые леммы о сложности больших чисел суммы двух функций с известными сложностями больших чисел. Тогда вы просто заметите, что все члены с обеих сторон равны O (x ^ n), а остальные можно игнорировать.

[*] На самом деле это выдумка, поскольку важно сравнение абсолютного значения функции. Но для достаточно большого x, f (x) имеет тот же знак, что и A_n, так что если это отрицательно, мы просто делаем аналогичное неравенство наоборот.

Я не думаю, что вам действительно нужно какое-либо использование неравенства треугольника, чтобы «избежать» абс, потому что полиномиальные функции обязательно являются монотонными вне определенного диапазона (то есть они имеют только конечное число точек перегиба), и когда учитывая пределы больших О, мы заботимся только о том, что происходит за пределами определенного диапазона.

[**] Еще одна выдумка, на самом деле я должен был написать предельную константу M на RHS и включить ее при переводе терминов в LHS. Итак, это всего лишь набросок доказательства.

Answer 3

Вы можете доказать, что это и большая O (x ^ n), и большая Омега (x ^ n).