1樓：Joker
現在很多機器（膝上型電腦）大約每秒鐘能夠執行大約v=10^9條指令（這個數量級）。O(n^2)的演算法可以認為它有不超過c*n^2條需要執行的指令。c是某個常數，可以很大，c通常的程式在1～10之間。
秒數大約c*n^2/v。你如果時間複雜度沒算錯，那麼大概是c很大，或者v很小。要麼是演算法有問題，要麼是機器有問題。
（秒數只精確到數量級。
2樓：Octopus136
一般計算機的執行效率大概也能在1e8次運算每秒n=2e4時，O(n)的複雜度的理論運算時間是2e-4秒左右，如果跑了10秒的話，可能是你的時間複雜度分析有誤，10秒大概是O(n^2)的複雜度的效率。
當然，如果你的計算機在極端情況下真的在O(n)內跑出了10s的好成績，可以推測其效率為1s進行2e3次運算，在運算量為n^2，也就是4e8時，大概需要執行2e5秒，也就是55.56小時左右。
因為現在這麼慢的計算機已經不多見了，一般來說在n=2e4時O(n^2)的複雜度在10s內可以執行完畢，請檢查你的時間複雜度是否分析正確。
3樓：lishichengyan
你要理解O記號表示的是乙個函式族，是一種趨勢，而不是乙個具體的數值。
常數, n, n^2, n^2+9999999999999999n+99999999999999n^(1/2)+999999999999999都算O(n^2)……
STL庫里的演算法時間複雜度和空間複雜度都是最佳的嗎？
Alinshans 肯定不都是最佳的。但肯定比99 的人寫的都要好。競賽中不一定要求時間複雜度最小，但是基本上 嚴格一點的 要求達到乙個級別。比如複雜度能O nlogn 的你不要搞O n STL中的演算法肯定能確保你能達到，如果你的寫法沒有問題，但死活超時了 卡常數 我覺得題目出得有問題。另，你知道...
演算法時間複雜度中的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自帶的計算...