math - 大O日志问题解决

Question

我有一个来自我正在阅读的算法书的问题，我对如何解决它感到困惑（自从我完成对数或指数数学以来已经很长时间了）。问题如下：

假设我们在同一台机器上比较插入排序和归并排序的实现。对于大小为 n 的输入，插入排序以 8n^2 步运行，而合并排序以 64n log n 步运行。对于 n 的哪些值，插入排序优于合并排序？

对数以 2 为底。我已经开始尝试解决平等问题，但被困在 n = 8 log n 左右。

我想要讨论如何在数学上解决这个问题的答案（不接受 excel 的蛮力，抱歉；））。任何指向对数数学描述的链接也将非常有助于我理解您的答案。

先感谢您！

Answer 1

http://www.wolframalpha.com/input/?i=solve%288+log%282%2Cn%29%3Dn%2Cn%29 （由于旧链接停止工作而编辑）

Answer 2

最好的办法是使用牛顿法。

http://en.wikipedia.org/wiki/Newton%27s_method

Answer 3

解决这个问题的一种技术是简单地抓取一个图形计算器并绘制两个函数（参见另一个答案中的 Wolfram 链接）。找到您感兴趣的交叉点（如果有多个交叉点，如您的示例中所示）。

无论如何，没有一个简单的表达式来解决 n = 8 log₂ n（据我所知）。将问题改写为：“找到 f(n) = n - 8 log₂ 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。二进制搜索逻辑在第二个数据列中，我只是自动扩展了它。