<分区>
2^(n/2+10 log n)
或
2^n?
我正在做 MIT OCW 6.006 的练习。它有一个问题，即后来比前者增长得更快。但我不能同意这个证明。我说前者比后者长得快。有人可以解释我是否错了并让我知道原因。谢谢!
<分区>
2^(n/2+10 log n)
或
2^n?
我正在做 MIT OCW 6.006 的练习。它有一个问题，即后来比前者增长得更快。但我不能同意这个证明。我说前者比后者长得快。有人可以解释我是否错了并让我知道原因。谢谢!
最佳答案
您可以通过拉出指数部分来构建不同的框架，然后只需询问 (n/2+10logn) 或 n 哪个更大。 这里很明显，只要 10logn 小于 n 的一半，第二个就会更大。
当 n 达到大约 30 时，这就成立了，所以从那时起，第二个更大。 (对于以 10 为底的日志)
让我们进一步讨论以 2 为底的对数，以及 10LogN 何时可能小于 N/2？
嗯，这和问什么时候 logN 变得小于 N/20 一样
粗略地说，log_2 是描述一个以 2 为基数的数字所需的位数。所以:
现在我们正在寻找第一个值(32,64,128 等)何时超过第二个值的 20 倍。如您所见，这会发生在刚好超过 128/7 对时，并且它们会迅速分开。
关于algorithm - 哪个功能增长更快，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20761870/