algorithm - 复杂性——决定增长的顺序

Question

我基本上了解如何计算函数的复杂度。这同样适用于确定数学函数的增长顺序。 [我可能不像我想的那样理解它，这就是为什么我可能会问这个。] 例如:

an^3 + bn^2 + cn + d 可以用大 O 表示法写成 O(n^3)，因为对于足够大的 n bn^2 + cn + d 项的值与 an^3 相比是微不足道的(常数系数 a、b、c 和 d 也被忽略，因为他们对值(value)的贡献也变得微不足道了)。

我不明白的是，当前导词涉及某种除法时，这是如何工作的？例如:

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

对于前一个公式，设n=100，a=1000，b=10，则有

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

或者对于后者来说更引人注目 - 在这种情况下，前导项不仅像上面那样缓慢增长，而且还在缩小，不是吗？:

a/n^3 = 1000/100^3 = 0.001 和 bn^2 = 100,000 如上所述。

在这两种情况下，第二项的贡献要大得多，所以不是n^2实际上决定了增长的顺序吗？

当首项后跟减法 (a/n^3 - bn^2) 或第二项也是 a 时，情况会变得更加复杂(至少对我而言)除法 (n^3/a + n^2/b) 或者两者都是除法但顺序混合 (a/n^3 + n^2/b)等

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

Answer 1

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

关于减法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) 中.有关减法的更详细说明，请参见:Algorithm complexity when faced with substraction in value

大 O 符号通常用于递增(不必是单调)函数和递减函数，例如 a/n不适合它，虽然O(1/n)似乎仍然是完美定义的，据我所知，它是 O(1) 的子集(除非您只考虑离散函数)。然而，这对算法分析的值(value)很小，因为算法的复杂度并不能真正缩小..