資料結構中的時間複雜度和空間複雜度有沒有直接的關係？

1樓：

1.在絕大多數情況下，演算法的時間複雜度不會低於空間複雜度…2.為什麼在一段時間內學習到的實現同樣目標演算法中，二者似乎矛盾對立？

因為如果A演算法在時空上都優秀於B演算法，我覺得你不會去記B演算法就醬

2樓：

不用很長各種各樣的論述，你記住幾點（其實只要記住最後一點就可以了）：

1，完成乙個既定目標的任意演算法，總有乙個（現實）的最高時間複雜度和最大空間需求。

2，最高時間複雜度不一定對應最少空間需求。

3，同樣，最大空間需求不一定對應最低時間複雜度。

4，在通常情況下，放棄兩者之一，能加速另外一側，但是不強相關。

5，通常時間複雜度O^2以上的演算法，都存在增加空間開銷而降低時間複雜度的同質演算法（但是可能不穩定）

6，所以看待乙個演算法的三個關鍵點在於（是的，提問忘記了演算法當中乙個最重要的點：穩定性）時間複雜度，空間開銷，和穩定性這三要素

7，演算法三要素構成乙個抽象的三角形，其中任一邊變長變短，其他各邊相應變化，這樣記憶就很方便了

3樓：msldxy

其實光看執行時間和記憶體消耗這兩個詞，就不會認為會有什麼直接聯絡吧。

兩者有一定聯絡但不是必然，即一些情況下它們是有聯絡的，比如時空權衡的互相轉換。

4樓：冒泡

從你的問法來看，似乎是想說二者有矛盾的關係，這在某些時候有，比如dp就有空間換時間的思想，但要說直接和必然的矛盾關係，是沒有的

非要說有直接關係應該就只有一句：時間複雜度不可能小於空間複雜度，因為你要訪問的空間如果是f(N)的大小，而每個單位的空間至少訪問一次，每次常數時間，那麼時間複雜度必然是Ω(f(N))的，有時候證明下界會用到這個結論

注意這裡的空間複雜度是指演算法執行中訪問到的空間，像二分查詢，總資料集合是預先存在好的，客觀存在但並不一定都在演算法執行中訪問到，因此看上去占用空間是O(N)而時間是O(lgN)，這是看問題角度不同，換句話說如果將原始資料讀入也計算在內，任何演算法都不可能是亞線性了

5樓：WZJRJ28

你舉得例子是錯的，但的確很多問題可以用空間換時間，比如記憶化搜尋，很多資料結構也可以看做是通過多記錄一些冗餘資訊來達到空間換時間的目的。

6樓：Joseph Holy

演算法的時間複雜度的計算，一般是預設在絕對理想的計算環境下的乙個數學推導或者數學歸納。所以遞迴還是遍歷從數學定義上來講是沒有區別的。說遞迴空間複雜度度高主要有兩個方面，第乙個是在演算法書講遞迴演算法的時候會舉例一些本身時間複雜度的很高的例子，比如斐波那契數列的遞迴實現。

然後遞迴因為涉及到多層的函式呼叫，但是函式呼叫的時候會涉及到一作業系統的函式呼叫棧這部分。這部分棧道特點就是他的空間是有限且不會很大比如4mb。並且在函式呼叫的時候還需要儲存一系列函式的狀態。

因此很多資料結構書會說遞迴會用更多的空間。而用遍歷的時候，所耗費的空間主要在堆heap上開闢，heap本身的size要遠遠大於棧stack。且因為沒有多層函式呼叫不用儲存函式呼叫的中間狀態，所以某種程度上來講用遍歷實現同乙個演算法比遞迴要消耗更少的記憶體。

但是理論上還是一致的。