更新時間:2022-05-31 來源:黑馬程序員 瀏覽量:
分析一個算法主要看這個算法的執(zhí)行需要多少機器資源。在各種機器資源中,時間和空間是兩個最主要的方面。因此,在進行算法分析時,人們最關心的就是運行算法所要花費的時間和算法中使用的各種數(shù)據所占用的空間資源。算法所花費的時間通常稱為時間復雜度,使用的空間資源稱為空間復雜度。接下來學習如何計算一個算法的時間復雜度和空間復雜度。
1.時間復雜度
在進行算法分析時,語句總的執(zhí)行次數(shù)T(n)是關于問題規(guī)模n的函數(shù),然后分析T(n)隨n的變化。
這樣用大寫的O來標記算法的時間復雜度,稱之為大O(Order的簡寫)標記法。一般隨著n的增長,T(n)也會隨之增長,其中T(n
)增長最慢者就是時間性能最優(yōu)的算法。
在計算時間復雜度的時候,根據T(n)與n的最高階數(shù)關系,我們給這些算法的復雜度進行了歸類,如表1所示。
當然還會有一些其他階數(shù)關系,這里只是列出了幾種較常見的關系。算法的執(zhí)行次數(shù)可能會與規(guī)模n呈現(xiàn)出這些關系,那么這些關系又是如何推導出來的呢?下面給出大O階的推導方法:
(1)用常數(shù)1取代運行中的所有加法常數(shù)。
(2)在修改后的運行次數(shù)函數(shù)中,只保留最高階項。
(3)如果最高階項存在,且不是1,則除去其常系數(shù),得到的結果就是大O階。
接下來通過分析幾段程序的執(zhí)行過程來推導出其時間復雜度,程序段1代碼如下所示:
int a=100; //執(zhí)行一次 int b=200; //執(zhí)行一次 int sum=a+b; //執(zhí)行一次 printf("&d\n",sum); //執(zhí)行一次
上述程序段有4行代碼,每一行執(zhí)行1次,加起來一共執(zhí)行了4次,f(n)=4,即T(n)=O(4)。根據推導方法中的第一條,將常數(shù)項以1代替。在保留其最高階項時,發(fā)現(xiàn)其沒有最高階項,因此該算法的時間復雜度為O(1),為常數(shù)階。程序段2代碼如下所示:
void func() { int i,sum=0; //執(zhí)行一次 for (i=0;i<=100;i++) { sum +=i; //執(zhí)行n次 } printf("sd\n",sum); //執(zhí)行一次 }
該程序段的執(zhí)行次數(shù)為1+n+1,則f(n)=n+2,即T(n)=O(n+2)。然后將常數(shù)項以1替換,且只保留最高階項,則得出T(n)=O(n),因此該算法的時間復雜度為O(n),為線性階。
程序段3代碼如下所示:
void func() { int i=l; do { i*=2; } while (i<n); }
在這個程序段中,當i<n時,循環(huán)結束。如果循環(huán)了f(n)次,則2(fn)=n,即f(n)=log2n,T(n)=O(log2n)。然后消除常系數(shù),保留最高階項,最后得出T(n)=O(logn),為對數(shù)階。
用大O階來推導算法的復雜度并不難,讀者在以后的學習中設計算法,就可以用此法來估測算法的優(yōu)劣。
2.空間復雜度
空間復雜度是對一個算法在運行過程中所占存儲空間大小的度量,一般也作為問題規(guī)模n的函數(shù),以數(shù)量級形式給出,格式如下所示:
一個算法的存儲量包括輸入數(shù)據所占空間、程序本身所占空間和輔助變量所占空間。在對算法進行分析時,只考慮輔助變量所占空間。若所需輔助空間相對于輸入數(shù)據量來說是常數(shù),則稱此算法為原地工作。若所用空間量依賴于特定的輸入,則除了有特殊說明外,均按最壞情況考慮。
有時候,在寫代碼時可以用空間來換取時間,例如,寫一個算法來判斷某年是否是閏年,這樣每輸入一個年份都要調用算法去判斷一下,在時間上就有點復雜。為了提高效率,可以用空間來換取時間,即建立一個大小合適的數(shù)據,編號從0到n,如果是閏年,則存入數(shù)據1,否則存入數(shù)據0。這樣只要通過判斷年份編號上存儲的是0還是1就知道該年份是否是閏年了。
用空間換取時間可以將運算最小化,但這兩種情況哪種更好,要結合具體情況而定。一般情況下,都是用時間復雜度來度量算法,當不加限定地使用“復雜度”這一術語時,都是指時間復雜度。