算法的订单功能

-1

有人可以帮我理解这个问题吗？我可能会在明天的考试中拿到它，但我无法在互联网或我的演讲中找到类似的问题。算法的订单功能

enter image description here

2013-01-20 a1204773

你试过什么？你卡在哪里？ – hugomg

首先你需要将每个函数表示为Theta(something)。
例如，对于第一个：Theta((1-n)(n^3-17)) = Theta(n^4 + ...) = Theta(n^4)。对于第二个：Theta(30+log(n^9)) = Theta(30 + 9logn) = Theta(logn)。
这些是排序为g1, g2，因为n^4 = Omega(logn)。
依此类推。
对于排序：说g1 = Omega(g2)意味着g1增长至少与g2一样快，那就是我们正在定义一个下限。所以，把他们从最糟糕的（最慢的，最快的增长）中分类到最好的（注意：奇怪的是练习想要“第一个是最好的”，但欧米茄的定义毫无疑问）。
顺便说一句：如果你想要更正式，这里是欧米茄符号的定义：
f = Omega(g) iff exist c and n0 > 0 such that forall n >= n0 we have 0 <= c*g(n) <= f(n)（言语：f增长至少与g一样快）。

来源

2013-01-20 14:53:22 Simon

我没有得到排序...你能解释一下更多细节吗？ – a1204773

@Loclip编辑。只需用他们的成长来分类。如果您不确定其中一些人的比较情况，请使用wolframalpha来绘制它们并查看哪一个增长得更快。 – Simon

但是n^4比logn增长得快得多，所以我们怎么说'n^4 = Omega（logn）？' – a1204773

首先，你必须通过规定一定的生长级的各项功能，例如来计算西塔符号1，log（n），n，n log（n）等等。要做到这一点，当然要扩展这些功能。拥有每个功能的增长级别，您必须按照其良好顺序排列它们。最后，你必须把这些函数放到关系中，比如g1 = omega（g2）。因此，只要记住函数t（n）被称为在欧米伽（g（n））中，如果t（n）的范围低于g（n）的某个倍数，例如。 n³> =n²，因此n³是欧米茄（n²）的元素。这也可以写成n³= omega（n²）

来源

2013-01-20 14:33:24 windler

我究竟如何计算theta？那是对的吗？一世。 Θ（n^3）ii。 Θ（logn）iii。 Θ（3^n）iv。 Θ（n）v。Θ（n^2）vi。 Θ（n^9）vii。 Θ（nlogn）viii。 1 – a1204773

@Loclip 1和5不正确。他们是n^4和n^3。 – Simon

@Simon哦我没有做乘法确定..谢谢 – a1204773

对于theta，this answer和that one总结了什么是你的问题。功能，您可以找哪家克使得（比如说˚F是你上面的8个功能之一）

渐近上述˚F（称为O(g(n))）乘以一个常数范围

乘以（通常）另一恒定边界渐近下面˚F（称为omega(g(n))

例如，对于iv：10^5n,Θ(n)适合，因为您可以很容易地找到两个常量，其中k1.n界限低于10^5n和k2.n渐近地将其限制在上面。（这里f是O(n)和Omega(n)如f，iv.是一个容易的）。

来源

2013-01-20 14:54:44

你要明白，所有大O和大欧米茄和大THETA申请糟糕/最佳/平均情况

一些功能：大O - > O（..）是上限此功能将永远不会超过..例如为更高的价值大欧米茄 - >是更低的磅功能永远不会低于它.e。克在小的值大theta是这样的：有2个常数，使得：大的ω* C <大西塔<大O * C2

所以要你的样品： ⅰ）的阶数n^4其大欧米茄和O（n^+ n）。 viii）它的常数使得奥比格O和大奥米加相同。因此大的Theta相同

来源

2013-01-20 15:07:59 blackmath

算法的订单功能

回答

相关问题