1樓：夏洛克
人類最古老的演算法：查表法，就是空間換時間的典型。
九九乘法表就是通過耗費一定的大腦空間來記憶這個表，來達提高乘法的計算速度的目的。
乘法真正的規模是乙個個去數所耗費的步驟
2樓：
你可以把時間和空間想象成正交的關係。
而乙個問題的不同解只是這個正交空間的某乙個點或者某乙個集合。
這樣看的話，空間換時間只是在兩個解做權衡而已，當然也可能存在空間一樣或者更小，同時時間也更小的解法。
3樓：趙玖桐
我認為time-memory trade off的核心在於子問題的規模。
面對複雜的大問題，我們往往需要解決乙個又乙個的子問題。這種思想和分治遞迴是有所不同的，因為子問題不一定是縮小規模的大問題。
比如大問題:午飯吃什麼？
分為子問題便是 :
中午在哪兒吃？
那家店(家裡)有什麼菜？
我更想吃哪些菜？
每一種選擇背後的代價是啥？(費錢好吃節省時間健康)
如果我們已經有了乙個問題的答案了(如「我王境澤就算餓死，從外邊跳下去，也不會吃你們一點東西」)，就可以縮小我們所要考慮的子問題的數量，從而節省時間。
反之亦然，如果你不想提前記答案，臨場現算也是可以的(是不是很像某些同學考數學物理時的樣子)。
總而言之，子問題一直都是那麼多，時間可以用來解決子問題(通過臨場計算)，空間也可以用來解決子問題(通過儲存子問題的答案)。
4樓：
我覺得這更像乙個經濟學問題。因為空間主要是記憶體空間，有時候也指磁碟空間。而時間就是運算時間。
空間是可以花錢買的，加記憶體就行了，時間是買不到的。對實時性有要求時間就是死的限制。
5樓：
我相信會有專門的文獻可以解釋這個問題，但是我沒有足夠的專業知識來回答，所以我寫下了看到這個問題的之後我的一些想法，希望你能從此得到一點有用的資訊。
「空間換時間」或者「時間換空間」這樣的概念不僅僅在演算法中，在我們平時生活中也會經常遇到類似的概念。我們可以將這個問題抽象一下，將「演算法」對應成「目標」,「時間」和「空間」則對應了要達到這個「目標」需要的一些「要素」或者"資源"。所以這個問題就變成了，完成乙個「目標」需要怎樣的「資源"分配的問題了。
你可以舉出很多相應的例子，比如你想去某個地方，你可以選擇很多種出行方式，相應地需要付出不同的資源。可以步行去，不花錢但需要花很多時間，你也可以打車去，用金錢換時間，多花錢少花時間，或者折衷點坐公車地鐵。所以你可以看到，完成同樣乙個目標（去某個地方），簡單地只考慮時間和金錢這兩種資源，你就可以有很多種資源分配方式了。
而你對這兩種資源的價值定位，決定了你傾向什麼出行方式，趕時間你可能就打車了，要是心疼錢，你可能會步行也說不定。再進一步思考，能夠這麼轉換的前提也是因為兩種資源之間是存在轉換路徑的，比如在出行方式例子中，是因為你有條件可以花錢買到更快的交通工具的服務，如果你孤身處於荒島之上，再有錢可能也打不到車的，那就不能轉換了。回到你演算法的例子，所謂空間換時間，也是因為這二者存在轉換路徑，是因為你演算法中有些操作需要花時間去找到某些東西（空間位置），同樣的資料量下，花空間少則對應規則可能複雜些，那麼花時間多；花空間多則對應規則簡單些，則花時間少。
如果你的演算法中，空間是固定的，那麼就換不了了。如果你接受我的這種說法的話，那麼對於」演算法能否被優化「這問題，你可以想想，你的問題裡哪種要素或者資源是當前更迫切需要優化的，是空間還是時間，然後按需分配。那麼，有沒有在一種資源（空間）消耗相同的情況下，另一種資源（時間）也能減少的情況呢？
有，那你可能需要引入第三種資源了，比如偉大的創造力，前人或者你自己花了大量精力想出來的更優演算法也是耗費了很多資源的。
如何看待以時間換空間的說法
一開始接觸到這句話時，我更多的認為這是一種無能的表現。只有無能的人才會拿時間換空間當藉口。因為我們一直都是時間就是金錢，金錢就是效率的思想。後來自己逐漸成長了。當自己面對困難和苦難越來越多而自己總是顯得束手無策時，回過來想 時間換空間 這句話是客觀規律演變過程的一種中庸選擇。沒辦法！現實與美好願望兩...
演算法時間複雜度中的PSPACE,coNP complete,DP complete的含義。
A complete 的定義對於所有 class 都一樣,就是說 class A NP 中的所有問題都可以規約到某個特定問題 3 SAT 想看書去找 Sipser,或者 Arora Barak,或者 Goldreich,或者 Papadimitriou.至於 PSPACE 和 coNP,這兩個算常見...
STL庫里的演算法時間複雜度和空間複雜度都是最佳的嗎？
Alinshans 肯定不都是最佳的。但肯定比99 的人寫的都要好。競賽中不一定要求時間複雜度最小，但是基本上 嚴格一點的 要求達到乙個級別。比如複雜度能O nlogn 的你不要搞O n STL中的演算法肯定能確保你能達到，如果你的寫法沒有問題，但死活超時了 卡常數 我覺得題目出得有問題。另，你知道...