不能定義增長率爲了

我不知道爲什麼A（n）大於C（n）的慢，因爲較高的增長率意味着運行時間較慢

從我的角度來看，他們都有分子的根。但是，A（n）除以logn，這意味着它應該小於根n。因此，由於C（n）仍然有根n（即使它是n^1/3，但仍有根），並且沒有被任何東西除，所以整個A（n）變得比C（n）快。

定義增長率訂單有最簡單的方法嗎？

非常感謝你，如果你能解釋爲什麼A（n）比C（n）慢。

2017-06-13 Ryu

*「我不知道爲什麼A（n）比C（n）慢，因爲更高的增長率意味着更慢的運行時間。」* - 不一定。假設A（n）複雜度爲1000000 * n，B（n）複雜度爲n^3。 A（n）是有界的，但它有一個非常大的常量。當n <1000時，[B（n）將優於A（n））（https://www.symbolab.com/solver/equation-calculator/1000000n%20%3C%3D%20n%5E%7B3%7D）。結論是，如果你知道關於你的數據集的一些信息，你可以選擇一個漸近較慢的算法，並且在某些情況下仍然可以獲得更好的性能。 – jww

我投票結束這個問題作爲題外話，因爲潛在的問題是關於[math.se]。 – Dukeling

或者也許它只是[簡單英文解釋「大O」符號？]的副本（https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-大O型）（Big O？Big Theta？足夠接近）。或者這可能是一些脫離主題和重複的組合。 – Dukeling

C(n)和A(n)都在分子的根源，但它們是不同的根。在C(n)這是一個立方根和A(n)它是一個平方根。寫他們另一種方法是：

C(n) = Θ(n^(1/3))

和

A(n) = Θ(n^(1/2)/some-log-term)

現在很明顯，1/3 < 1/2，並因此與n足夠大的n^(1/3)遠小於n^(1/2)（和n^(1/2)/some-log-term太）。事實上A(n)是任意大，這意味着C(n) << A(n)

來源

2017-06-14 06:47:08

不能定義增長率爲了

回答

相關問題