什么是時間復(fù)雜度，算法中某個函數(shù)有n次基本操作重復(fù)執(zhí)行，用T(n)表示，現(xiàn)在有某個輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。通俗一點講，其實所謂的時間復(fù)雜度，就是找了一個同樣曲線類型的函數(shù)f(n)來表示這個算法的在n不斷變大時的趨勢 。當(dāng)輸入量n逐漸加大時，時間復(fù)雜性的極限情形稱為算法的“漸近時間復(fù)雜性”。
計算時間復(fù)雜度的方法：
- 用常數(shù)1代替運行時間中的所有加法常數(shù)
- 修改后的運行次數(shù)函數(shù)中，只保留最高階項
- 去除最高階項的系數(shù)
按數(shù)量級遞增排列，常見的時間復(fù)雜度有：
隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。
1. 常數(shù)階
這種與問題規(guī)模的大小無關(guān)（n的多少），執(zhí)行時間恒定的算法，我們稱之為具有O(1)的時間復(fù)雜度，又叫常數(shù)階。
int sum = 0, n = 100; /*執(zhí)行一次*/
sum = (1 + n) * n / 2; /*執(zhí)行一次*/
printf("%d",sum); /*執(zhí)行一次*/
2. 線性階
線性階的循環(huán)結(jié)構(gòu)會復(fù)雜很多。要確定某個算法的階次，我們常常需要確定某個特定語句或某個語句集運行的次數(shù)。因此，我們要分析算法的復(fù)雜度，關(guān)鍵就是要分析循環(huán)結(jié)構(gòu)的運行情況。
下面這段代碼，它的循環(huán)的時間復(fù)雜度為O(n)， 因為循環(huán)體中的代碼須要執(zhí)行n次。
int i;
for(i = 0; i < n; i++){
/*時間復(fù)雜度為O(1)的程序步驟序列*/
}
3. 對數(shù)階
int count = 1;
while (count < n){
count = count * 2;
/*時間復(fù)雜度為O(1)的程序步驟序列*/
}
由于每次count乘以2之后，就距離n更近了一分。 也就是說，有多少個2相乘后大于n，則會退出循環(huán)。 由2^x=n 得到x=log2(n)。 所以這個循環(huán)的時間復(fù)雜度為O(log2(n))。
4. 平方階
這段代碼的時間復(fù)雜度為O(n^2)。
int i, j;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
/*時間復(fù)雜度為O(1)的程序步驟序列*/
}
循環(huán)的時間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以該循環(huán)運行的次數(shù)。
int i, j;
for(i = 0; i < n; i++){
for(j = i; j < n; j++){ /*注意j = i而不是0*/
/*時間復(fù)雜度為O(1)的程序步驟序列*/
}
}
由于當(dāng)i=0時，內(nèi)循環(huán)執(zhí)行了n次，當(dāng)i = 1時，執(zhí)行了n-1次，……當(dāng)i=n-1時，執(zhí)行了1次。所以總的執(zhí)行次數(shù)為:
根據(jù)時間復(fù)雜度的算法，第一條，沒有加法常數(shù)不予考慮；第二條，只保留最高階項，因此保留時(n^2)/2; 第三條，去除這個項相乘的常數(shù)，也就是去除1/2，最終這段代碼的時間復(fù)雜度為O(n^2)。
5. 立方階
int i, j;
for(i = 1; i < n; i++)
for(j = 1; j < n; j++)
for(j = 1; j < n; j++){
/*時間復(fù)雜度為O(1)的程序步驟序列*/
}
最壞時間復(fù)雜度和平均時間復(fù)雜度
- 最壞情況下的時間復(fù)雜度稱
最壞時間復(fù)雜度。一般不特別說明，討論的時間復(fù)雜度均是最壞情況下的時間復(fù)雜度。
這樣做的原因是：最壞情況下的時間復(fù)雜度是算法在任何輸入實例上運行時間的上界，這就保證了算法的運行時間不會比任何更長。平均時間復(fù)雜度是指所有可能的輸入實例均以等概率出現(xiàn)的情況下，算法的期望運行時間。設(shè)每種情況的出現(xiàn)的概率為pi,平均時間復(fù)雜度則為sum(pi*f(n))
