編寫一個測試程序來評估計算複雜性（大O）

我的任務是寫一個測試程序來評估以下問題的計算複雜度（大O），真的不知道從哪裏開始。編寫一個測試程序來評估計算複雜性（大O）

這就是我能產生

for(int i=0; i <n; i++){ 
    // Do stuff 
}

現在的問題是如何編寫測試程序。有人可以幫我嗎？

2011-09-02 Edd

C語言？你在正確的軌道上。閱讀關於big-o的更多信息，請點擊這裏http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o –

你不能真正「評估計算複雜性」，因爲定義了大O符號在*漸近*性能方面（即它是一個代數表達式，當'n'變爲無窮大時）。但是，你可以運行你的程序來獲取不同的'n'值，計算時間並繪製結果。這是你想要做的嗎？ –

從你所描述的，算法的複雜性似乎是O（n^2）。可以嘗試對其進行「實驗性」評估：只需運行具有不同n值的算法並計算時間。然後在圖的x軸上繪製n個值，並在y軸上繪製時間值。你現在應該看到一些近似拋物線的東西。

2011-09-02 21:02:17 Simone

對於k> = 0形式（n^k）的複雜性問題，可以通過計數嵌套循環的數量來編寫代碼。但是在複雜的（（n^2）* lg（n））複雜的遞歸問題中很難實現。

我沒有實現它，但我確信，可以做

2012-02-29 05:36:54 abhi120

回答