大O Log问题解决
我有一个来自我正在阅读的算法书籍的问题，我对如何解决它感到困惑（自从我完成对数或指数数学以来已经很长时间了）。问题如下：
假设我们正在比较插入排序和归并排序的实现 机器。对于大小为 n 的输入，插入排序以 8n^2 步运行，而合并排序以 64n log n 步运行。对于哪些 n 值，插入排序优于合并排序？
Log 以 2 为底。我开始尝试求解相等问题，但陷入了 n = 8 log n 的困境。
我希望答案能够讨论如何用数学方法解决这个问题（不接受使用 excel 进行暴力破解，抱歉；））。任何对数数学描述的链接对我理解你的答案也非常有帮助。
先感谢您！
I have question that comes from a algorithms book I'm reading and I am stumped on how to solve it (it's been a long time since I've done log or exponent math). The problem is as follows:
Suppose we are comparing implementations of insertion sort and merge sort on the same
machine. For inputs of size n, insertion sort runs in 8n^2 steps, while merge sort runs in 64n log n steps. For which values of n does insertion sort beat merge sort?
Log is base 2. I've started out trying to solve for equality, but get stuck around n = 8 log n.
I would like the answer to discuss how to solve this mathematically (brute force with excel not admissible sorry ;) ). Any links to the description of log math would be very helpful in my understanding your answer as well.
Thank you in advance!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
解决这个问题的一种技术是简单地使用图形计算器并绘制两个函数的图形（请参阅另一个答案中的 Wolfram 链接）。找到您感兴趣的交叉点（如果有多个交叉点，如您的示例中所示）。
无论如何，没有一个简单的表达式可以解决 n = 8 log2 n （据我所知）。将问题改写为：“找到 f(n) = n - 8 log2 n 中的零”可能会更简单。首先，找到包含您感兴趣的交集的区域，并不断缩小该区域。例如，假设您知道目标 n 大于 42，但小于 44。f(42) 小于 0，f(44) 大于 0。尝试 f(43)。它小于 0，所以尝试 43.5。它仍然小于 0，所以尝试 43.75。它大于 0，因此请尝试 43.625。大于0，所以继续往下，依此类推。这种技术称为二分搜索。
抱歉，这只是“用 excel 暴力破解”的一种变体:-)
编辑：
为了好玩，我制作了一个电子表格，通过二分搜索解决了这个问题：binary-search.xls 。二分搜索逻辑位于第二个数据列中，我只是自动扩展了它。
One technique to solving this would be to simply grab a graphing calculator and graph both functions (see the Wolfram link in another answer). Find the intersection that interests you (in case there are multiple intersections, as there are in your example).
In any case, there isn't a simple expression to solve n = 8 log₂ n (as far as I know). It may be simpler to rephrase the question as: "Find a zero of f(n) = n - 8 log₂ n". First, find a region containing the intersection you're interested in, and keep shrinking that region. For instance, suppose you know your target n is greater than 42, but less than 44. f(42) is less than 0, and f(44) is greater than 0. Try f(43). It's less than 0, so try 43.5. It's still less than 0, so try 43.75. It's greater than 0, so try 43.625. It's greater than 0, so keep going down, and so on. This technique is called binary search.
Sorry, that's just a variation of "brute force with excel" :-)
Edit:
For the fun of it, I made a spreadsheet that solves this problem with binary search: binary‑search.xls . The binary search logic is in the second data column, and I just auto-extended that.
最好的选择是使用牛顿法。
http://en.wikipedia.org/wiki/Newton%27s_method
Your best bet is to use Newton;s method.
http://en.wikipedia.org/wiki/Newton%27s_method
http://www .wolframalpha.com/input/?i=solve%288+log%282%2Cn%29%3Dn%2Cn%29
（由于旧链接停止工作而编辑）
http://www.wolframalpha.com/input/?i=solve%288+log%282%2Cn%29%3Dn%2Cn%29
(edited since old link stopped working)