问题标签 [big-theta]

我想计算这个嵌套 for 循环的 theta 复杂度：

我会说它是 n^3，但我认为这是不正确的，因为每个 for 循环都不会从 1 变为 n。我做了一些测试：

n = 5 -> 10

10 -> 120

30 -> 4060

50 -> 19600

所以它必须在n^2和n^3之间。我尝试了求和公式等，但我的结果太高了。虽然是 n^2 log(n)，但这也是错误的......

我目前正在学习算法的期末考试。这不是家庭作业问题，而是来自旧的期末考试。

很明显，log log n 比 log n 小很多，因此微不足道。但是我怎样才能正式地展示它呢？我熟悉限制和 L'hopital，所以如果您能告诉我如何使用这种方法，我将不胜感激。

我对 Big Theta ( Θ ) 运行时复杂度的概念不熟悉，

我有以下递归关系要分析，

T(n) = 2T(n/3) + 5n ² 我得到Θ( ² )

T(n) = T(n/4) + n ⁴ 我得到Θ(n ⁴ )

请验证我的回答。

考虑以下一段 C++ 代码：

通常，在分析一段代码的时间复杂度时，我们会确定内循环做了多少工作，然后将其乘以外循环运行的次数。但是，在这种情况下，内部循环完成的工作量因迭代而异，因为正在构建的字符串越来越长。

您将如何分析此代码以获得大 O 时间复杂度？

我被告知

1 + 8 + 27 + 64 + ... + (√n) ³ = Θ(n ² )

为什么会这样？

所以我正在阅读我的笔记，但我并没有真正理解这部分：

定义 f, s 为一个区间的开始和结束时间。按完成时间对所有间隔进行排序。所以假设我们有一组区间 I_1, ..., I_n 并定义 pred[i] = 最大索引 j 使得 f_j <= s_i。（所以基本上在 i 之前的下一个最接近的间隔不与 i 重叠）。

现在我们要为 n 中的所有 I_i 求解所有 pred[i]。为什么这个 theta(n log n) 的运行时间是？我认为，在最坏的情况下，所有 I_1，...，I_(i-1) 都与 I_i 重叠；因此将进行 n - 1 次比较，然后进行 n - 2 次比较，依此类推。最好的情况是没有一个区间重叠，并且 pred(i) 对每个区间进行 1 次比较。我不确定为什么“排序和计算 pred[i] 值”的运行时是 theta(n logn)。

如果是这样，你能提供明确的例子吗？我知道像快速排序这样的算法可以有 O(n log n) 的预期运行时间，但在更坏的情况下是 O(n^2)。我假设如果预期/最坏情况的相同原则适用于 theta，那么上述问题可能是错误的。了解 theta 的工作原理将帮助我理解 theta 和 big-O 之间的关系。

我正在尝试学习如何找到各种算法的大θ界限，但我很难理解如何做到这一点，即使在阅读了这里的一些问题以及关于该主题的讲座和教科书之后也是如此。所以例如

我想根据 n（数组 a 中的索引数）计算出加法数的大θ界限。我可以看到外循环本身经历了 log(n) 迭代，但我不知道如何表达内循环中发生的事情。有没有人有解释，甚至可能有我可以尝试咨询的资源？

我正在尝试从最大到最小订购这些不同的大 theta 值：

并且有些值是等价的。特别是，我想知道常数项是否使一个大θ值大于没有常数项的相同大θ项（例如，这两个值是否等效：Θ（22n）和Θ（n）？）。

给定f(x, y)和g(n)：

什么是 Big Theta 界限g(n)？

我推断由于 x == y，条件 inf(x, y)永远不会为真，因此 2 个递归调用将决定复杂性。

仅考虑f(x - 1, y - 1)：需要 n 次递归调用才能到达基本情况，每个调用都分支到另一个f(x - 1, y - 1)。在这一点上，我不知道如何进行。

（答案是 Θ(2 ⁿ )。）