1

我已经使用主定理来解决递归关系。我已经把它归结为Θ(3n 2 -9n)。这是否等于Θ(n 2 )？我有另一个递归，其解决方案是Θ(2n 3 - 100 2 )。在 BigTheta 表示法中，您总是只使用最大的项吗？所以我的第二个是Θ(n 3 )？在第二种情况下，似乎100n 2会更重要。那么我丢弃它有关系吗？

有什么建议么？

4

2 回答 2

2

是的。你的假设是正确的。第一个是Θ(n 2 )，第二个是Θ(n 3 )。当您使用Θ表示法时，您只需要最大的项。

如果您的第二次重复考虑n = 1000, 那么n 3 = 1000000000。其中100n 2只是100000000。随着n值的增加，n 3变得比100n 2越来越占优势。

出于理论目的，您不需要考虑常数，它可能有多大。但实际应用程序可能更喜欢具有小常数的算法，即使复杂度很高。例如，如果n的值不是很大，则使用复杂度为 0.01n 3的算法可能比使用复杂度为10000n 2的算法更好。

于 2013-04-21T17:03:24.040 回答
0

如果我们有函数 f(n) = 3n^2-9n ，可以忽略低阶项和成本，我们考虑高阶项，因为它们在函数的增长中起主要作用。通过仅考虑高阶项，我们可以很容易地找到上界，这是示例。

                  f(n)= 3n^2-9n
  For all sufficient large value of n>=1,
                                      3n^2<=3n^2 
                           and       -9n  <= n^2

                     thus, f(n)=3n^2 -9n <= 3n^2 + n^2
                                         <= 4n^2

  *The upper bound of f(n) is 4n^2 , that means for all sufficient large 
  value of n>=1, the value of f(n) wouldn't be greater than 4n^2.* 

                  therefore,           f(n)= Θ(n^2)  where c=4 and n0=1

在此处输入图像描述

我们可以通过忽略方程 f(n)= 3n^2-9n 中的低阶项和常数来直接找到上界，结果将是相同的 Θ(n^2)

于 2013-04-21T17:50:46.747 回答