复杂性——决定增长的顺序
Complexity - determining the order of growth
我基本上了解如何计算函数的复杂度。这同样适用于确定数学函数的增长顺序。 [我可能不像我想的那样理解它，这就是为什么我可能会问这个。] 例如：
an^3 + bn^2 + cn + d 可以用大 O 表示法写成 O(n^3)，因为对于足够大的 n，项 bn^2 + cn + d 的值与an^3（常数系数 a、b、c 和 d 也被忽略，因为它们对值的贡献也变得微不足道）。
我不明白的是，当前导词涉及某种除法时，这是如何工作的？例如：
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) 或第二项也是除法 (n^3/a + n^2/b) 或当两者都是师，但顺序是混合的 (a/n^3 + n^2/b)，等等
列表似乎无穷无尽，所以我的一般问题是，如何理解和处理涉及除法（和减法）的公式以确定给定函数的增长顺序？
除法只是乘以 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) 中。有关减法的更详细说明，请参见：
big O 符号通常用于递增（不必是单调的）函数，而递减函数如 a/n 不太适合它，尽管 O(1/n) 似乎仍然完美定义，AFAIK，它是 O(1) 的子集（除非你只考虑离散函数）。但是，这对算法分析的价值很小，因为算法的复杂度并不能真正缩小..
您发布的问题类型有一个非常简单的规则。
假设您要查找 f(n) 的增长顺序，并且您找到了一些简单的函数 g(n) 使得
lim {n -> inf} f(n) / g(n) = k
其中 k 是正有限常数。那么
f(n) = Theta(g(n))
（从微积分定义中很容易看出这一点。）
现在让我们看看这如何适用于您的示例：
lim {n -> inf} (a/n^3 + bn^2) / n^2 = b
所以是 Theta(n^2)。
lim {n -> inf} (a n^3 - bn^2) / n^3 = a
所以是 Theta(n^2)。
（当然，假设a和b都是正数。）
我基本上了解如何计算函数的复杂度。这同样适用于确定数学函数的增长顺序。 [我可能不像我想的那样理解它，这就是为什么我可能会问这个。] 例如：
an^3 + bn^2 + cn + d 可以用大 O 表示法写成 O(n^3)，因为对于足够大的 n，项 bn^2 + cn + d 的值与an^3（常数系数 a、b、c 和 d 也被忽略，因为它们对值的贡献也变得微不足道）。
我不明白的是，当前导词涉及某种除法时，这是如何工作的？例如：
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) 或第二项也是除法 (n^3/a + n^2/b) 或当两者都是师，但顺序是混合的 (a/n^3 + n^2/b)，等等
列表似乎无穷无尽，所以我的一般问题是，如何理解和处理涉及除法（和减法）的公式以确定给定函数的增长顺序？
除法只是乘以 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) 中。有关减法的更详细说明，请参见：
big O 符号通常用于递增（不必是单调的）函数，而递减函数如 a/n 不太适合它，尽管 O(1/n) 似乎仍然完美定义，AFAIK，它是 O(1) 的子集（除非你只考虑离散函数）。但是，这对算法分析的价值很小，因为算法的复杂度并不能真正缩小..
您发布的问题类型有一个非常简单的规则。
假设您要查找 f(n) 的增长顺序，并且您找到了一些简单的函数 g(n) 使得
lim {n -> inf} f(n) / g(n) = k
其中 k 是正有限常数。那么
f(n) = Theta(g(n))
（从微积分定义中很容易看出这一点。）
现在让我们看看这如何适用于您的示例：
lim {n -> inf} (a/n^3 + bn^2) / n^2 = b
所以是 Theta(n^2)。
lim {n -> inf} (a n^3 - bn^2) / n^3 = a
所以是 Theta(n^2)。
（当然，假设a和b都是正数。）