问题标签 [big-theta]

我有一个为客户端生成 JSON 的服务器端程序。我的一些同事建议使用 zip/gzip 压缩来减少通过网络发送的数据量。但是，当针对我的一条普通 JSON 消息进行测试时，它们实际上都增加了发送的数据量。直到我发送了一个异常大的回复，拉链才开始起作用并且很有用。

所以我开始研究 stackoverflow，最终找到了LZO，它在测试时完全符合我的要求。但是，我似乎找不到算法运行时间的文档，而且我还不够好，无法坐下来自己研究代码：)

tl;博士？LZO 的运行时间？

当数组通过重复附加 19 增长时，选择排序算法的 Big-Theta (T) 表示法的最佳情况和最坏情况复杂度是多少？

例如：

等等。n用于表示数组的长度。

所以我们将相同的数字添加到数组的末尾，但这个数字也恰好是最大的数字，所以它会留在数组的末尾。这是否意味着它真的对效率没有任何影响？我很困惑。

有人可以为我提供一个如何计算大 theta 的实时示例。

大 theta 是否类似于平均情况（最小-最大）/2？

我的意思是（最短时间 - 大 O）/2

如果我错了，请纠正我，谢谢

我已经解决了运行时间为 Θ(2^n)、指数时间的递归关系。对于相同的递归关系，我如何找到 Ω 和 O。

我想如果它是 Θ(2^n)，它也应该是 O(2^n)，对吗？我如何找到 Ω 的下限？

我尝试解决递归关系：

T(n) = 2T(n-1) + C。

我试图在双嵌套 for 循环上确定 Big Theta 运行时间，这比常规的 Θ(n ² ) 双循环要花哨一些。

我知道我可以说它是 O(n ² )，但我喜欢 Θ 格式。

我有一个关于几何级数的问题。为什么是

1 + c + c ² + ... + c ⁿ = Θ(c ⁿ )

当 c > 1 时？^{我理解为什么如果 c = 1 是 Θ( n} )，如果 c < 1 是 Θ(1)，但我就是不明白为什么如果 c>1 是 Θ(cn)。

谢谢！

x = x + 1用 n 表示语句在下面的段中执行的次数的 Θ 表示法：

我知道它i的增长率为O(3^k)，但我不确定如何Θ获得n.

我有作业问题：

1. 求语句 x = x + 1 执行次数的 theta 表示法。（10分）。

这就是我所做的：

好的，首先让我们让它更容易。我们将首先找到增长的顺序：

具有增长顺序的O(log(n)) 实际上对数基数 2

另一个内部 for 循环将执行 n 次，因此算法应该是有序的：

O(log(n)*n)

我感到困惑的部分是我应该找到 theta 符号而不是 big-O。我知道 theta 表示法假设将函数限制在上限和下限。正确答案会是Theta(log(n)*n)？

我在这个链接中找到了答案，但我不知道你是如何得到这个答案的。为什么他们声称答案是 Theta(n) ？

我有作业问题：

令 T(n) 表示语句 x = x + 1 在算法中执行的次数

求 x = x + 1 执行次数的 theta 表示法。（10分）。

这是我所做的：

我们完成了以下工作量： - 基本情况检查的恒定工作量 - O(n) 工作来计算数字 - 递归调用一半大小的东西所需的工作

我们可以将其表示为递归关系： T(1) = 1 T(n) = n + T(n/2)

让我们看看这是什么样子。我们可以通过注意到

我们可以在这里开始看到一种模式。如果我们将 T(n/2) 位扩展 k 次，我们得到： T(n)=n+n/2+n/4+⋯+n/2^k +T(n/2^k )

最终，当这种情况发生时停止n/2^k =1 ，我们有： T(n)=n+n/2+n/4+n/8+⋯+1

这意味着什么？有趣的是，这个总和等于 2n+1，因为总和n+ n/2 + n/4 + n/8 +…. = 2n. 因此第一个函数是O(n)

由于@templatetypedef回答了这个问题，我得到了答案

知道我对 theta 表示法感到困惑。答案会一样吗？我知道 theta 表示法应该将函数与下限和上限绑定。这意味着我需要发挥作用？

我不是在这里寻找答案，而是如何找到以下问题的最坏/最佳情况（以 theta 表示法）；for 循环通常是 (theta(n))，这将是最好和最坏的情况，但我认为这里发生了其他事情。任何帮助，将不胜感激。

编辑答案：

由于 return x + n 常数 (theta(1)) 将是最好的。

最佳 = (theta(1)) 最差 = (theta(n))