我试图回答这个问题: $ 3x ^ 3 + 2x + 1 $ $ \ oomega(x \ cdot \ log x)$

我的问题是如何解决这个问题。

这是我迄今为止的尝试:

我应用了定义 $ 3x ^ 3 + 2x + 1> c \ cdot x \ log x $ 对于所有c,给定 $ n \ geq k $ ,对于某些k

我试图应用应用程序的平等的技术: $ n

因为n小于最高订单术语,我们只需移动所有术语n ??

给出 $ 6x

然后你可以选择: $ k <2 ^ \ frac {6} {c} $

有帮助吗?

解决方案

我推荐的是什么首先要注意,如果你正在寻找函数的复杂性 $ 3x ^ 2 + 2x + 1 $ ,真正所有的关心是函数 $ x ^ 2 $ 。 因为如果你将证明 $ x ^ 2=oomega(xlogx)$ 然后添加 $ 2x + 1 $ 不会破坏证明,因为 $ x ^ 2 $ 是多项式的大于 $ 2x + 1 $ ,所以我们只能查看 $ x ^ 2 $ 。< / p>

(我将使用 $ n $ 而不是 $ x $ ,因为这是我的熟悉但对于 $ x $ )完全相同, 所以现在我们想要证明的是 $$ n ^ 2=oomga(nlogn)$$

您只提供在等式中的侧面需要触发方程式,我们需要找到一个正面 $ c $ ,因此对于任何 $ n> 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.Constant $$ $$ 2.logarithmic $$ $$ 3.linear $$ $$ 4.linearithmic $$ $$ 5.polynomial $$ $$ 6.exponential $$

(您可以在此处阅读更多信息: https://adrianmejia.com/mest-popular-algorithms-time-pomplexity-every-programmer-should-know-free-online-tutorial-course/ )

另一种方式看它是如果你会发现两个函数的划分的限制,让我们说我们会选择: $$ {f(n)\ over g(n)} $$

如果 $$ \ lim_ {n \ to \ infty} {f(n)\ over g(n)} \ lightarrow \ infty $$ 这意味着 $ f(n)$ $ g(n)$ < / p>

如果 $$ \ lim_ {n \ to \ infty} {f(n)\ over g(n)} \ lightarrow 0 $$ 这意味着 $ f(n)$ $ g(n)$ < / p>

最后一个选项(此方法的至少至少)是: $$ \ lim_ {n \ to \ infty} {f(n)\ over g(n)} \ lightarrow c $$ $ c \ gt 0 $ 时,这意味着两个功能都具有渐近相同的复杂性。

返回我们的功能,我们可以看到: $$ \ lim_ {n \ to \ infty} {n \ Over log(n)} $$

我们将使用横向规则并获得: $$ \ lim_ {n \ to \ infty} {1 \超过1 / n} \ lightarrow \ infty $$

我们现在可以看到 $ f(n)= n $ $ g(n)= log(n)$ 因此: $$ n=oomega(log(n))$$


我真的希望我尽可能清晰简单地解释,这只是英语不是我的母语语言,所以我提前安排了语法等的错误。


更新:我注意到你已经改变了原来的函数,现在它是 $ 3x ^ 3 + 2x + 1 $ ,但证明会是相同的,只需使用 $ n ^ 3 $ ,而不是在使用斜倚时仍然得到相同的结果。 这是因为,如果我们刚刚证明 $ n ^ 2 $ 是大于 $ log(n)$ < / span>比当然是 $ n ^ 3 $ ,它比 $ n ^ 2 $ 也比 $ log(n)更大。$

其他提示

最简单的方法是检查 $ \ lim_ {x \ to \ idty} \ frac {3x ^ 3 + 2x +1} {x \ log x}= +infty $ ,这是 $ 3x ^ 3 + 2x +1 \ in \ oomega(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 = +秒。 $$

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top