问题标签 [big-theta]

我正在阅读算法简介第 3 版（Cormen 和 Rivest），在第 69 页的“强力解决方案”中，他们指出 n 选择 2 = Theta (n^2)。我认为它会在 Theta (n!) 中。为什么 n 选择 2 紧密绑定到 n 平方？谢谢！

这是代码：

我的问题是我无法确定这个for循环的Θ，
我认为它是平方根（n）但是有一个名为平方根n的顺序吗？

我的答案是：
Theta(sqrt(n)) 因为这个循环

i * i <= n两边取 sqrt

i <= sqrt(n)

如果我错了，请纠正我！

今天我们教授提到O(n^2)和Θ(n^2)是一样的。

我不明白对此的解释，我在互联网上找不到任何东西。请有人向我解释一下吗？

非常感谢。

大θ的运行时间是多少？

我最好的猜测，在黑暗中拍摄：我总是看到嵌套的for循环是O（n ^ k），其中k是循环数，所以循环是O（n ^ 4），然后我会乘以O (1) 恒定时间？这一切会是什么？

假设我们有一个数组，我们知道所有元素都是 0...2n 并且没有排序。

如果我们使用复杂度为 O(n+k) 的桶排序算法，其中 k 是元素的范围，在本例中为 2n，那么对这个数组进行排序的复杂度是否会是 Θ(n)？

我的基本原理是运行时间为 O(n + 2n)，与 O(3n) 相同，并且由于 3 只是一个系数，因此复杂度为 Θ(n)。

这个分析准确吗？

我正在开发一些占用 O(log^3 n) 的算法。（注意：将 O 视为 Big Theta，尽管 Big O 也可以）

我不确定，而 O(log^3 n)，甚至 O(log^2 n)，被认为与 O(n log n) 一样复杂/多/少/同样复杂。

如果我要立即遵守规则，我会说 O(n log n) 是更复杂的规则，但我仍然不知道为什么或如何。

我做了一些研究，但我无法找到这个问题的答案。

非常感谢你。

如果算法时间复杂度为 theta(n^2)，是否有可能对于一个输入它会在 O(n) 中运行？根据 theta 的定义，似乎没有输入将在 O(n) 中运行。但是有人说这是可能的。

我真的想不出在 theta(n^2) 中运行的算法会有一个可能在 O(n) 中运行的输入。

如果是真的，你能给我解释一下并举个例子吗？

非常感谢！

我正在尝试在 Big-Theta(n^m) 中实现具有时间复杂度的算法，n 和 m 是自然数。

我的第一个解决方案：

我的第二个解决方案：

当我分析我的第二个解决方案时，称为algo(n,m,m)，我得到T(i) = n * T(i-1), i > 0. 随着 T(0) = 恒定时间，我得到T(i) = n^m. 所以我认为我的第二个解决方案是正确的，但我不知道我的第一个解决方案有什么问题。

假设我们从一个文本文件开始，例如：

该算法将是典型的算法，您使用前缀构建霍夫曼树，在遍历树时读取编码位，直到到达叶子，然后在该叶子处返回字符。

有人可以解释我如何确定运行时间和空间复杂度吗？

它是 f(n)=theta(h(n)) 因为 theta 是传递的。但是谁能解释为什么 h(n)=theta(f(n))。