问题标签 [big-theta]

我设计了一个算法，我试图找到能够得出θ的上限和下限：

如您所见，它与 kruskal 算法非常相似。这里我的问题是我无法理解 find-set 的运行时间

对于另一部分，我有：

makeset O(v) 排序 O(ElogE) union O(1) 但是对于 find set 我不知道如何计算它？（你能告诉我计算的 union 运行时间是否为真）

我分析了 Kruskal 算法的运行时间，得出了 O(ElogE+Elogv+v)

我问我的教授，他说如果图形非常稀疏，有许多孤立的顶点，V 支配 E，如果不是，那么 E 支配 V，我不明白为什么？我可以举一个例子，其中图形不是稀疏的，但 V 仍然大于 E

谁能帮我消除这种困惑？

我必须找到以下函数的运行时间。

到目前为止，我相信运行时间T(n)=((n^2)-3)*(3*i*log(i)-4)但我无法得到第二部分的 n。我还发现它可以是最大值或大 O 表示法是((n^2)-3) (3 (n^2)*log(n^2))如果n^2是通过内部循环的每次迭代的 i 值，但事实并非如此，这基本上告诉我它可以写成O((n^4)*log(n^2))。为了找出大的 theta 值，我一直在尝试计算3*i*log(i)的平均值，以用作每次迭代的 i 值，但我似乎无法弄清楚。

有什么建议么？或者其他方法来解决这个问题？

给定 PHP 中的两个函数，比如说

如何检查函数 f(n) 是否在 PHP 中的 Ω(g(n))、Θ(g(n)) 或 O(g(n)) 中？

到目前为止我尝试了什么：

那不应该工作吗？

我有一个家庭作业问题，要求我们证明 2n+5 是 O(n²)。

这就是我试图解决它的方法：

我选择了 k = 1 并假设 n > 1 所以 f(n)/g(n) = (2n+5)/n² < (2n+5n)/n² = 7n/n² = 7/n

所以，因此 C 等于 7/n 因此，2n+5 <= (7/n)(n²) 所以 2n+5 <= 7n 这对于所有 n > 1 都是正确的。这就是为什么 2n+5 是 O( n²)。

我只是不确定这是否正确。我不是 100% 肯定，但如果有人能证实那会很棒。

此外，我对另一个要求简化为 theta 表示法的问题感到困惑：

(x ^4.2 )/(1+x²)。那只是 Θ(x ^2.2 )，因为我刚刚将它评估为无穷大吗？

另外，x³⋅lg(x) 我不知道从哪里开始。

提前致谢！

对于所有这些，我必须找出运行时间。

1.

2.

3.

4.

5.

6.

7.

8.

第一个我得到 O(n)，第四个我得到 O(n^2)。这些是正确的吗？我该怎么做其他人？我真的对第二个感到困惑。

答案可以用大 O 或大 theta 表示。

我将如何计算该算法的运行时间，以便将来可以解决类似的问题？

对于输入大小 n 满足递归关系（对于 n>= 1）

给定大 theta：

所以这就是我的想法..不确定是否正确：

第一个 for 循环将运行 n 次迭代。然后第一个 for 循环中的 for for 循环也将运行 n 次迭代，给出 O(n^2)。

对于 else 语句，while 循环将运行 n 次迭代，而 k = k/ 2 将运行 logn 时间，给出 O(nlogn)。那么整个事情看起来像 n^2 + nlogn 并且通过更长的运行时间，答案将是 theta n^2 ？

_{令 T 为左子树为 T L}且右子树为 T _R的 AVL 树。让我们|T _L | 和 |T _R | 分别为左右子树的节点数。

我需要证明 |T _R | ≠ Θ(|T _R |) 反之亦然，但我不知道怎么做。我认为这与一棵树是完整的 AVL 树而另一棵树是最小的 AVL 树（斐波那契树）的情况有关，但我不知道从那里该怎么做。

鉴于 f(n) ∈ Ѳ(g(n)); 你如何证明 2^(f(n)) ∈ Ѳ(2^(g(n)))？我尝试过使用大 theta 的限制并使用第一原则，但没有运气。请帮忙