大欧米茄和大Theta
像f(n)=3n^2+2这样的函数是O( n^2 )，因为n^2是函数中的最大指数。然而，函数1f(n)= n^31不是O(n^2)，因为最大指数是3，而不是2。
因此，为了在大欧米茄或大Theta上做出这样的猜测，我们应该在函数中寻找什么？我们能做一些类似于上面对大O符号所做的事情吗？
例如，假设问题要求我们找到函数f(n)= 3n^2 +1的Big或Big。f(n)= O(n)，Big Omega(n)还是Big Theta(n)？如果我要对这个函数是否是大O(n)进行有教养的猜测，我会说不(因为这个函数的最大指数是2，而不是1)。我会用归纳来证明这一点。
那么，我们能做一些类似于我们在第一个例子中用Big符号所做的事情吗？我应该在函数中寻找什么来猜测大欧米茄和Theta将是什么，并确定“受过教育的猜测”是否正确？
回答 2
Stack Overflow用户
发布于 2017-11-28 22:00:35
你的例子使用多项式，所以我假设。
- 如果k大于或等于多项式的阶数，则多项式为O(n^k)。
- 如果k小于或等于多项式的阶数，则多项式为Omega(n^k)。
- 如果同时为O(n^k)和Omega(n^k)，则多项式为Theta(n^k)。
Stack Overflow用户
发布于 2020-03-06 21:18:01
那么，我们能做一些类似于我们在第一个例子中用Big符号所做的事情吗？
如果你在寻找能让你眼球的东西，如果某个东西是大欧米茄，大O，或者是多项式的大Theta，你可以使用多项式阶定理(几乎是Patrick87所说的)。
基本上，多项式阶定理允许你只看最高阶项，并使用它作为你想要的大O，大欧米茄和大Theta的界。
我应该在函数中寻找什么来猜测大欧米茄和Theta将是什么，并确定“受过教育的猜测”是否正确？
理想情况下，您的函数将是一个多项式，因为这将使问题更加简单。但是，它也可以是对数函数或指数函数。
要确定“受过教育的猜测”是否正确，您必须首先了解您要寻找的是哪种运行时。扪心自问:我在寻找这个算法最坏的运行时间吗？还是我在寻找这个算法的最佳运行时间？还是我在寻找算法的一般运行时间？
如果你看算法最坏的运行时间，你可以简单地用多项式阶定理(如果是多项式函数)或通过一个例子来证明Big。然而，您必须分析算法，才能证明大O和大Theta。
如果您正在查看算法的最佳运行时间，您可以使用一个例子或通过多项式阶定理(如果是多项式)来证明Big。然而，大欧米茄和大Theta只能通过分析该算法才能得到证明。
基本上，您只能通过一个例子证明算法的最佳运行时间和最坏情况运行时间的信息最少的界限。
为了证明算法的一般运行时间，您必须确保给出的算法运行时间的函数是用于所有输入的--在这种情况下，一个例子是不够的。当你没有一个用于所有输入的函数时，你必须分析算法来证明这三个输入中的任何一个(Big，Big，Big )对于算法的所有输入。
https://stackoverflow.com/questions/47503526
复制相似问题
腾讯云开发者
