確定哪種算法漸近更快

Question

您將如何確定一種算法是否比另一種算法漸近更快？假設一個方程是t（n）= 7t（n/2）+ n^2，另一個方程是t（n）= aT（n/4）+ n^2。你如何確定一個方程的哪個值比第一個更快。

任何幫助，將不勝感激。

Answer 1

我不完全在分析算法性能的專家，但...

漸近，你把最大的兩個術語來確定算法的增長。因此，您必須確定導致第一項的增長率高於第二項的「a」的值，但由於我們也將其與第一個方程進行比較，因此它必須具有比它更高的增長率以及。根據大師定理，這將是其中，f（n）。

使用在例如F（N）= N ，B = 4。因此，你將不得不解決登錄一個值>日誌 7> 2爲一個。這是約。 48.5

編輯： 這不是我用來作爲源，但我決定做一些谷歌搜索，以找到一個支持源。 https://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf