如何找到2个算法运行时间的交叉点？

Question

我想比较两种排序算法。假设对于大小为n的所有输入，第一个算法在8n^2秒内运行，而第二个算法在n秒内以64n lg运行。第一个算法的第n哪个值会胜过第二个算法？

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

2 <= n <= 43. 

我如何获得它的问题？为什么不是。

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

和获取价值2 <= n <= 43。对不起，我是新手。任何人都可以向我解释？

Answer 1

如果没记错的话，相信我这已经有一段时间，但所有你真的需要做的就是图这些曲线中找到了答案。为了更好地理解这个问题，绘制一个基本的日志功能。您会发现它在开始时会快速加速，并且随着x变大，而x^2算法的加速度将继续增加，会逐渐减小。看看图，如果你有一个图形计算器，它会帮助你更好地理解它

Answer 2

你想n这样

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

我们solve h(n) = 8n^2 - 64n lg n for its roots，并发现它在n_1 ~= 1.100和n_2 ~= 43.559有根。如果我们plot这个函数，我们看到它在n < n_1和n > n_2时是正值。

因此，二次算法超过运行时间为linearithmic算法时n < n_1或n > n_2。因此，二次算法击败linearithmic如果n在[1.1, 43.559]这意味着2 <= n <= 43因为n必须是不可或缺的。否则，对于所有其他n，二次算法不如线性算法。