1樓：冒泡
問題規模是指「輸入資料的『長度』」，這裡的長度一般來說就是用N進製（N>1）來表示的時候的位數
如果非要用「一進製」（其實應該沒這個詞），就像古埃及那種原始的表示法（N個棍棍表示數字N），那情況會不同，但是N大於1的時候沒啥差別的，因為O(log(N,a))=O(log(N,b))，可以用極限證明
繼續說回來，揹包是偽多項式主要是因為其複雜度O(NW)中的W是乙個「數值輸入」，其輸入規模其實是L=lgW，所以實際上複雜度應該是O(N*2^L)，指數級別的，這裡還隱含了乙個前提，就是N這個物品數量表示了物品資訊的輸入規模，意即每個物品的資訊的輸入長度是看做有乙個上限的，如果每個物品的重量、價值都可以很大，那麼情況就複雜一些，因為這時候加減法也需要看做是線性演算法了（但比較數字大小還是常數的，可以證明）
至於說為啥W需要是乙個變數而不能看做是有上限的，我覺得是因為DP過程需要乙個O(W)大小的陣列吧，實際上如果說W很大但是N個物品的所有重量組合又相對很少，可以改用備忘錄的做法，只記錄可能出現的W值，這時候演算法複雜度就可以跟W關係不大（但一般而言，還是跟2^N這個規模有關的，所以還是指數級別）
演算法時間複雜度為O（n ）的是什麼演算法？
子正 O n 的演算法不稱其為演算法，它意味著這個問題尚未解決。n稍微大一點，就會耗盡CPU的算力。它比不斷摺紙 圍棋盤上擺大公尺得到的數更大。這種 演算法 是進行演算法改進的物件。演算法老師沒有花力氣說明這種演算法的荒謬之處倒是個很不可思議的事情。n 是個很大的數，你可以用windows自帶的計算...
STL庫里的演算法時間複雜度和空間複雜度都是最佳的嗎？
Alinshans 肯定不都是最佳的。但肯定比99 的人寫的都要好。競賽中不一定要求時間複雜度最小，但是基本上 嚴格一點的 要求達到乙個級別。比如複雜度能O nlogn 的你不要搞O n STL中的演算法肯定能確保你能達到，如果你的寫法沒有問題，但死活超時了 卡常數 我覺得題目出得有問題。另，你知道...
資料結構中的時間複雜度和空間複雜度有沒有直接的關係？
1.在絕大多數情況下，演算法的時間複雜度不會低於空間複雜度 2.為什麼在一段時間內學習到的實現同樣目標演算法中，二者似乎矛盾對立？因為如果A演算法在時空上都優秀於B演算法，我覺得你不會去記B演算法就醬 不用很長各種各樣的論述，你記住幾點 其實只要記住最後一點就可以了 1，完成乙個既定目標的任意演算法...