與大O有點混淆

Question

所以我有一個關於如何驗證函數的大O的快速問題。

例如：一個快速排序算法的排序5000000元件的陣列產生的0.008524秒的時間間隔，以百萬元件產量0.017909運行相同的算法。如果我的quicksort是/不是n * log（n）的大O，我將如何檢查大O？

我想我明白：N增加2因而運行應當由2 *日誌（2）增加嗎？

F（N）= 0.008524 - >的n log（n）的

F（2N）= 0.017909 - > 2N *日誌（2N）

Answer 1

大O符號通常不關心遊程時間以秒爲單位。它與相關的操作數由算法執行。確定這一點的唯一方法是查看函數的代碼。

不僅將運行時間由低階方面的影響（請記住，大O符號只關注自身與最高階項），而且還東西，如程序啓動時的開銷，緩存效率和分支預測。

說了這麼多，這可能是因爲沒有這些其他影響將在你的情況顯著。在這種情況下，如果n加倍，那麼您會預期運行時間將從knlog（n）增加到k.2n.log（2n）= k（2n.log（2）+ 2n .log（n））。

Answer 2

兩個數據點是不是真的不夠。但是，2 * n * log（2 * n）= 2 * n *（log（n）+ log（2）），所以您可以看到當乘數大約爲2 * log（2）你的體積增加一倍。這看起來似乎適合你給的數字。你應該添加更多的點並仔細檢查。

請注意，在您的計時中可能會有一些常數項，至少如果您在其中包含程序啓動 - 這可能很重要。另一方面，如果你只在沒有啓動的情況下進行分揀階段的時間，則更準確。您應該對輸入數據的許多排列重複該過程，以確保您獲得具有代表性的一組值。

Answer 3

大O符號是漸近。這意味着它只適用於n越來越大的限制。

爲什麼使用50和100元素進行排序可能無法跟蹤O（n log n），緩存效果是可能的候選項，這有很多原因。如果你嘗試了100000比20000比100萬，你可能會發現它跟蹤更好一點。

另一種可能性是大多數快速排序實現平均只有O（n log n）一些投入會花費更長時間。遇到這種病理輸入的機率比50個元素高出10萬。

不過說到底，你不「驗證」大O的運行時間;你證明它基於算法的作用。

Answer 4

有了這段代碼，你要看的是，它需要多長時間才能運行50個元素，而不是100個，而不是定時本身。就像我正在迭代一個數組一樣，這將是線性時間O（n），因爲數組必須通過每個索引到最後。 N表示數組的大小。此外，從長遠來看，大O符號意味着整體計劃。如果平均的時間爲50，100，1000，100000，1000000你會看到平均這將有O（n日誌（N））。

Answer 5

有幾個要點要牢記：首先，當你改變大小，硬件（至少一個典型的計算機上），將有一個效果爲好。特別是，當你的數據變得很大以適應特定大小的緩存時，你可以期望看到運行時間的大幅增加，這完全獨立於所討論的算法。爲了更好地瞭解算法的適用性，您應該（可能）首先比較一些具有真正複雜性的算法，但使用相同大小的數據。對於一個明顯的可能性，時間用隨機數填充陣列需要多長時間。至少假設一個合理的典型PRNG，這應該是線性的。

然後計算您的算法，並查看它是如何將相對更改爲相同大小的線性算法。例如，你可以使用像這樣的代碼：

#include <vector> 
#include <algorithm> 
#include <iostream> 
#include <time.h> 
#include <string> 
#include <iomanip> 

class timer { 
    clock_t begin; 
    std::ostream &os; 
    std::string d; 
public: 
    timer(std::string const &delim = "\n", std::ostream &rep=std::cout) 
     : os(rep), begin(clock()), d(delim) 
    {} 
    ~timer() { os << double(clock()-begin)/CLOCKS_PER_SEC << d; } 
}; 

int main() { 
    static const unsigned int meg = 1024 * 1024; 

    std::cout << std::setw(10) << "Size" << "\tfill\tsort\n"; 
    for (unsigned size=10000; size <512*meg; size *= 2) { 
     std::vector<int> numbers(size); 
     std::cout << std::setw(10) << size << "\t"; 
     { 
      timer fill_time("\t"); 
      std::fill_n(numbers.begin(), size, 0); 
      for (int i=0; i<size; i++) 
       numbers[i] = rand(); 
     } 
     { 
      timer sort_time; 
      std::sort(numbers.begin(), numbers.end()); 
     } 
    } 
    return 0; 
} 

如果我繪製既填補了時間和排序的時候，我得到的是這樣的：

由於我們的規模是指數型的，我們的線性算法顯示（粗略）指數曲線。排序的時間顯然還在增長（有點）更快。

編輯：憑心而論，我也許應該補充的是日誌（N）成長緩慢，對數據的幾乎任何實際的量，它的貢獻極小。對於大多數實際用途，您可以將快速排序（例如）視爲線性大小，只是填充內存的常數因子較大。線性增長的規模和製圖的結果使這更明顯：

如果你仔細觀察，你或許可以看到只顯示一個輕微向上從曲線上線「的日誌（N）」因子。另一方面，如果我不知道它應該在那裏，我不確定我是否會注意到任何曲率。