如何根據O-notation來判斷一個函數是否比另一個函數更快？

我有一個問題，如何確定1函數比另一個函數更快或更慢。如果教授使用O（1）和O（n）的例子，我知道O（1）更快，但我真的只知道通過記憶運行時間順序的簡單函數......但是如果給出更復雜的例子，我不明白如何找到更快的功能。如何根據O-notation來判斷一個函數是否比另一個函數更快？

例如，假設我想比較ñ^ LOGN和n ^（LOGN）^ 2和n ^（開方（N））。我怎樣才能比較這些功能，並能夠分辨出哪一個具有最快和最慢的運行時間（大O符號）？有沒有一步一步的過程，我可以按照每次，以便比較功能運行時間時可以使用？

下面是我對上面的例子思想。我知道n^2比n^3快。所以我想比較每個函數的n^____。因此，如果每插入n = 1000000，logn將具有最小值，logn^2將具有第二個值，並且logn^sqrt（n）將具有最大值。這是否意味着最小值（n^logn）將是最快的，而最大值（n^sqrt（n））將是最慢的？ 2. N^LOGN（最快） 1. N^LOGN^2 2. N^SQRT（N）（最慢）

來源

2014-10-02 Marika Lee

它取決於N的值。查看錶達式的圖形。 – SLaks 2014-10-02 02:43:02

簡短的答案是，你不能。「n」接近無窮大時，複雜性告訴你漸近行爲。它並不一定告訴你任何有限的'n'的實際速度。 – 2014-10-02 02:50:31

一般大O寫爲N的函數（除了在恆定的情況下，O（1））。

所以這是簡單的堵塞任何N（3倍或4的值，優選爲足夠的值看曲線）到您比較兩者的功能和計算的問題。如果可以的話，圖表他們。

但你不應該需要做的是，你應該有功能的大圓滿類有基本的瞭解如果你不能計算它，你也應該知道，O（日誌N）大於O（1）等。O符號是最糟糕的情況。所以如果你熟悉最常見的功能，通常比較很容易。

這是否意味着最小的值（N^LOGN）將是最快和最大數（n ^的sqrt（N））將是最慢？ 2. N^LOGN （最快）1. N^LOGN^2 2. N^SQRT（N）（最慢）

爲了您比較的目的，是的。 O符號用於比較最壞情況，複雜度或算法類別，因此您只是假設比較中的所有候選者都是最差情況。您無法從O符號中得知最佳，典型或平均的表現。

來源

2014-10-02 02:45:01 codenheim

你也不能從O符號中知道對於任何特定的選擇n會發生什麼。它純粹是漸近的，重要的是不要超支。 – tmyklebu 2014-10-02 03:49:34

比較ö符號基本上是比較曲線的問題。我建議你繪製曲線 - 這對你的理解有幫助。

如果您使用Python，我想推薦嘗試mathplotlib.pyplot。這非常方便。

來源

2014-10-02 02:44:33

如何根據O-notation來判斷一個函數是否比另一個函數更快？

回答

相關問題