Как мне доказать, что $ 3x ^ 3 + 2x + 1 $ равно $ \ omega (x \ cdot \ log x) $

Question

Я пытаюсь ответить на этот вопрос:$3x^3 +2x + 1$ является $ \omega(x \cdot \log x)$

Мой вопрос заключается в том, как решить этот вопрос.

Вот что я пробовал до сих пор:

Я применил это определение $3x^ 3 + 2x + 1 > c \cdot x\log x$ для всех c, учитывая $n \ geq k$, для некоторых k

Я попытался применить технику применения равенства, которое:$n < n^3$

Поскольку n меньше термина высшего порядка, мы можем просто переместить все термины в порядок n ??

Отдающий $6x < c \cdot x \log x$

Тогда вы можете выбрать:$ k < 2^\frac{6}{c}$

Answer 1

Что я рекомендую в первую очередь, так это заметить, что если вы смотрите на сложность функции $3x^ 2+2x+1$, на самом деле все, о чем вы должны заботиться, - это функция $x^2$.потому что если вы докажете это $x^2 = \omega(xlogx)$ затем добавляем $2x + 1$ не разрушу это доказательство, так как $x^2$ полиномиально больше, чем $2x + 1$ и поэтому мы можем просто взглянуть на $x^2$.

(Я буду использовать $n$ вместо того, чтобы $x$ потому что это то, с чем я знаком, но это точно то же самое для $x$)

Итак, теперь мы хотим доказать, что $$n^2 = \omega(nlogn)$$

который, как вы предложили, только вам нужно перевернуть свои стороны уравнения, нам нужно будет найти положительное $C$, так что для любого $n>n_0$ или $n>k$ : $$f (n)\ge C\cdot g(n)$$ когда $f(n) = n^2$ , $g(n) = nlogn$

Это поможет нам:$ n ^ 2 \ge Cnlogn $

Мы можем разделить обе стороны на $n$: $$n \ge Clogn$$

Вот это уже немного сложнее.но "известно", что полиномиальное время выполнения МЕДЛЕННЕЕ логарифмического.

По сути, это означает, что вы предпочли бы достичь логарифмической сложности, если это возможно, потому что тогда вы получите более быстрое выполнение.

Как правило, это порядок выполнения, когда первое является самым быстрым:

$$1.Постоянная$$ $$2.Логарифмический$$ $$3.Линейный$$ $$4.Линеарифмический$$ $$5.Многочлен$$ $$6.Экспоненциальный$$

(подробнее об этом вы можете прочитать здесь: https://adrianmejia.com/most-popular-algorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course/)

Другой способ увидеть это - если вы найдете предел разделения двух функций, допустим, мы выберем:$${f(n) \над g(n)}$$

Если $$\lim_{от n\ до \infty} {f (n) \над g(n)} ightarrow \infty$$ Это означает , что $f(n)$ это "намного больше", чем $g(n)$

Если $$\lim_{от n\до \infty} {f (n) \над g(n)} ightarrow 0$$ Это означает , что $f(n)$ является "намного меньшим", чем $g(n)$

Последним вариантом (по крайней мере, в этом методе) является:$$\lim_{от n\до \infty} {f(n) \над g(n)} ightarrow C$$ Когда $C \gt 0$ это означает, что обе функции имеют асимптотически одинаковую сложность.

Возвращаясь к нашим функциям, мы можем видеть, что :$$\lim_{от n\до \infty} {n \ по логарифму (n)}$$

Мы воспользуемся правилом люпитала и получим:$$\lim_{от n\ до \infty} {1 \ больше 1/n} ightarrow \infty$$

Теперь мы можем видеть, что $f(n) = n$ больше Асимптотически из $g(n) = log(n)$ следовательно :$$n = \omega (log(n))$$

---

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

---

Обновить :Я заметил, что вы внесли изменения в исходную функцию, и теперь это $3x^3+2x+1$, но доказательство будет тем же самым, просто используйте $n^3$ и тогда вы все равно получите тот же результат при использовании люпитала.Это потому, что неизбежно, если бы мы только что доказали, что $n^2$ это намного больше, чем $log(n)$ чем, конечно, то , что $n^3$ что намного больше, чем $n^2$ также было бы больше, чем $log(n).$

Answer 2

Самый простой способ - проверить, что $ \ lim_ {x \ to \ infty} \ frac {3x ^ 3 + 2x +1} {x \ log x}= + \infty $ , который является достаточным условием для $ 3x ^ 3 + 2x +1 \ in \ Omega (x \ log x) $ .

$$ \ lim_ {x \ to \ \ infty} \ frac {3x ^ 3 + 2x +1} {x \ log x}= \ lim_ {x \ to \ \ infty} \ frac {3x ^ 3} {x \ log x}= \ lim_ {x \ to \ \ infty} \ frac {3x ^ 2} {\ log x}= \ lim_ {x \ to \ \ infty} 6x ^ 2 = + \ infty. $$