按照渐近增长率排序的函数

Question

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

g1(n) = n

g2(n) = n^3 +4n

g3(n) = 2n log(base 2) n

g4(n) = 2^n

g5(n) = 3 ^ (3 * log(base 3) n)

g6(n) = 10^n

我已经查看了几个在线示例，但我不知道如何做到这一点，它似乎对我来说完全是一个外国概念。如果有人能帮我，那将不胜感激。我该如何计算增长率？

- 1010101

Answer 1

许多你可能会发现最有用的技巧是处理涉及对数和指数表达式的技巧。

首先，你可能想复习一下对数的幂运算规则：

a log_b c = log_b c^a.

接下来，有一个事实，指数和对数是彼此的反函数： log_b bⁿ = b^{log_b n} = n

这些规则可能会帮助你重写g₅(n)。

还有另一个有用的规则：

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

你实际上可以使用前两个规则来更改指数函数的底数。例如，假设你想比较2ⁿ和5ⁿ。注意到：

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

这样是否更容易看出这两个函数中哪个增长更快了呢？

最后，你可能想使用以下事实：所有多项式增长速度都比底数大于1的所有指数函数慢。这意味着n^k比任何n>1的aⁿ增长要慢。同样，所有多项式增长速度都比所有对数函数快，因此对于所有k>0，log_b n < n^k。

使用上述规则，尝试将每个表达式重写为n的对数、n的多项式或n的指数形式。然后，你可以将对数表达式与自身进行排名，将多项式与自身进行排名，将指数函数与自身进行排名，然后按顺序写出它们。

一般来说，这里提到的技巧在未来非常有用。希望这能让你走上正确的轨道！

- templatetypedef

Answer 2

有一个非常简单的规则可以帮助解决这些问题。使用微积分和复杂性的基本定义很容易证明它（这可能是一个不错的练习）。

给定两个函数f(n)和g(n)：

• 如果lim_{n → ∞}f(n) / g(n) = 0，那么f(n) = o(g(n)。

• 如果lim_{n → ∞}f(n) / g(n) = ∞，那么f(n) = w(g(n)（这是从前面的点得出的）。

• 如果lim_{n → ∞}f(n) / g(n) = c，0 < c < ∞，那么f(n) = Θ(g(n)。

看着你在这里的例子，它们每一个都可以用这些方法来解决。例如，lim_{n → ∞} g1(n) / g2(n) = 0，所以g1(n) = o(g2(n))。

- Ami Tavory