發(fā)布時間: 2025年01月01日 14:09
算法的空間復(fù)雜度
空間復(fù)雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度,記做S(n)=O(f(n))。比如直接插入排序的時間復(fù)雜度是O(n^2),空間復(fù)雜度是O(1) 。而一般的遞歸算法就要有O(n)的空間復(fù)雜度了,因為每次遞歸都要存儲返回信息。一個算法的優(yōu)劣主要從算法的執(zhí)行時間和所需要占用的存儲空間兩個方面衡量。
分析一個算法所占用的存儲空間要從各方面綜合考慮。如對于遞歸算法來說,一般都比較簡短,算法本身所占用的存儲空間較少,但運行時需要一個附加堆棧,從而占用較多的臨時工作單元;若寫成非遞歸算法,一般可能比較長,算法本身占用的存儲空間較多,但運行時將可能需要較少的存儲單元。