用任何編程語言測量程序的時間複雜度

Question

我正在尋找標準程序來識別程序的運行時間複雜度。 正如here所述，我不是通過查看代碼而是通過程序運行時的某些其他參數尋找解析來分析它的解決方案。

考慮一個程序，該程序要求用戶將二進制字符串轉換爲十進制等效字符。當每次處理每個二進制數字時，這樣的程序的時間複雜度應該是最差的O（n）。有了一些智能，運行時間可以減少到O（n/4）（每次從二進制字符串中處理4位數字，假設二進制字符串對於所有k = 1,2,3 ...都具有4k數字）

我用C編寫了這個程序，並且使用了time命令和一個函數，它使用gettimeoftheday（兩者）來計算具有64位四核處理器（每個核心在800MHz）的linux盒子在兩種類別下的運行時間：

1. 當系統正常負載（核心使用5-10％）下
2. 當系統是重負載（核心使用80-90％）

下

以下是O（n）的算法，二進制串的長度是100000，在正常負載下的讀數：

Time spent in User (ms) - 216 
Time Spent in Kernel (ms) - 8 
Timed using gettimeofday (ms) - 97 

以下是讀數O（n）的算法，二進制串的長度是20萬，高負載下：

Time spent in User (ms) - 400 
Time Spent in Kernel (ms) - 48 
Timed using gettimeofday (ms) - 190 

我在尋找：

1. 如果我使用時間命令，我應該考慮哪個輸出？真正的，用戶還是系統？
2. 是否有標準的方法來計算程序的運行時間？
3. 每次執行這些命令時，我都會得到不同的讀數。考慮到代碼沒有改變，我應該抽樣多少次，以便平均數始終相同。
4. 如果我想使用多個線程並通過調用這些程序的execve來測量每個線程中的時間，該怎麼辦？

從我所做的研究中，我還沒有遇到過任何標準方法。另外，無論我使用的任何命令/方法每次都給我不同的輸出（我明白這是因爲上下文切換和cpu週期）。我們可以假設，我甚至可以用一個依賴於機器的解決方案來完成。

Answer 1

回答您的問題：

1. 取決於你的代碼是幹什麼的time輸出的每個組件可以是顯著。 This問題涉及這些組件的含義。如果您正在計時的代碼不使用系統調用，計算「用戶」時間可能就足夠了。我可能只是使用「真實」的時間。
2. time怎麼了？如果你需要更好的粒度（即你只需要一段代碼而不是整個程序），你總是可以在你分析代碼塊之前獲得開始時間，運行代碼，然後獲得結束時間，然後計算差異以給你運行時間。 從不使用gettimeofday因爲時間不單調增加。系統時間可以由管理員或NTP進程更改。您應該使用clock_gettime。
3. 爲了儘量減少從運行到運行的運行時間差異，我會檢查cpu頻率縮放是否爲關閉特別是如果您得到的結果非常不一致。這已經讓我感覺到了。
4. 一旦開始進入多個線程，您可能需要開始查看一個分析器。 gprof是一個很好的開始。