问题标签 [big-theta]

我正在攻读计算机科学学位，在课堂上我们使用 big-theta 表示法比 big-O 表示法更频繁。尽管在阅读有关算法及其运行时间的文章时，我几乎找不到任何地方的大θ符号。在大多数书籍和文章中，为什么不使用 theta 表示法以更合适的方式指示算法运行时间的最坏情况？

我在 geeksforgeeks.org 上发现了一些我似乎无法理解的问题（#1 和 #3）。我希望有人可以为我澄清答案：

澄清是真/有效还是假

1.快速排序的时间复杂度是Θ(n^2)

我的回答是对的，但它是错的，为什么？如果快速排序的时间复杂度为 O(n^2) 并且我们知道 Θ(g(n))={f(n) 其中 c1*g(n) <= f(n) <=c2*g(n ) 并且 n >= n0} 那么这是否证明它是正确的，因为 c2*g(n) 作为上限可以等于 f(n)？

2.快速排序的时间复杂度是 O(n^2) - true

3.所有计算机算法的时间复杂度可以写成Ω(1)

这是真的，但我不明白为什么这是真的。假设我们在第一个元素上找到了我们正在寻找的东西，搜索算法可以具有 Ω(1) 的下限，但这对于所有计算机算法（例如最坏情况为 O(n^2) 的插入排序算法来说如何成立)?

链接： http ://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/

我想了解更多关于Big-O的信息，并找到了以下信息：

'如果f(x) = O(g(x))的增长率f(x)渐近小于或等于g(x)'

在这种情况下渐近意味着什么？我也很难理解为什么 Big-Theta 不依赖于我们使用的计算机？谁能提供有关这两个问题的更多信息？

我有一个程序：

我的问题是 - 我知道 while 循环运行log(n)次数，但我不确定整个程序运行了多少次？在此先感谢您的时间！

我有一个关于涉及递归的伪代码算法分析问题的问题。

对于那些不知道的人，算法分析通常是指找出函数运行所需时间的顺序。举个简单的例子，如果一个函数有 2 个从 1 到 n 的嵌套 while 循环，则该函数将花费大约 n^2 时间。这对于确定程序运行的估计时间非常有用。希望这是有道理的。

这是一个涉及递归的有趣问题。让我们从代码开始：

这是一个有趣的问题，因为您必须仔细考虑 k 的可能性以及 k 是随机选择的事实。

让我们取 n = 100。那么，k 的最坏可能值是多少（最坏的意思是导致程序运行时间最长的值）？一开始可能会认为 k=100 将是最差的值，因为由于从 R1 调用的 n-3 的 n 的数量很少，这将导致两个递归运行的次数最多。R1 将被 n=97 击中，现在 R1 或 R2 在随后的递归中被击中的可能性更大（请记住，每次程序运行时随机选择 k）。在随后的大规模递归循环的每一级，如果不是在循环的每一级都命中的话，它们中的至少一个很可能会被命中。

但是，这只会导致其中一个递归运行，而另一个被忽略。也许另一个最坏的情况是 k = 50，恰好是 n 的一半，并且是偶数。然后，R1 和 R2 在第一次贯穿时都被击中。这不仅立即花费了两倍的时间，而且现在两个递归都在运行，因此在随后的循环中遇到进一步递归的可能性是两倍。例如再次取 n = 100 和 k = 50。然后 R1 和 R2 分别被击中 n=97 和 n=91。然而，现在我们有 2 个递归循环，因此进一步递归调用被命中的可能性是两倍（想想：如果在那些 R1/R2 递归调用中，对于随机选择，K1 = 97 和 K2 = 40 会发生什么情况从原始运行中调用？）。

这里的时间安排最坏的情况是什么？什么是估计的（使用概率，即 R1 = 1/2 而 R2 = 1/2 的机会）渐近运行时间？

谁能帮我理解 Is 2^(n^2 )=Θ(2^(n^3 )) ？如果也为此提供证据，那就太好了。根据我的观点，这不需要相等。

我找了很多天，我尝试了很多递归算法示例，但我找不到任何具有Θ( log n )运行时间的算法。
你知道java中有什么递归算法吗T(n) = Θ( log n )？T(n)表示算法基本操作执行次数的函数在哪里。
非常感谢任何帮助。
谢谢！

我分析了一个算法，运行时间我得到了 Θ(n ^3/2 )。现在我想将它与 Θ(n log n) 进行比较，看看它是渐近更快还是更慢，因为我这样做了：

Θ(n ^3/2 ) = Θ(n · n ^1/2 )

如果我们比较它们，我们会发现我们需要比较 n ^1/2和 log n。我检查了两者的增长，发现对于较大的数字，n ^1/2的增长超过 log n。我可以说 n ^3/2渐近地比log n 慢吗？

我设计了一个算法来将 10 的幂转换为二进制，假设 n 是 2 的幂。我使用高斯方法来使用这种好方法的快速运行时间。为此，我将 n 除以 2 并将其发送到 Gauess 方法，如下所示：

很显然，Guess 方法会先分而治之，再结合。最后，我们将数字更改为二进制。现在我的问题是关于算法的运行时间：我的理解是，由于 Guess 运行时间是 Theta(n^log3(base2)) 我们可以说这个算法的运行时间也是一样的，因为大部分工作已经完成通过猜测。另一方面，当我尝试找到递归关系时，我想出了 T(n/2)+O(n)，即 Theta(n) 那么哪个是正确的？我在计算中是否遗漏了某事我会矛盾吗？

我可以通过证明它只需要 5 次乘法来证明 2 * 2 的矩阵 A 的平方是 O(n^log5)。到现在为止我没有问题，但是当我想解释为什么我们不能将它推广到其他平方情况（不同的 n*n 大小）的两个原因之后，我可以想出一个如下：

我能想出的第一个原因是我将例如 3*3 矩阵与自身相乘并得出结论，它至少有 6 次乘法，因此它的运行时间至少为 O(n^log6)，其中 n^epsalon 大于 O( n^log5) 所以它比较慢，我们不能将 O(n^log5) 推广到所有情况。现在我需要另一个原因，但我不知道如何解释第二个原因有人可以帮忙吗（我只需要一个提示就可以提出一个想法）？