复杂性-确定增长顺序 [英] Complexity - determining the order of growth

问题描述

我了解大部分情况下如何计算函数的复杂度。确定数学函数的增长顺序也是如此。 [我可能不太理解我的理解，这就是为什么我可能会问这个。]例如：

I understand how to calculate a function's complexity for the most part. The same goes for determining the order of growth for a mathematical function. [I probably don't understand it as much as I think I do, which is why I'm probably asking this.] For instance:

an ^ 3 + bn ^ 2 + cn + d 可以用big-o表示为O（n ^ 3），因为足够大的 n b bn ^ 2 + cn + d 的值与 an ^ 3 （常量系数a，b，c和d也被忽略了，因为它们对值的贡献也变得无关紧要。）

an^3 + bn^2 + cn + d could be written as O(n^3) in big-o notation, since for large enough nthe values of the term bn^2 + cn + d are insignificant in comparison to an^3 (the constant coefficients a, b, c and d are left out as well, as their contribution to the value become insignificant, too).

我不明白的是，当主导词涉及某种划分时，这如何工作？例如：

What I don't understand is, how does this work when the leading term is involved in some sort of division? For instance:

a / n ^ 3 + bn ^ 2 或 n ^ 3 / a + bn ^ 2

让前一个公式的n = 100，a = 1000和b = 10，那么我们有

Let n=100, a=1000 and b=10 for the former formula, then we have

n ^ 3 / a = 100 ^ 3/1000 = 1000 和 bn ^ 2 = 10 * 100 ^ 2 = 100,000

后者甚至更具戏剧性-在这种情况下，主导词不仅像上述那样缓慢增长，但它还在缩小，不是吗？：

or even more dramatic for the latter - in this case the leading term is not only growing slowly as above, but it's also shrinking, isn't it?:

a / n ^ 3 = 1000/100 ^ 3 = 0.001 和 bn ^ 2 = 100,000 。

在两种情况下，第二项的贡献都更大，那么不是真的确定增长顺序的是 n ^ 2 吗？

In both cases the second term contributes much more, so isn't it n^2that actually determines the order of growth?

它变得更加复杂（对我而言，至少）在前项后面加上减法（ a / n ^ 3-bn ^ 2 ）或第二项也是除法时（ n ^ 3 / a + n ^ 2 / b）或两者均为除法但混合顺序（ a / n ^ 3 + n ^ 2 / b ），等等。

It gets even more complicated (for me, at least) when the leading term is followed by a subtraction (a/n^3 - bn^2) or when the second term is also a division (n^3/a + n^2/b) or when both are divisions but in mixed order (a/n^3 + n^2/b), etc.

t似乎无穷无尽，所以我的一般问题是，如何理解和处理涉及除法（和减法）的公式以确定给定函数的增长顺序？

The list seems endless, so my general question is, how to understand and handle formulas that involve division (and subtraction) in order to determine the order of growth for a given function?

推荐答案

除法只是乘法逆，因此 n ^ 3 / a == n ^ 3 * a ^ -1 ，您可以像处理其他任何系数一样处理它。

A division is just a multiplication by the multiplicative inverse, so n^3/a == n^3 * a^-1, and you can handle it the same way as any other coefficient.

关于减法 a * n ^ 3-b * n ^ 2< = a * n ^ 3 也在 O（n ^ 3）中。另外， a * n ^ 3-b * n ^ 2> = a / 2 * n ^ 3 对于足够大的 n ，它也位于 Omega（n ^ 3）中。有关减法的更详细说明，请参见：面对价值减法时的算法复杂度

With regards to substraction a*n^3 - b*n^2 <= a*n^3, so it is also in O(n^3). Also, a*n^3 - b*n^2 >= a/2 * n^3 for large enough values of n, and it is also in Omega(n^3). A more detailed explanation about substraction can be found in: Algorithm complexity when faced with substraction in value

big O表示法通常用于递增（不必是单调）函数，而递减函数（例如 a / n ）用于虽然 O（1 / n）似乎仍然是完美定义的，但AFAIK还是一个很好的选择，它是 O（ 1）（除非您仅考虑离散函数）。但是，这对于算法的分析几乎没有价值，因为算法的复杂性无法真正降低。.

big O notation is generally used for increasing (don't have to be monotonically) functions, and a decreasing function such as a/n is not a good fit for it, though O(1/n) seems to be still perfectly defined, AFAIK, and it is a subset of O(1) (unless you take into account only discrete functions). However, this has very little value for algorithm's analysis, as a complexity of an algorithm cannot really shrink..

这篇关于复杂性-确定增长顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！