问题标签 [big-theta]

除了 Big O 之外，我无法理解时间复杂度。在这个例子中：

是 f θ(g) 吗？我猜它是 θ(g) 因为你可以找到一个常数 c1 和 c2 将允许 c1*g(n) 成为 f(n) 的上限，而 c2*g(n) 将成为下限.

我正在解决一个来自 CLRS 的问题，我们需要证明 (ceil(lg lg n))！是多项式有界的。

现在如果我能证明 theta(lg n)=o(n)

我面临的唯一问题是证明theta(lg n)=o(n)。请帮忙！

有人可以给我一个非数学的（用文字而不是公式来回答）Big O，Big Omega和Big Theta之间的确切区别是什么？我查看了很多资源，但仍然非常混乱。我知道 Big O 是上限，Omega 是下限，而 Theta 在上限和下限内。但这究竟是什么意思？

This maybe a trivial/ mathematical concept that I cant seem to work my head around. So if the processing time T(n) of a certain algorithm is both Ω(n) and O(n^3), how can i prove that the T(n) is Θ(n^2) is either correct or not?

是否有任何算法 A，使得对于 A 的一组最坏情况实例 S，A 具有不同的最坏情况上限和最坏情况下限？此外，对于某些输入集，它应该具有不同的最佳情况界限，不等于任何最坏情况界限。

例如，假设 H 是一种假设算法，使得 H 具有最坏情况上限 Ο(n^3)、最坏情况下限 Ω(n^2) 和最佳情况运行时间 Θ(n)。

让我知道上述情况实际上是否有意义？

谢谢 ：）

我正在尝试分析该算法的最坏情况增长顺序作为 N 的函数：

我正在尝试total++通过查看内部和外部循环来分析线路将运行多少次。内部循环应该运行(N^2)/2时间。外环我不知道。谁能指出我正确的方向？

So I have a loop embedded inside a loop here:

n is a power of 2

I'm trying to understand how to calculate the Time complexity of this however I'm having trouble figuring out the Big-theta notation for this.

I know that the the outter loop runs in O(n) time, but I'm not sure about the inner loop due to the b+=a. I know that If I had the time for both loops, I could multiply them to get the Big-theta time of the function, but I'm not sure what the inner loop is running at.

When I plug in sample n's (ie. 2, 4, 8, 16), then the inner loop is looped 3, 9, 24, 61 times, respectively. I don't see how these values correlate.

Edit:

Ok I see what you are saying, but I'm trying to compare it to this function. What would the time for this function be? Then i can compare the speed of the two:

我明白为什么在链式哈希表中不成功的搜索平均具有 Θ(1+(n/m)) 的时间复杂度，因为在不成功的搜索中检查的元素的预期数量是 (n/m)，并且总所需时间（包括计算 hashFunction(key) 的时间）为 Θ(1+(n/m))。但是为什么成功的搜索是一样的呢？

我编写了一个遍历非二叉树结构的递归算法。该结构由目录或文件组成。

该算法采用输入目录 ( curDirectory) 并首先遍历树深度。当它到达分支的底部时，它会查找文件并打印一些信息。然后它返回一个级别，查找文件并打印内容，等等。我们不知道目录中子目录或文件的数量。

如何分析该算法的最坏情况和平均情况时间？

是 2^n = Θ(4^n) 吗？

我很确定 2^n 不在 Ω(4^n) 中，因此不在 Θ(4^n) 中，但我的大学导师说它是。这让我很困惑，我无法通过谷歌找到明确的答案。