理論上如何計算某種方法的執行時間？

假設我有「堆排序」方法，其複雜度爲O（nlogn）。當我通過1000000次輸入測量此方法的執行時間時，我得到了0.375770669秒。我如何從理論上計算此方法的執行時間？理論上如何計算某種方法的執行時間？

來源

2011-05-20 Eng.Fouad

如果你已經知道它是O（n log n） - 或Θ（n log n）更準確 - 那麼你想從理論上計算什麼？理論上你想知道如何到達「0.375770669秒」的數字嗎？ – ShreevatsaR 2011-05-20 04:53:36

@ShreevatsaR我想比較測量的和理論的。 – 2011-05-20 04:55:32

理論上沒有辦法計算這個。這取決於很多因素，如：

Java版本和主版本/次版本/補丁版本號。
各種JVM調優參數;例如堆有多大。
您的硬件平臺; CPU，內存大小，甚至主板和主頻。
機器上的負載;即它正在做什麼。
CPU散熱片上的絨毛量。嚴重的是，如果處理器芯片太熱，主板振盪器的時鐘速度也有點溫度敏感，那麼時鐘速度可能會降低。

即使您知道所有這些，計算本質上也是Java JIT編譯器和硬件執行的取證模擬。設想太複雜了。

在「速度」的理論測量方面，您可以合理期望達到的最佳效果是在源代碼級別對抽象操作進行計數。即使鑽取並計算執行的字節碼也可能太難以實用。

我想比較測量的和理論的。

基本上，你不能。

來源

2011-05-20 04:48:35

你可能會做的是運行你的代碼爲各種數量的輸入，如1000,10000,100000,1000000,1000000000等，並記錄在排序花費的時間。然後將這些記錄時間與X-Y圖中的元素數進行比較並查看是否獲得了複雜度曲線。

也期待在本文檔的堆排序分析和演示：http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm

來源

2011-05-20 04:49:15 anubhava

記住，O（＆middot）或Θ（＆middot;）符號描述生長的漸近率，在極限n接近無窮大：它描述了當您將輸入大小乘以10時算法得到的速度。這與實際輸入大小（與「無窮大」相比總是無限小）的實際執行時間有多密切取決於用於分析算法的理論模型與您所擁有的實際機器的對應程度。

具體而言，「堆排序需要Θ（N log n）的時間」是指存在常數Ç和c 使得對於足夠大的n，如果T（n）是時間它發生在大小n的輸入，然後

ç的n logñ< T（n）的<ç的n logñ

爲n的大小= 1000000可能會或可能不會是「足夠大N」的漸近行爲踢。

然而，假設它是和解釋的聲明意味着花費的時間大約是（CN log n）的一些常數c，等同

c1000000lg（1000000）=0.375770669秒

給出了C語言≈1.88×10 -8 。這意味着n = 2000000的輸入應該花費大約0.79秒，n = 10000000應該花費大約4.38秒。您可以將此「理論」結果與通過使用該尺寸輸入運行算法得到的實驗結果進行比較。

拇指爲典型的計算機的一個粗略的規則是，c是某處10 ^-7緩慢計算機和算法之間，和10 ^-9爲合理體面的。將任意一端的另一個因子10乘以安全。（這個想法是，典型的分析給常量c在1-200之間，典型的計算機在一個數量級或兩個速度之內。當然，「典型」是主觀的，如果你用斐波那契可能要失望了。）

與先驗猜測下約10 ^-8會因爲運行時間是0.2秒左右開始。

來源

2011-05-20 05:19:22 ShreevatsaR

理論上如何計算某種方法的執行時間？

回答

相關問題