什么是時(shí)間復(fù)雜度腻要，算法中某個(gè)函數(shù)有n次基本操作重復(fù)執(zhí)行，用T(n)表示，現(xiàn)在有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí)谢肾，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度捎谨，簡(jiǎn)稱時(shí)間復(fù)雜度。通俗一點(diǎn)講憔维，其實(shí)所謂的時(shí)間復(fù)雜度涛救，就是找了一個(gè)同樣曲線類型的函數(shù)f(n)來(lái)表示這個(gè)算法的在n不斷變大時(shí)的趨勢(shì) 。當(dāng)輸入量n逐漸加大時(shí)业扒，時(shí)間復(fù)雜性的極限情形稱為算法的“漸近時(shí)間復(fù)雜性”检吆。
計(jì)算時(shí)間復(fù)雜度的方法：
- 用常數(shù)1代替運(yùn)行時(shí)間中的所有加法常數(shù)
- 修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)
- 去除最高階項(xiàng)的系數(shù)
按數(shù)量級(jí)遞增排列程储，常見(jiàn)的時(shí)間復(fù)雜度有：
隨著問(wèn)題規(guī)模n的不斷增大蹭沛，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低章鲤。
1. 常數(shù)階
這種與問(wèn)題規(guī)模的大小無(wú)關(guān)（n的多少）摊灭，執(zhí)行時(shí)間恒定的算法，我們稱之為具有O(1)的時(shí)間復(fù)雜度败徊，又叫常數(shù)階帚呼。
int sum = 0, n = 100; /*執(zhí)行一次*/
sum = (1 + n) * n / 2; /*執(zhí)行一次*/
printf("%d",sum); /*執(zhí)行一次*/
2. 線性階
線性階的循環(huán)結(jié)構(gòu)會(huì)復(fù)雜很多。要確定某個(gè)算法的階次皱蹦，我們常常需要確定某個(gè)特定語(yǔ)句或某個(gè)語(yǔ)句集運(yùn)行的次數(shù)萝挤。因此御毅，我們要分析算法的復(fù)雜度，關(guān)鍵就是要分析循環(huán)結(jié)構(gòu)的運(yùn)行情況怜珍。
下面這段代碼端蛆，它的循環(huán)的時(shí)間復(fù)雜度為O(n)， 因?yàn)檠h(huán)體中的代碼須要執(zhí)行n次酥泛。
int i;
for(i = 0; i < n; i++){
/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/
}
3. 對(duì)數(shù)階
int count = 1;
while (count < n){
count = count * 2;
/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/
}
由于每次count乘以2之后今豆，就距離n更近了一分。 也就是說(shuō)柔袁，有多少個(gè)2相乘后大于n呆躲，則會(huì)退出循環(huán)。 由2^x=n 得到x=log2(n)捶索。 所以這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(log2(n))插掂。
4. 平方階
這段代碼的時(shí)間復(fù)雜度為O(n^2)。
int i, j;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/
}
循環(huán)的時(shí)間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以該循環(huán)運(yùn)行的次數(shù)腥例。
int i, j;
for(i = 0; i < n; i++){
for(j = i; j < n; j++){ /*注意j = i而不是0*/
/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/
}
}
由于當(dāng)i=0時(shí)辅甥，內(nèi)循環(huán)執(zhí)行了n次，當(dāng)i = 1時(shí)燎竖，執(zhí)行了n-1次璃弄，……當(dāng)i=n-1時(shí)，執(zhí)行了1次构回。所以總的執(zhí)行次數(shù)為:
根據(jù)時(shí)間復(fù)雜度的算法夏块，第一條，沒(méi)有加法常數(shù)不予考慮纤掸；第二條脐供，只保留最高階項(xiàng)，因此保留時(shí)(n^2)/2; 第三條借跪，去除這個(gè)項(xiàng)相乘的常數(shù)患民，也就是去除1/2，最終這段代碼的時(shí)間復(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++){
/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/
}
最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度
- 最壞情況下的時(shí)間復(fù)雜度稱
最壞時(shí)間復(fù)雜度匹颤。一般不特別說(shuō)明，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度托猩。
這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界印蓖，這就保證了算法的運(yùn)行時(shí)間不會(huì)比任何更長(zhǎng)。平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下京腥，算法的期望運(yùn)行時(shí)間赦肃。設(shè)每種情況的出現(xiàn)的概率為pi,平均時(shí)間復(fù)雜度則為sum(pi*f(n))
