问题标签 [big-theta]

有时我看到 Θ(n) 带有奇怪的 Θ 符号，中间有东西，有时只是 O(n)。只是懒惰打字，因为没有人知道如何输入这个符号，还是意味着不同的东西？

它要求指出函数所属的类 Big-Theta(g(n)) 并证明断言。

在这种情况下 f(n) = (n^2+1)^10

根据定义 f(n) E Big-Theta(g(n)) <=> c1*g(n) < f(n) < c2*g(n)，其中 c1 和 c2 是两个常数。

我知道对于这个特定的 f(n)，Big-Theta 是 g(n^20)，但我不知道谁来正确证明它。我想我需要操纵这种不平等，但我不知道如何

如果 f(n) 是 Θ(g(n))，那么函数 2 ^f(n)是否总是 Θ(2 ^g(n) )？为什么或者为什么不？

完全披露：这是一个家庭作业问题。老实说，当它看起来如此简单时，它却躲避了我这么久，我真的有点害怕。

好的，问题是，f(n) = n^2*log(n), g(n) = n^2.1。f 在 theta(g) 中吗？

我只需要想出常数 c ₁ , c ₂以便超过某个 n ₀ , f(n) <= c ₁ g(n) <= c ₂ f(n)。但我什至不确定 f 是否在 theta(g) 中。我很困惑。

我正在学习使用麻省理工学院课件和 CLRS 书《算法简介》。

我目前正在尝试解决复发问题（从第 107 页开始）

T(n) = 2T(n/2) + n ⁴

如果我制作一个递归树，我会得到：

0级：n ⁴

1 级 2(n/2) ⁴

2 级 4(n/4) ⁴

3 级 8(n/8) ⁴

这棵树有 lg(n) 个级别。因此我认为复发应该是

T(n) = Θ(n ⁴ lg n)

但是，如果我使用主定理，我明白了

T(n) = Θ(n ⁴ )

显然，这两个都不对。哪一个是正确的？我的推理哪里出错了？

据我了解，第一行是操作，第二行是(i+1)操作，第三行是(i-1)操作，第四行是n操作。这是否意味着运行时间将是1 + (i+1)(i-1) + n？只是这些最后的步骤让我感到困惑。

如何决定表达算法的时间复杂度？

O(n)我们应该选择用或来表达时间复杂度theta(n)吗？因为函数f(n)可以表示为Big-Oh(g(n))或theta (g(n))。

我们什么时候选择 big-oh 而不是 theta ？

我试图弄清楚f(n)=n^(logb(n))是 inTheta(n^k)并因此增长多项式或 inTheta(k^n)并因此呈指数增长。

首先我试图简化函数： f(n) = n^(logb(n)) = n^(log(n)/log(b)) = n^((1/log(b))*log(n))因为1/log(b)是常数，所以我们得到f(n)=n^log(n).

但现在我被困住了。我的猜测是f(n)指数增长Theta(n^log(n))甚至超指数增长，因为指数log(n)也在增长。

我有两个功能：

• f(n) = 2;
• g(n) = 10 ^ 100;

我必须证明 f(n) = BigTheta(g(n)) 是否合理。

我的猜测是 f(n) 是 BigTheta(g(n))，因为这两个函数都是常数（这意味着函数是成比例的），但是我的老师坚持认为我错了。

我对吗？有什么办法可以让我的案子休息吗？对不起，如果这听起来像一个菜鸟问题！谢谢。

我知道这个循环是 O(n^2) 但什么是 Big-Omega 和 Big-Theta？在这种情况下，您如何计算它们？