按渐近增长率对函数排序

按渐近增长率的非降序列出以下函数。如果两个或多个函数具有相同的渐近增长率，则将它们分组在一起。

g1(n) = n

g2(n) = n^3 +4n

g3(n) = 2n log(以 2 为底) n

g4(n) = 2^n

g5(n) = 3 ^ (3 * log(以 3 为底) n)

g6(n) = 10^n

我一直在网上浏览几个例子，但我不知道如何做到这一点，这对我来说似乎是一个完全陌生的概念。如果有人可以帮助我，我将不胜感激。我如何计算增长率？

您可能会发现这里最有用的许多技术是操作涉及对数和指数的表达式的技巧。

首先，您可能需要回顾一下对数的幂法则：

a log_b c = log_b c^a.

接下来，指数和对数互为倒数：

log_b bⁿ = b^{log_b n} = n

These rules might help you rewrite g₅(n), for example.

这是另一个有用的规则：

(a^b)^c = a^bc = (a^c)^b.

You can actually use the two previous rules to change the bases of exponential functions. For example, suppose you want to compare 2ⁿ to 5ⁿ. Notice that

5ⁿ = (2^{log₂ 5})ⁿ

= (2ⁿ)^{log₂ 5}.

这是否可以更容易地看出这两个功能中哪一个会增长得更快？

Finally, you might want to use the following fact: all polynomials grow slower than all exponents whose base is greater than 1. This means that n^k grows strictly slower than aⁿ for any n > 1. Similarly, all polynomials grow strictly faster than all logarithms, so log_b n < n^k for all k > 0.

使用上述规则，看看是否可以尝试将每个表达式重写为 n 的对数、n 的多项式或 n 的指数。然后，您可以根据对数表达式自身、多项式自身和指数自身对对数表达式进行排序，然后按顺序将它们写出来。

一般来说，这里提到的技术对于未来非常有用。我希望这能让您走上正轨！