STL庫里的演算法時間複雜度和空間複雜度都是最佳的嗎？

1樓：Alinshans

肯定不都是最佳的。

但肯定比99%的人寫的都要好。

競賽中不一定要求時間複雜度最小，但是基本上（嚴格一點的）要求達到乙個級別。比如複雜度能O(nlogn)的你不要搞O(n)。

STL中的演算法肯定能確保你能達到，如果你的寫法沒有問題，但死活超時了（卡常數），我覺得題目出得有問題。

另，你知道了會不會用也是乙個問題。有人說vector會跪。我演示一下：

#include

#include

#include

intmain

()autot2=

std::

chrono

::high_resolution_clock

::now

();printf

(" %fms\n"

,std

::chrono

::duration

,std

::milli

>(t2

-t1));}

我的電腦上，多執行幾次，基本都是在

225.914928ms

然後把迴圈體內改成這樣：

v.push_back(i);

再次執行，基本是

124.791752ms

再改：v[i] = rand();

執行：22.133219ms

.還有sort，我覺得是夠用的，當然針對題目自己寫的肯定會更快，我是有測試的：https://

要看結果直接拖到最下面。當然我也從沒有自己專門寫過sort。

2樓：

STL裡面的演算法複雜度多數是最佳的，也有很多不是最佳卻是最實用的（比如sort），特殊情況當然要自己寫特殊演算法。庫里的演算法至少在90%以上應用中夠用。

演算法時間複雜度中的PSPACE,coNP complete,DP complete的含義。

A complete 的定義對於所有 class 都一樣,就是說 class A NP 中的所有問題都可以規約到某個特定問題 3 SAT 想看書去找 Sipser,或者 Arora Barak,或者 Goldreich,或者 Papadimitriou.至於 PSPACE 和 coNP,這兩個算常見...

演算法時間複雜度為O（n ）的是什麼演算法？

子正 O n 的演算法不稱其為演算法，它意味著這個問題尚未解決。n稍微大一點，就會耗盡CPU的算力。它比不斷摺紙 圍棋盤上擺大公尺得到的數更大。這種 演算法 是進行演算法改進的物件。演算法老師沒有花力氣說明這種演算法的荒謬之處倒是個很不可思議的事情。n 是個很大的數，你可以用windows自帶的計算...

edmonds karp 演算法的複雜度？

證明 Edmonds Karp演算法時間複雜度為 閱讀如下詳細證明的前提是你已經完全掌握了EK演算法的步驟。證明開始 參考了網上找到的 證明1 證明2 a EK演算法中一次BFS尋找增廣路的時間複雜度為 每次BFS增廣，在增廣路上的未飽和邊會多出一條反向邊，故增廣操作導致的邊數增長不會使總邊數超過原...