1.2.5　算法的時間復雜度和空間復雜度

所謂算法的時間復雜度，是指執行算法所需要的計算工作量。一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數f（n），算法的時間度量記作T（n）=O（f（n））。它表示隨著問題規模n的增長，算法執行時間的增長率和f（n）的增長率相同，稱為算法的漸近時間復雜度（簡稱時間復雜度）。例如：

（1）{a=3；b=4；sum=a+b；}

（2）for（i=1；i<=n；i++）s+=x；

（3）for（i=1；i<=n；i++）

for（j=1；j<=n；j++）x=x+2；

3個程序段的時間復雜度分別為O（1）、O（n）、O（n2）。

有些情況下，算法中基本操作重復執行的次數隨問題的輸入數據的不同而不同，例如，對n個整數進行排序，此時取其平均時間復雜度。但當平均時間復雜度無法計算時，則取其最壞情況下的時間復雜度。

算法的空間復雜度一般是指執行這個算法所需要的內存空間，記作S（n）=O（g（n）），其中n為問題的規模，它表示隨著問題規模n的增大，算法運行所需存儲量的增長率與g（n）的增長率相同。一個上機執行的程序除了需要存儲空間來寄存本身所用指令、常數、變量和輸入數據外，也需要一些對數據進行操作的工作單元和存儲一些實現計算機所需信息的輔助空間。若輸入數據所占空間只取決于問題本身，和算法無關，則只需要分析除輸入和程序外的輔助變量所占的額外空間，否則應同時考慮輸入本身所需的空間（和輸入數據的表示形式有關）。若所需的額外空間相對于輸入數據量來說是常數，則稱此算法為原地工作。若所需存儲量依賴于特定的輸入，則通常按最壞情況考慮。