在计算Big（oh）时，g（n）的上限从哪里来？ [英] While calculating Big(oh), Where from upper bound g(n) comes?
问题描述
例如我有一个程序的f（N）= 5N +3。我想知道此功能的主要功能（哦）。我们说高阶项O（N）。
For example i have f(N) = 5N +3 from a program. I want to know what is the big (oh) of this function. we say higher order term O(N).
-
这是通过删除低阶项和常量来找到任何程序的大（oh）的正确方法吗？
Is this correct method to find big(oh) of any program by dropping lower orders terms and constants?
如果仅通过查看复杂度函数5N + 3得出O（N）。那么，此公式F（N）< = C * G（N）的目的是什么？
If we got O(N) by simply looking on that complexity function 5N+3. then, what is the purpose of this formula F(N) <= C* G(N)?
我知道，该公式仅用于比较两个功能。我的问题是
i got to know that, this formula is just for comparing two functions. my question is,
在此公式中，F（N）< = C * G（N），我有F（N）= 5N + 3 ，但是该上限G（N）是多少？它来自哪里？我们将从哪里拿走？
In this formula, F(N) <= C* G(N), i have F(N) = 5N+3, but what is this upper bound G(N)? Where it comes from? where from will we take it?
我研究了许多书籍和许多帖子，但我仍然面临困惑。
i have studied many books, and many posts, but i am still facing confusions.
推荐答案
Q：这是通过删除来查找任何程序的大方法的正确方法吗？
低阶术语和常量？
Q: Is this correct method to find big(oh) of any program by dropping lower orders terms and constants?
是的，大多数在检验时间复杂度方面至少有经验的人都使用这种方法
Yes, most people who have at least some experience with examining time complexities use this method.
Q：如果我们仅通过看复杂度函数5N + 3得到O（N）。那么
，此公式F（N）< = C * G（N）的目的是什么？
Q: If we got O(N) by simply looking on that complexity function 5N+3. then, what is the purpose of this formula F(N) <= C* G(N)?
正式证明您正确估计了某些算法的大哦。假设您有 F（N）= 5N ^ 2 + 10 ，并且（错误地）得出结论，此示例的大复杂度为 O（ N）。通过使用此公式，您可以很快发现这是不正确的，因为不存在常量 C ，这样对于 N 持有 5N ^ 2 + 10< = C * N 。这意味着 C> = 5N + 10 / N ，但是无论您选择多大的常量 C ，总是 N 大于此常数，因此不等式不成立。
To formally prove that you correctly estimated big-oh for certain algorithm. Imagine that you have F(N) = 5N^2 + 10 and (incorrectly) conclude that the big-oh complexity for this example is O(N). By using this formula you can quickly see that this is not true because there does not exist constant C such that for large values of N holds 5N^2 + 10 <= C * N. This would imply C >= 5N + 10/N, but no matter how large constant C you choose, there is always N larger than this constant, so this inequality does not hold.
Q：在此公式中，F（N）< = C * G（N），我有F（N）= 5N + 3，但这
的上限G（ N）？它来自哪里？我们将从哪里得到它？
Q: In this formula, F(N) <= C* G(N), i have F(N) = 5N+3, but what is this upper bound G(N)? Where it comes from? where from will we take it?
它来自检查 F（N），特别是找到其最高阶词。您应该掌握一些数学知识，以估计哪个功能比另一个功能增长得更快，首先请检查此有用的链接。复杂度有几类-常数，对数，多项式，指数。。但是，在大多数情况下，很容易找到任何函数的最高阶项。如果不确定，则始终可以绘制函数图或正式证明一个函数的增长快于另一个函数。例如，如果 F（N）= log（N ^ 3）+ sqrt（N）也许乍一看不清楚最高阶术语是什么，但是如果您对于N = 1、10和1000计算或绘制 log（N ^ 3）并为 sqrt（N）值，立即可以清楚地看到 sqrt（N）的增长速度更快，因此该函数的大哦是 O（sqrt（N））。
It comes from examining F(N), specifically by finding its highest order term. You should have some math knowledge to estimate which function grows faster than the other, for start check this useful link. There are several classes of complexities - constant, logarithmic, polynomial, exponential.. However, in most cases it is easy to find the highest order term for any function. If you are not sure, you can always plot a graph of a function or formally prove that one function grows faster than the other. For example, if F(N) = log(N^3) + sqrt(N) maybe it is not clear at first glance what's the highest order term, but if you calculate or plot log(N^3) for N = 1, 10 and 1000 and sqrt(N) for same values, it is immediately clear that sqrt(N) grows faster, so big-oh for this function is O(sqrt(N)).
这篇关于在计算Big（oh）时，g（n）的上限从哪里来？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
