1樓：XonAzis
所謂的「常數」其實是對於時間複雜度而言的。
眾所周知，要計算乙個演算法的時間複雜度，都會想想將某變數設定為無窮大，那麼最後會得出乙個什麼式子。
就拿乙個函式來做乙個簡單的例子好了。
那麼如果我們把x設為無窮大，那麼我們可以看到，那個 會變得異常之大，以至於剩下的 都可以省略，那麼最後計算出來，時間複雜度就是 。剩下的 ，就是常數咯。
那麼這麼看來，對於常數，其實你如果有耐心，有毅力，是可以計算出來的，具體可以詳見《演算法導論》的前3章，那裡有非常詳細的解析。
凡是學到提高的應該都知道幾種資料結構吧：如線段樹，st表之類的。線段樹的查詢，時間複雜度是 ，而st表的時間複雜度是 。這樣看起來st表要比線段樹厲害很多，但事實是這樣的嗎？
其實並不是。
眾所周知，st表在之前有著 的預處理，這樣一看其實與線段樹差不了多少了，這就是所謂的「常數」吧。
真實經歷，我的乙個同學在做另乙個毒瘤同學出的題，結果90，因為用了vector。將vector換成陣列後，立馬就滿分了。各位也應該有把cin改成scanf甚至快讀拿分的經歷吧。
那麼這個常數你就無法算出來了，因為這是這個語言內部的屬性。除非你是c++之父，不然，有那個人能具體說出cin和scanf的區別？為什麼scanf比cin快？
我相信有時間煩這些的都不會來學OI，不學OI的也不用管這麼一點點時間吧。。。
作為學OI的，你只需要知道，什麼比什麼快這一事實不就好了嘛！
演算法時間複雜度中的PSPACE,coNP complete,DP complete的含義。
A complete 的定義對於所有 class 都一樣,就是說 class A NP 中的所有問題都可以規約到某個特定問題 3 SAT 想看書去找 Sipser,或者 Arora Barak,或者 Goldreich,或者 Papadimitriou.至於 PSPACE 和 coNP,這兩個算常見...
資料結構中的時間複雜度和空間複雜度有沒有直接的關係？
1.在絕大多數情況下，演算法的時間複雜度不會低於空間複雜度 2.為什麼在一段時間內學習到的實現同樣目標演算法中，二者似乎矛盾對立？因為如果A演算法在時空上都優秀於B演算法，我覺得你不會去記B演算法就醬 不用很長各種各樣的論述，你記住幾點 其實只要記住最後一點就可以了 1，完成乙個既定目標的任意演算法...
STL庫里的演算法時間複雜度和空間複雜度都是最佳的嗎？
Alinshans 肯定不都是最佳的。但肯定比99 的人寫的都要好。競賽中不一定要求時間複雜度最小，但是基本上 嚴格一點的 要求達到乙個級別。比如複雜度能O nlogn 的你不要搞O n STL中的演算法肯定能確保你能達到，如果你的寫法沒有問題，但死活超時了 卡常數 我覺得題目出得有問題。另，你知道...