algorithm - 如何找到两种算法运行时间的交叉点？

Question

我正在尝试比较两种排序算法。假设对于所有大小为的输入n，第一个算法在8n^2几秒内运行，而第二个算法在 64n lg n 秒内运行。第一个算法在哪个值上n优于第二个算法？

答案是：8n^2 < 64n lg n.

2 <= n <= 43.

我如何从问题中得出它？为什么不是。

8n^2 > 64n lg n
or  8n^2 = 64n lg n

并获得价值2 <= n <= 43。对不起，我是新手。谁能给我解释一下？

score 2 · Accepted Answer

你想要n这样

   8n^2 < 64n lg n
=> 8n^2 - 64n lg n < 0

我们求解h(n) = 8n^2 - 64n lg n它的根，发现它的根位于n_1 ~= 1.100和n_2 ~= 43.559。如果我们绘制这个函数，我们会看到它是正的 whenn < n_1和 when n > n_2。

8^n2 - 64n lg n 的图

因此，当或时，二次算法超过了线性算法的运行时间。因此，二次算法优于线性如果，其中意味着因为必须是积分的。否则，对于所有其他，二次算法不如线性算法。n < n_1n > n_2n[1.1, 43.559]2 <= n <= 43nn

score 1 · Accepted Answer

如果我没记错的话，相信我已经有一段时间了，但你真正需要做的就是绘制这些曲线来找到答案。为了更好地理解这个问题，绘制一个基本的日志函数。你会看到它在开始时加速很快，随着 x 变大而趋于平稳，而 x^2 算法的加速度将继续增加。如果您有图形计算器，请查看图表，它将帮助您更好地理解它

2 回答 2