前言
上一篇《數(shù)據(jù)結構和算法》中我介紹了數(shù)據(jù)結構的基本概念，也介紹了數(shù)據(jù)結構一般可以分為邏輯結構和物理結構。邏輯結構分為集合結構昌罩、線性結構阱穗、樹形結構和圖形結構饭冬。物理結構分為順序存儲結構和鏈式存儲結構。并且也介紹了這些結構的特點揪阶。然后昌抠，又介紹了算法的概念和算法的5個基本特性，分別是輸入鲁僚、輸出炊苫、有窮性、確定性和可行性冰沙。最后說闡述了一個好的算法需要遵守正確性侨艾、可讀性、健壯性拓挥、時間效率高和存儲量低唠梨。其實，實現(xiàn)效率和存儲量就是時間復雜度和空間復雜度侥啤。本篇我們就圍繞這兩個"復雜度"展開說明当叭。在真正的開發(fā)中茬故，時間復雜度尤為重要，空間復雜度我們不做太多說明科展。
時間復雜度
時間復雜度和空間復雜度是算法效率的度量方法均牢。也就是說，一個好的算法取決于它的時間復雜度和空間復雜度才睹。
函數(shù)的漸近增長：給定兩個函數(shù)f(n)和g(n)徘跪，如果存在一個整數(shù)N，使得對于所有的n>N琅攘，f(n)總是比g(n)大垮庐。那么，我們說f(n)的增長漸近快于g(n)坞琴。
翻譯過來就是：如果存在一個臨界值哨查，使得f(n)>g(n)永遠成立，那么我們就認為"f(n)的增長漸近快于g(n)"剧辐。
這里我拿3個函數(shù)的增長曲線來說明問題寒亥。如下圖：
函數(shù)一：X = 3n 注釋：3乘以n
函數(shù)二：Y = 2n^2 注釋:n的平方乘以2
函數(shù)三：Z = 2n^2 + 3n 注釋：n的平方乘以2 + 3乘以n
當n=1時，Y < X < Z.
當n=2時荧关，X < Y < Z.
所以溉奕，存在一個值，這個值位于1和2之間忍啤，使得X < Y < Z永遠成立加勤。我們就稱Y的漸進增長快于X，Z的漸進增長快于Y同波，當然鳄梅，根據(jù)傳遞性規(guī)則，Z的漸進增長也快于X未檩。
定義
算法時間復雜度的定義：在進行算法分析時戴尸，語句總的執(zhí)行次數(shù)T(n)是關于問題規(guī)模n的函數(shù)，進而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級冤狡。
算法的時間復雜度孙蒙，也就是算法的時間量度，記作：T(n)= O(f(n))筒溃。
它表示隨問題規(guī)模n的增大马篮，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復雜度怜奖，簡稱為時間復雜度浑测。其中f(n)是問題規(guī)模n的某個函數(shù)。
時間復雜度計算方法
1.用常數(shù)1取代運行時間中的所有加法常數(shù)。
2.在修改后的運行次數(shù)函數(shù)中迁央，只保留最高階項掷匠。
3.如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)岖圈。
最后讹语，得到的最后結果就是時間復雜度。
常見的時間復雜度
按數(shù)量級遞增排列蜂科，常見的時間復雜度有：
常數(shù)階O(1),對數(shù)階O( log n ),線性階O(n),線性對數(shù)階O(nlog2n),平方階O(n2)顽决，立方階O(n3),...，k次方階O(nk),指數(shù)階O(2n)导匣。隨著問題規(guī)模n的不斷增大才菠，上述時間復雜度不斷增大，算法的執(zhí)行效率越低贡定。
也就是：
常用的時間復雜度所耗費的時間從小到大依次是：O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
常數(shù)階
// 常數(shù)階
int n = 0;
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
上面這段代碼的時間復雜度是O(1)赋访。因為，按照時間復雜度的定義來說缓待，n和問題的規(guī)模沒有關系蚓耽。當然，按照時間復雜度計算方法第一條也可以得出結果為O(1)旋炒。
線性階
// 線性階int i ,
n = 10086, sum = 0;
for( i=0; i < n; i++ )
{
sum = sum + i;
}
上面這段代碼的時間復雜度是O(n)步悠，因為問題規(guī)模會隨著n的增長而變得越來越大，并且這種增長是線性的国葬。
平方階
// 平方階
int i, j, n = 998;
for( i=0; i < n; i++ )
{
for( j=0; j < n; j++ )
{
printf(“oneSong”);
}
}
上面這段代碼外層執(zhí)行n次贤徒，外層循環(huán)每執(zhí)行一次芹壕，內(nèi)層循環(huán)就執(zhí)行n次汇四，那總共程序想要從這兩個循環(huán)出來，需要執(zhí)行n*n次踢涌，也就是n的平方通孽。所以這段代碼的時間復雜度為O(n^2)。
對數(shù)階
// 對數(shù)階
int i = 1, n = 100;
while( i < n )
{
i = i * 2;
}
由于每次i*2之后睁壁，就距離n更近一步背苦，假設有x個2相乘后大于或等于n，則會退出循環(huán)潘明。于是由2^x = n得到x = log(2)n行剂，所以這個循環(huán)的時間復雜度為O(logn)。
算法的空間復雜度
算法的空間復雜度通過計算算法所需的存儲空間實現(xiàn)钳降，算法的空間復雜度的計算公式記作：S(n)=O(f(n))厚宰，其中，n為問題的規(guī)模，f(n)為語句關于n所占存儲空間的函數(shù)铲觉。
在程序開發(fā)中澈蝙，我們所指的復雜度不做特別說明的情況下，就是指時間復雜度∧煊模現(xiàn)在的硬件發(fā)展速度之快使得我們完全可以不用考慮算法所占的內(nèi)存灯荧，通常都是用空間換取時間。加之算法的空間復雜度比較難算盐杂，所以逗载，無論是在考試中還是在項目開發(fā)中，我們都側(cè)重于時間復雜度链烈。所以撕贞，空間復雜度，略過测垛。
圖片來源參考自:魚C工作室捏膨。感謝魚C工作室貢獻出了這么好的圖片。
如非特別說明食侮，筆者所有文章都是原創(chuàng)文章号涯。如果您喜歡這篇文章，轉(zhuǎn)載請注明出處锯七。如果您對數(shù)據(jù)結構感興趣链快，請關注我，后續(xù)會更新大量精品文章供大家參考眉尸！
PS:本篇文章在博客園也有同步更新域蜗，大家也可以通過博客園關注我
http://www.cnblogs.com/wsnb
