1樓：jsx
例如你要求解一列數的和，需要輸入、求解、輸出。我們一般認為這是O(n)的。但是我們基本上要輸入數列的長度、數列的內容、求和、輸出結果，這至少要2n+2步，這兩個2都是常數。
但我們仍認為這是O(n)的。
你可以看一下大O表示法的定義，基本上是用乙個函式f(x)分別乘乙個數，在x足夠大的時候「壓住」執行的時間函式T(x)。例如T(x) 這裡，就是我們能夠忽略之前的那兩個2的原因。因為n足夠大時，2n+2<3n，可以把3n看作3*f(n)，f(n)=n。 2樓：Max 常數複雜度就是O(n),O(nlogn)這類式子的係數，這些係數雖然不會影響時間複雜度（因為在計算時已經忽略掉了），但是可能在評測時對你的答案起到影響，對於小規模資料，常數複雜度對執行時間的影響並不大，但是資料規模較大時，就不得不考慮常數帶來的影響了。 暴力卡常是可能打敗複雜度更優但常數較大的解法的。 比如對於 O(nlogn) 的解法,A程式對於每次查詢只需要800個單位的時間，B程式需要1200個單位的時間，這兩個程式其他地方是一樣優的，那麼A程式總共所用的時間假設是900ms勉強AC，B程式是1100ms，就TLE了，可見優秀的常數可以對演算法競賽題目起到很好的助力。 具體的優化方法：cin改用scanf或者快讀（最好不要關閉流同步因為說不定還要用string） 快速取模和快速冪 其他玄學的優化方法比如迴圈register int 3樓： 舉乙個簡單的例子吧。 (1) 題目給你 n 個整數，讓你求和。這道題很簡單，你邊讀入邊累加，求完了。時間複雜度是 O(n)。 (2) 題目給你 n 個整數，不僅讓你求和，還要你求出最大值。還是很簡單，你邊讀入邊累加，同時比較當前數字與已經出現的最大值哪個大。時間複雜度還是 O(n)。 上述兩個例子中，時間複雜度都記作 O(n)，但需要的執行時間顯然不同。如果忽略掉讀入資料的過程，你可以粗略認為第二個演算法執行時間是第乙個的二倍。也就是說，這兩個演算法的時間消耗差了乙個常數倍——2。 當然，在實際的程式或演算法設計中，你並不會精確地知道這個常數到底是多少，你只能知道，這個常數跟另乙個相比，是偏大還是偏小。比如，我們都知道，scanf/printf 比 cin/cout 快，是因為雖然兩者都實現了基本的輸入輸出功能，但後者在你看不到的地方做了很多必要的操作，拖慢了速度。這時候就可以說： scanf/printf 比 cin/cout 常數小。 再比如，你可能聽說過「char 陣列比 string 速度快」的說法。兩者的基礎功能都是存字串，但是 string 在背後維護了很多資料。比如，每次修改 string 物件，其 size() 的值都會發生變化，意味著 string 物件的長度等資訊是一直在維護的，維護這些資訊就需要時間成本。 但是 char 陣列根本就沒有 size() 這個東西，也就不需要花費時間來維護。維護與不維護之間，就差了乙個常數。不過這個常數是多少？ 咱不知道。只能說「string 比 char 陣列常數大，所以 string 慢。」 Alinshans 肯定不都是最佳的。但肯定比99 的人寫的都要好。競賽中不一定要求時間複雜度最小，但是基本上 嚴格一點的 要求達到乙個級別。比如複雜度能O nlogn 的你不要搞O n STL中的演算法肯定能確保你能達到，如果你的寫法沒有問題，但死活超時了 卡常數 我覺得題目出得有問題。另，你知道... A complete 的定義對於所有 class 都一樣,就是說 class A NP 中的所有問題都可以規約到某個特定問題 3 SAT 想看書去找 Sipser,或者 Arora Barak,或者 Goldreich,或者 Papadimitriou.至於 PSPACE 和 coNP,這兩個算常見... 子正 O n 的演算法不稱其為演算法，它意味著這個問題尚未解決。n稍微大一點，就會耗盡CPU的算力。它比不斷摺紙 圍棋盤上擺大公尺得到的數更大。這種 演算法 是進行演算法改進的物件。演算法老師沒有花力氣說明這種演算法的荒謬之處倒是個很不可思議的事情。n 是個很大的數，你可以用windows自帶的計算...STL庫里的演算法時間複雜度和空間複雜度都是最佳的嗎？
演算法時間複雜度中的PSPACE,coNP complete,DP complete的含義。
演算法時間複雜度為O（n ）的是什麼演算法？