数学效率的对数计算

Question

你好我数学不好。但我试图解决下面的问题。我做得对吗>

给定：A 是 B 的大 O、omega 或 theta。

问题是：

A = n^3 + n * log(n);

B = n^3 + n^2 * log(n);

举个例子，我取n=2。

A= 2^3+2log2 => 8.6

B= 2^3+2^2log2 => 9.2

A 是 B 的下界..

我还有其他问题，但我只需要确认我应用的方法是否正确，或者是否有其他方法可以这样做。

这样做对吗？提前致谢。

Answer 1

 A     n^3 + n  *log(n)     1 + log(n)/n^2
--- = ------------------ = ----------------
 B     n^3 + n^2*log(n)     1 + log(n)/n

由于 log(n)/n 和 log(n)/n^2 对 n 趋于无穷大的极限为零，因此取消商 A/B 以远离零的两侧为界。例如，有一个下限 N，使得所有 n > N 的两个表达式都落入区间 [1/2,3/2]。这意味着所有的可能性都是真实的。

Answer 2

大 O 符号背后的想法是比较长期行为。你的想法（插入 n=2）揭示了对于较小的 n 值，A 还是 B 是最大的。然而，O 是关于大值的。部分问题是弄清楚什么是大值。

了解问题的一种方法是对越来越大的 n 值制作 table 的 A 和 B：

           A       B
n=10
n=100
n=1000
n=10000
n=100000
n=1000000

table 中的第一个条目是 n=10 的 A：A=10^3 + 10*log(10) = 1000+10*1 = 1010。

接下来要做的，就是在同一个坐标系下绘制A和B的图形。你能看出两者之间有什么长期关系吗？

Calculation of log for efficiency in math