如何找到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，二次算法不如線性算法。