1樓：
在我的記憶中STL的search是沒有規定方法的，所以應該是實現相關的。在實踐中肯定不算快的，如果需要快速的字串匹配，可以考慮用專門的演算法。
一般的標準庫都是直接暴力比較的吧，最壞n*m，但是在字串比較隨機的實際場合基本都是符合期望時間O(n)的，使用KMP有一些缺點，比如需要預處理，需要額外的空間存放next函式，所以使用並不多。
在追求速度的時候，實際上有一些實踐中更適合的演算法，比如BM或者sunday。他們比KMP更快，因為期望的時間複雜度甚至連O(n)都不到。我可以簡單講一下快的原因：
kmp是基於自動機的演算法，至少待匹配的串你還要讀取一遍才能search完，但bm可以這樣：
假設在abbaaaa中找bbbbb，你先看第5個字元是a，在bbbbb中沒出現，於是可以看第10個字元了，你發現這個字串根本沒有10個字元，於是直接得出bbbbb不可能在這個字串中出現。
你會發現這樣你只檢視了字串中乙個字元，就得出了結果...... 當然我為了突出效果，選的例子比較極端，實際演算法也複雜一些，但是希望你能從中體會到一些演算法中的思想上精彩的東西，能感受到樂趣是最好的。
2樓：Htedsv
KMP時間複雜度確實要比傳統搜尋要低，不過實際效率一般只在ACM競賽中體現出來，對於隨機的字串匹配，還是傳統的匹配比較快（KMP常數比較大），因此一般的庫中都會用傳統的search。
所以STL的search是O(mn)的。
STL庫里的演算法時間複雜度和空間複雜度都是最佳的嗎？
Alinshans 肯定不都是最佳的。但肯定比99 的人寫的都要好。競賽中不一定要求時間複雜度最小，但是基本上 嚴格一點的 要求達到乙個級別。比如複雜度能O nlogn 的你不要搞O n STL中的演算法肯定能確保你能達到，如果你的寫法沒有問題，但死活超時了 卡常數 我覺得題目出得有問題。另，你知道...
資料結構中的時間複雜度和空間複雜度有沒有直接的關係？
1.在絕大多數情況下，演算法的時間複雜度不會低於空間複雜度 2.為什麼在一段時間內學習到的實現同樣目標演算法中，二者似乎矛盾對立？因為如果A演算法在時空上都優秀於B演算法，我覺得你不會去記B演算法就醬 不用很長各種各樣的論述，你記住幾點 其實只要記住最後一點就可以了 1，完成乙個既定目標的任意演算法...
演算法時間複雜度中的PSPACE,coNP complete,DP complete的含義。
A complete 的定義對於所有 class 都一樣,就是說 class A NP 中的所有問題都可以規約到某個特定問題 3 SAT 想看書去找 Sipser,或者 Arora Barak,或者 Goldreich,或者 Papadimitriou.至於 PSPACE 和 coNP,這兩個算常見...