考點2 算法的復雜度
1算法的時間復雜度
算法的時間復雜度，是指執(zhí)行算法所需要的計算工作量。同一個算法用不同的語言實現(xiàn)，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行，效率均不同。這表明使用絕對的時間單位衡量算法的效率是不合適的。撇開這些與計算機硬件、軟件有關的因素，可以認為一個特定算法“運行工作量”的大小，只依賴于問題的規(guī)模(通常用整數(shù)n表示)，它是問題的規(guī)模函數(shù)。即
算法的工作量=f(n)
例如，在N×N矩陣相乘的算法中，整個算法的執(zhí)行時間與該基本操作(乘法)重復執(zhí)行的次數(shù)n3成正比，也就是時間復雜度為n3，即
f(n)=O(n3)
在有的情況下，算法中的基本操作重復執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。例如在起泡排序的算法中，當要排序的數(shù)組a初始序列為自小至大有序時，基本操作的執(zhí)行次數(shù)為氏當初始序列為自大至小有序時，基本操作的執(zhí)行次數(shù)為n(n- 1)/2。對這類算法的分析，可以采用以下兩種方法來分析。
(1)平均性態(tài)(Average Behavior)
所謂平均性態(tài)是指各種特定輸入下的基本運算次數(shù)的加權平均值來度量算法的工作量。
設x是所有可能輸入中的某個特定輸入，p(x)是x出現(xiàn)的概率(即輸入為x的概率)，t(x)是算法在輸入為x時所執(zhí)行的基本運算次數(shù)，則算法的平均性態(tài)定義為
其中Dn表示當規(guī)模為n時，算法執(zhí)行的所有可能輸入的集合。
(2)最壞情況復雜性(Worst-case Complexity)
所謂最壞情況分析，是指在規(guī)模為n時，算法所執(zhí)行的基本運算的次數(shù)。
2算法的空間復雜度
算法的空間復雜度是指執(zhí)行這個算法所需要的內存空間。
一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結構所需要的附加存儲空間。如果額外空間量相對于問題規(guī)模來說是常數(shù)，則稱該算法是原地(in place)工作的。在許多實際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技術，以便盡量減少不必要的額外空間。
1算法的時間復雜度
算法的時間復雜度，是指執(zhí)行算法所需要的計算工作量。同一個算法用不同的語言實現(xiàn)，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行，效率均不同。這表明使用絕對的時間單位衡量算法的效率是不合適的。撇開這些與計算機硬件、軟件有關的因素，可以認為一個特定算法“運行工作量”的大小，只依賴于問題的規(guī)模(通常用整數(shù)n表示)，它是問題的規(guī)模函數(shù)。即
算法的工作量=f(n)
例如，在N×N矩陣相乘的算法中，整個算法的執(zhí)行時間與該基本操作(乘法)重復執(zhí)行的次數(shù)n3成正比，也就是時間復雜度為n3，即
f(n)=O(n3)
在有的情況下，算法中的基本操作重復執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。例如在起泡排序的算法中，當要排序的數(shù)組a初始序列為自小至大有序時，基本操作的執(zhí)行次數(shù)為氏當初始序列為自大至小有序時，基本操作的執(zhí)行次數(shù)為n(n- 1)/2。對這類算法的分析，可以采用以下兩種方法來分析。
(1)平均性態(tài)(Average Behavior)
所謂平均性態(tài)是指各種特定輸入下的基本運算次數(shù)的加權平均值來度量算法的工作量。
設x是所有可能輸入中的某個特定輸入，p(x)是x出現(xiàn)的概率(即輸入為x的概率)，t(x)是算法在輸入為x時所執(zhí)行的基本運算次數(shù)，則算法的平均性態(tài)定義為
其中Dn表示當規(guī)模為n時，算法執(zhí)行的所有可能輸入的集合。
(2)最壞情況復雜性(Worst-case Complexity)
所謂最壞情況分析，是指在規(guī)模為n時，算法所執(zhí)行的基本運算的次數(shù)。
2算法的空間復雜度
算法的空間復雜度是指執(zhí)行這個算法所需要的內存空間。
一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結構所需要的附加存儲空間。如果額外空間量相對于問題規(guī)模來說是常數(shù)，則稱該算法是原地(in place)工作的。在許多實際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技術，以便盡量減少不必要的額外空間。