如何計算算法的確切複雜度？

不使用漸近表示法，是計算獲得算法時間複雜度的唯一方法的單調乏味的步驟？如果沒有每行代碼的步數，我們是否可以得到任何程序的大O代表？如何計算算法的確切複雜度？

詳細信息：試圖找出幾種數值分析算法的複雜性，以決定哪種最適合解決特定問題。例如 - 從Regula-Falsi方法或Newton-Rhapson方法中求解eqns，意圖是評估每種方法的確切複雜性，然後決定（把'n'的值或任何參數），哪種方法不那麼複雜。

來源

2010-07-28 AruniRC

唯一的方法---不是「簡單」或困難的方法，但唯一合理的方法---找到一個複雜算法的確切複雜性是分析它。算法的現代實現與數值庫以及CPU和浮點單元之間存在複雜的交互。例如，高速緩存內存訪問比高速緩存內存訪問要快得多，並且最重要的是可能有多個級別的高速緩存。計算步驟實際上更適合於你認爲不夠用於你的目的的漸近複雜性。

但是，如果您確實想自動計算步驟，也有辦法做到這一點。您可以在每行代碼中添加一個計數器遞增命令（如C中的「bloof ++;」），然後在末尾顯示該值。您還應該瞭解更精確的時間複雜度表達式f（n）*（1 + o（1）），這對分析計算也很有用。例如n^2 + 2 * n + 7簡化爲n^2 *（1 + o（1））。如果常數因子是關於通常漸近符號O（f（n））的困擾，那麼這種細化是一種跟蹤它的方法，並且仍然拋出可忽略的項。

來源

2010-07-28 04:57:34

簡化將有幫助謝謝。你能告訴我更多/指向我如何'分析'複雜算法的必要資源。 – AruniRC 2010-07-29 05:15:25

請參閱http://en.wikipedia.org/wiki/Profiling_%28computer_programming%29。我不是花哨的開發工具的專家，但是維基百科頁面可以幫助您開始。特別是，它提到了經典的Unix分析命令「gprof」。 – 2010-07-29 14:25:35

'簡單的方法'是模擬它。嘗試使用大量n值和大量不同數據的算法，繪製結果，然後將圖上的曲線與方程進行匹配。

您的結果可能不是嚴格正確的，它們只與您生成良好測試數據的能力一樣有效，但對於大多數情況下這將起作用。

來源

2010-07-28 03:00:10 Daniel

例如， - 從Regula-Falsi方法或Newton-Rhapson方法中求解eqns，意圖是評估每種方法的確切複雜性，然後決定（把'n'的值或任何參數），哪種方法不那麼複雜。

對於非線性求解器，我不認爲一般可以回答這個問題。你可以在每次迭代中進行確切的計算次數，但是你永遠不會知道每個求解器需要進行多少迭代才能收斂。還有其他一些複雜問題，比如需要用牛頓的雅可比行列式，這可能會使計算複雜度變得更加困難。

總之，最有效的非線性求解器總是依賴於你正在解決的問題。如果您正在解決的各種問題非常有限，那麼使用不同求解器進行一系列實驗並測量迭代次數和CPU時間可能會爲您提供更多有用的信息。

來源

2010-07-29 00:38:24 MikeT

如何計算算法的確切複雜度？

回答

相關問題