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