渐近增长率的排序函数 [英] Ordering functions by Asymptotic Growth Rate

问题描述

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

List the following functions in non-descending order of asymptotic growth rate. If two or more functions have the same asymptotic growth rate then group them together.

g1(n)= n

g2(n)= n ^ 3 + 4n

g2(n) = n^3 +4n

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

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

g4(n)= 2 ^ n

g4(n) = 2^n

g5(n)= 3 ^(3 * log(基数3)n)

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

g6(n)= 10 ^ n

g6(n) = 10^n

我一直在网上浏览几个示例，但是我不知道该怎么做，对我来说这似乎是一个完全陌生的概念.如果有人可以帮助我，将不胜感激.我什至如何计算增长率?

I've been looking through several examples online but I have no idea how to do this, it just seems like a completely foreign concept to me. If anyone could help me, that would be much appreciated. how do I even calculate the growth rate?

推荐答案

在这里您可能会发现最有用的许多技术是处理涉及对数和指数的表达式的技巧.

Many of the techniques that you might find most useful here are tricks for manipulating expressions involving logs and exponents.

首先，您可能需要查看对数的幂规则:

First, you might want to review the power rule for logarithms:

a log _b c = log _b c ^a .

a log_b c = log_b c^a.

接下来，事实是指数和对数互为倒数:

Next, there's the fact that exponents and logarithms are inverses of one another:

log _b b ⁿ = b ^{log _b n} = n

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

例如，这些规则可以帮助您重写g ₅ (n).

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

这是另一个有用的规则:

Here's another helpful rule:

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

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

您实际上可以使用前两个规则来更改指数函数的基数.例如，假设您要比较2 ⁿ 与5 ⁿ .注意

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} .

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

这是否使查看这两个功能中的哪个功能变得更迅速变得更容易?

Does that make it easier to see which of these two functions will grow more rapidly?

最后，您可能需要使用以下事实:所有多项式的增长都比所有底数大于1的指数慢.这意味着n ^k 的增长严格慢于a ⁿ 对于任何n>同样，所有多项式的增长严格快于所有对数，因此log _b n <对于所有k> n ^k 0.

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中的指数形式.然后，您可以从那里对它们自己的对数表达式，对他们自己的多项式以及对他们自己的指数进行排序，然后按顺序将它们写出来.

Using the above rules, see if you can try to rewrite each of these expressions as either a logarithm of n, a polynomial in n, or something exponential in n. From there, you can then rank the logarithmic expressions against themselves, the polynomials against themselves, and the exponentials against themselves, then write them out in order.

通常来说，这里提到的技术在将来很有用.我希望这能使您走上正确的轨道！

Generally speaking, the techniques mentioned here are super useful going forward. I hope that this gets you on the right track!

这篇关于渐近增长率的排序函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！