如何从 CLRS 解决相对渐近增长 (table) 的问题？
How to solve a problem on relative asymptotic growth (table) from CLRS?
尽管我最近学了微积分并且擅长数学，但我很难填满这个 table。章节中只具体说明了如何处理lim(n^k/c^n)，其他函数怎么比较我就不知道了。我查看了解决方案手册，但没有相关信息，只有 table 的答案提供了很少的见解。
当我解决这些问题时，我并没有真正考虑限制——我依靠一些事实和大 O 表示法的一些众所周知的属性。
事实 1：对于所有函数 f 和 g 以及所有指数 p > 0，我们有 f(n) = O(g(n)) 当且仅当 f(n)p = O(g(n)p)，并且分别与 o、Ω、ω 和 Θ 类似。这从定义中得到了直接的证明；您只需要将常数 c 也提高到 p 次方即可。
事实 2：对于所有指数 ε > 0，函数 lg(n) 为 o(nε)。这遵循 l'Hôpital 的限制规则： lim lg(n)/nε = lim (lg(e)/n)/(ε nε−1 ) = (lg(e)/ε) lim n−ε = 0.
事实 3：
- 如果 f(n) ≤ g(n) + O(1)，则 2f(n) = O(2g(n) ).
- 如果 f(n) ≤ g(n) − ω(1)，则 2f(n) = o(2g(n) ).
- 如果 f(n) ≥ g(n) − O(1)，则 2f(n) = Ω(2g(n) ).
- 如果f(n) ≥ g(n) + ω(1)，则2f(n) = ω(2g(n) ).
事实 4：lg(n!) = Θ(n lg(n))。证明使用斯特林近似。
要解决 (a)，请使用事实 1 将两边都提高到 1/k 次方并应用事实 2。
求解(b)，重写nk = 2lg(n)k和cn = 2lg(c)n，证明lg(c) n − lg(n) k = ω(1)，应用事实3.
(c) 很特别。 nsin(n) 在 0 和 n 之间的任何地方结束。因为0是o(√n)，n是ω(√n)，所以是NO的实线行
为了求解 (d)，观察到 n ≥ n/2 + ω(1) 并应用事实 3。
求解(e)，重写nlg(c) = 2lg(n)lg(c) = 2lg(c)lg(n) = clg(n).
为了解决 (f)，使用事实 4 并发现 lg(n!) = Θ(n lg(n)) = lg(nn).
尽管我最近学了微积分并且擅长数学，但我很难填满这个 table。章节中只具体说明了如何处理lim(n^k/c^n)，其他函数怎么比较我就不知道了。我查看了解决方案手册，但没有相关信息，只有 table 的答案提供了很少的见解。
当我解决这些问题时，我并没有真正考虑限制——我依靠一些事实和大 O 表示法的一些众所周知的属性。
事实 1：对于所有函数 f 和 g 以及所有指数 p > 0，我们有 f(n) = O(g(n)) 当且仅当 f(n)p = O(g(n)p)，并且分别与 o、Ω、ω 和 Θ 类似。这从定义中得到了直接的证明；您只需要将常数 c 也提高到 p 次方即可。
事实 2：对于所有指数 ε > 0，函数 lg(n) 为 o(nε)。这遵循 l'Hôpital 的限制规则： lim lg(n)/nε = lim (lg(e)/n)/(ε nε−1 ) = (lg(e)/ε) lim n−ε = 0.
事实 3：
- 如果 f(n) ≤ g(n) + O(1)，则 2f(n) = O(2g(n) ).
- 如果 f(n) ≤ g(n) − ω(1)，则 2f(n) = o(2g(n) ).
- 如果 f(n) ≥ g(n) − O(1)，则 2f(n) = Ω(2g(n) ).
- 如果f(n) ≥ g(n) + ω(1)，则2f(n) = ω(2g(n) ).
事实 4：lg(n!) = Θ(n lg(n))。证明使用斯特林近似。
要解决 (a)，请使用事实 1 将两边都提高到 1/k 次方并应用事实 2。
求解(b)，重写nk = 2lg(n)k和cn = 2lg(c)n，证明lg(c) n − lg(n) k = ω(1)，应用事实3.
(c) 很特别。 nsin(n) 在 0 和 n 之间的任何地方结束。因为0是o(√n)，n是ω(√n)，所以是NO的实线行
为了求解 (d)，观察到 n ≥ n/2 + ω(1) 并应用事实 3。
求解(e)，重写nlg(c) = 2lg(n)lg(c) = 2lg(c)lg(n) = clg(n).
为了解决 (f)，使用事实 4 并发现 lg(n!) = Θ(n lg(n)) = lg(nn).