-1

有人可以帮我理解这个问题吗？我明天的考试可能会有它，但我在互联网或我的讲座中找不到类似的问题。

在此处输入图像描述

4

4 回答 4

1

首先，您必须通过确定每个函数的增长类别来计算 Theta 符号，例如 eG 1、log(n)、n、n log(n) 等。为此，您当然必须扩展这些功能。拥有每个功能的增长类，您必须按照它们的优点对它们进行排序。最后，您必须将这些函数放入关系中，例如 g1 = omega(g2)。因此请记住，如果 t(n) 的下界为 g(n) 的某个倍数，则称函数 t(n) 位于 omega(g(n)) 中，eG n³ >= n² 因此 n³ 是omega(n²) 的元素。这也可以写成 n³ = omega(n²)

于 2013-01-20T14:33:24.983 回答
1

首先，您需要将每个函数表示为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，也就是说我们正在定义一个下限。因此，将它们从最差（最慢，增长最快）到最好（注意：练习想要“第一个到最可取”很奇怪，但欧米茄的定义毫无疑问）。
顺便说一句：如果你想更正式一点，这里是 Omega 符号的定义：（
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-20T14:53:22.693 回答
1

对于theta，这个答案和那个总结了您的问题中可以找到的内容。你能找到哪个g函数（比如f是你上面的 8 个函数之一）

  • 乘以渐近于f的常数边界（称为O(g(n))）
  • 乘以（通常）渐近低于f的另一个常数边界（称为omega(g(n))

例如，对于iv: 10^5n，Θ(n)适合，因为您可以很容易地找到两个常数，其中k1.n位于下方10^5n，k2.n位于上方，渐近。（这里f是O(n)和fOmega(n)一样，这很容易）。iv.

于 2013-01-20T14:54:44.917 回答
0

您需要了解所有大 O、Big Omega 和 Big theta 都适用于更差/最佳/平均情况

对于某些函数：Big O -> O(..) 是这个函数永远不会超过的上限.. 例如对于更高的值 Big Omega -> 是下磅函数永远不会低于它。例如在小值中 Big theta 是比如：有 2 个常数，这样：Big omega * c < Big Theta < Big O *c2

所以去你的样本：i）Big Omega和O（n ^ + n）的顺序为n ^ 4。viii) 它是常数，所以 Obig O 和大 Omega 相同.. 因此大 Theta 相同

于 2013-01-20T15:07:59.950 回答