哪个功能增长得更快

Question

2 ^(n/2 + 10 log n)

要么

2 ^ N？

我在MIT OCW 6.006做了一个练习.它有一个问题,即后来比前者增长得更快.但我不同意这个证据.我说前者比后者增长得快.有人可以解释我是不是错了,让我知道为什么.谢谢!

Answer 1

您可以通过拉出指数部分来区别对待,然后只询问哪个更大(n/2 + 10logn)或n.这里很明显,只要10logn小于半n,第二个就会变大.

当n达到大约30时,这变成了现实,所以从那时起,第二个更大.(对于基数10)

让我们进一步讨论log base 2以及10LogN何时可能小于N/2？
好吧,这就像询问logN何时变得小于N/20一样

简而言之,log_2是描述基数为2的数字所需的位数.所以:

• log_2(32)给了我们5.
• log_2(64)给了我们6.
• log_2(128)给了我们7. < - 看这里128:7约为18:1
• log_2(256)给了我们8.
• log_2(512)给出了9.
• log_2(1024)给了我们10.
• log_2(64000)给我们~16.

现在我们正在寻找第一个值(32,64,128等)超过第二个值的20倍.正如你所看到的那样,这种情况会在128/7对之后发生,并且它们会迅速分开.