算法很重要，但是一般情況下做移動(dòng)開(kāi)發(fā)并不經(jīng)常用到，所以很多同學(xué)早就將算法打了個(gè)大禮包送還給了老師了，況且很多同學(xué)并沒(méi)有學(xué)習(xí)過(guò)算法。這個(gè)系列就讓對(duì)算法頭疼的同學(xué)能快速的掌握基本的算法。過(guò)年放假階段玩了會(huì)游戲NBA2K17的生涯模式，沒(méi)有比賽的日子也都是訓(xùn)練，而且這些訓(xùn)練都是自發(fā)的，沒(méi)有人逼你，從早上練到晚上，屬性也不漲，但是如果日積月累，不訓(xùn)練和訓(xùn)練的人的屬性值就會(huì)產(chǎn)生較大差距。這個(gè)突然讓我意識(shí)到了現(xiàn)實(shí)世界，要想成為一個(gè)球星（技術(shù)大牛）那就需要日積月累的刻意訓(xùn)練，索性放下游戲，接著寫(xiě)文章吧。
雖然計(jì)算機(jī)能快速的完成運(yùn)算處理，但實(shí)際上，它也需要根據(jù)輸入數(shù)據(jù)的大小和算法效率來(lái)消耗一定的處理器資源。要想編寫(xiě)出能高效運(yùn)行的程序，我們就需要考慮到算法的效率。 算法的效率主要由以下兩個(gè)復(fù)雜度來(lái)評(píng)估： 時(shí)間復(fù)雜度：評(píng)估執(zhí)行程序所需的時(shí)間。可以估算出程序?qū)μ幚砥鞯氖褂贸潭取?空間復(fù)雜度：評(píng)估執(zhí)行程序所需的存儲(chǔ)空間。可以估算出程序?qū)τ?jì)算機(jī)內(nèi)存的使用程度。
設(shè)計(jì)算法時(shí)，一般是要先考慮系統(tǒng)環(huán)境，然后權(quán)衡時(shí)間復(fù)雜度和空間復(fù)雜度，選取一個(gè)平衡點(diǎn)。不過(guò)，時(shí)間復(fù)雜度要比空間復(fù)雜度更容易產(chǎn)生問(wèn)題，因此算法研究的主要也是時(shí)間復(fù)雜度，不特別說(shuō)明的情況下，復(fù)雜度就是指時(shí)間復(fù)雜度。
時(shí)間頻度 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度。記為T(mén)(n)。
時(shí)間復(fù)雜度 前面提到的時(shí)間頻度T(n)中，n稱為問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律，為此我們引入時(shí)間復(fù)雜度的概念。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T(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))，它稱為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。
像前面用O( )來(lái)體現(xiàn)算法時(shí)間復(fù)雜度的記法，我們稱之為大O表示法。 算法復(fù)雜度可以從最理想情況、平均情況和最壞情況三個(gè)角度來(lái)評(píng)估，由于平均情況大多和最壞情況持平，而且評(píng)估最壞情況也可以避免后顧之憂，因此一般情況下，我們?cè)O(shè)計(jì)算法時(shí)都要直接估算最壞情況的復(fù)雜度。 大O表示法O(f(n)中的f(n)的值可以為1、n、logn、n2等，因此我們可以將O(1)、O(n)、O(logn)、O(n2)分別可以稱為常數(shù)階、線性階、對(duì)數(shù)階和平方階，那么如何推導(dǎo)出f(n)的值呢？我們接著來(lái)看推導(dǎo)大O階的方法。
推導(dǎo)大O階 推導(dǎo)大O階，我們可以按照如下的規(guī)則來(lái)進(jìn)行推導(dǎo)，得到的結(jié)果就是大O表示法： 1.用常數(shù)1來(lái)取代運(yùn)行時(shí)間中所有加法常數(shù)。 2.修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng) 3.如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)。
常數(shù)階 先舉了例子，如下所示。
int sum = 0,n = 100; //執(zhí)行一次 sum = (1+n)*n/2; //執(zhí)行一次 System.out.PRintln (sum); //執(zhí)行一次上面算法的運(yùn)行的次數(shù)的函數(shù)為f(n)=3，根據(jù)推導(dǎo)大O階的規(guī)則1，我們需要將常數(shù)3改為1，則這個(gè)算法的時(shí)間復(fù)雜度為O(1)。如果sum = （1+n）*n/2這條語(yǔ)句再執(zhí)行10遍，因?yàn)檫@與問(wèn)題大小n的值并沒(méi)有關(guān)系，所以這個(gè)算法的時(shí)間復(fù)雜度仍舊是O(1)，我們可以稱之為常數(shù)階。
線性階 線性階主要要分析循環(huán)結(jié)構(gòu)的運(yùn)行情況，如下所示。
for(int i=0;i<n;i++){//時(shí)間復(fù)雜度為O(1)的算法...}上面算法循環(huán)體中的代碼執(zhí)行了n次，因此時(shí)間復(fù)雜度為O(n)。
對(duì)數(shù)階 接著看如下代碼：
int number=1;while(number<n){number=number*2;//時(shí)間復(fù)雜度為O(1)的算法...}可以看出上面的代碼，隨著number每次乘以2后，都會(huì)越來(lái)越接近n，當(dāng)number不小于n時(shí)就會(huì)退出循環(huán)。假設(shè)循環(huán)的次數(shù)為X，則由2^x=n得出x=log?n，因此得出這個(gè)算法的時(shí)間復(fù)雜度為O(logn)。
平方階 下面的代碼是循環(huán)嵌套：
for(int i=0;i<n;i++){ for(int j=0;j<n;i++){ //復(fù)雜度為O(1)的算法 ... } }內(nèi)層循環(huán)的時(shí)間復(fù)雜度在講到線性階時(shí)就已經(jīng)得知是O(n)，現(xiàn)在經(jīng)過(guò)外層循環(huán)n次，那么這段算法的時(shí)間復(fù)雜度則為O(n2)。 接下來(lái)我們來(lái)算一下下面算法的時(shí)間復(fù)雜度：
for(int i=0;i<n;i++){ for(int j=i;j<n;i++){ //復(fù)雜度為O(1)的算法 ... } }需要注意的是內(nèi)循環(huán)中int j=i，而不是int j=0。當(dāng)i=0時(shí)，內(nèi)循環(huán)執(zhí)行了n次；i=1時(shí)內(nèi)循環(huán)執(zhí)行了n-1次，當(dāng)i=n-1時(shí)執(zhí)行了1次，我們可以推算出總的執(zhí)行次數(shù)為：
n+(n-1)+(n-2)+(n-3)+……+1 =(n+1)+[(n-1)+2]+[(n-2)+3]+[(n-3)+4]+…… =(n+1)+(n+1)+(n+1)+(n+1)+…… =(n+1)n/2 =n(n+1)/2 =n2/2+n/2
根據(jù)此前講過(guò)的推導(dǎo)大O階的規(guī)則的第二條：只保留最高階，因此保留n2/2。根據(jù)第三條去掉和這個(gè)項(xiàng)的常數(shù)，則去掉1/2,最終這段代碼的時(shí)間復(fù)雜度為O(n2)。
其他常見(jiàn)復(fù)雜度
除了常數(shù)階、線性階、平方階、對(duì)數(shù)階，還有如下時(shí)間復(fù)雜度： f(n)=nlogn時(shí)，時(shí)間復(fù)雜度為O(nlogn)，可以稱為nlogn階。 f(n)=n3時(shí)，時(shí)間復(fù)雜度為O(n3)，可以稱為立方階。 f(n)=2?時(shí)，時(shí)間復(fù)雜度為O(2?)，可以稱為指數(shù)階。 f(n)=n!時(shí)，時(shí)間復(fù)雜度為O(n!)，可以稱為階乘階。 f(n)=(√n時(shí)，時(shí)間復(fù)雜度為O(√n)，可以稱為平方根階。
下面將算法中常見(jiàn)的f(n)值根據(jù)幾種典型的數(shù)量級(jí)來(lái)列成一張表，根據(jù)這種表，我們來(lái)看看各種算法復(fù)雜度的差異。
| n | logn | √n | nlogn | n2 | 2? | n! |
|---|---|---|---|---|---|---|
| 5 | 2 | 2 | 10 | 25 | 32 | 120 |
| 10 | 3 | 3 | 30 | 100 | 1024 | 3628800 |
| 50 | 5 | 7 | 250 | 2500 | 約10^15 | 約3.0*10^64 |
| 100 | 6 | 10 | 600 | 10000 | 約10^30 | 約9.3*10^157 |
| 1000 | 9 | 31 | 9000 | 1000 000 | 約10^300 | 約4.0*10^2567 |
從上表可以看出，O(n)、O(logn)、O(√n )、O(nlogn )隨著n的增加，復(fù)雜度提升不大，因此這些復(fù)雜度屬于效率高的算法，反觀O(2?)和O(n!)當(dāng)n增加到50時(shí)，復(fù)雜度就突破十位數(shù)了，這種效率極差的復(fù)雜度最好不要出現(xiàn)在程序中，因此在動(dòng)手編程時(shí)要評(píng)估所寫(xiě)算法的最壞情況的復(fù)雜度。
下面給出一個(gè)更加直觀的圖： 
其中x軸代表n值，y軸代表T(n)值（時(shí)間復(fù)雜度）。T(n)值隨著n的值的變化而變化，其中可以看出O(n!)和O(2?)隨著n值的增大，它們的T(n)值上升幅度非常大，而O(logn)、O(n)、O(nlogn)隨著n值的增大，T(n)值上升幅度則很小。 常用的時(shí)間復(fù)雜度按照耗費(fèi)的時(shí)間從小到大依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2?)<O(n!)參考資料 《大話數(shù)據(jù)結(jié)構(gòu)》 《挑戰(zhàn)程序設(shè)計(jì)競(jìng)賽2》 《算法》
歡迎關(guān)注我的微信公眾號(hào)，第一時(shí)間獲得博客更新提醒，以及更多成體系的Android相關(guān)技術(shù)干貨。 掃一掃下方二維碼即可關(guān)注：
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
