程序優(yōu)化降低復(fù)雜度

1、32程序優(yōu)化-降-低復(fù)雜度時(shí)間昂貴、空間廉價(jià)一段代碼會(huì)消耗計(jì)算時(shí)間、資源空間，從而產(chǎn)生時(shí)間復(fù)雜度和空間復(fù)雜度。假設(shè)一段代碼經(jīng)過優(yōu)化后，雖然降低了時(shí)間復(fù)雜度，但依然需要消耗非常高的空間復(fù)雜度。0例如，對于固定數(shù)據(jù)量的輸入，這段代碼需要消耗幾十G的內(nèi)存空間，很顯然普通計(jì)算機(jī)根本無法完成這樣的計(jì)算。如果一定要解決的話，一個(gè)最簡單粗暴的辦法就是，購買大量的高性能計(jì)算機(jī)，來彌補(bǔ)空間性能的不足。反過來，假設(shè)一段代碼經(jīng)過優(yōu)化后，依然需要消耗非常高的時(shí)間復(fù)雜度。例如，對于固定數(shù)據(jù)量的輸入，這段代碼需要消耗10年的時(shí)間去完成計(jì)算。如果在跑程序的010年時(shí)間內(nèi)，出現(xiàn)了斷電、斷網(wǎng)或者程序拋出異常等預(yù)期范圍之外的問題

2、，那很可能造成10年時(shí)間浪費(fèi)的慘重后果。很顯然，用皿年的時(shí)間去跑一段代碼，對開發(fā)者和運(yùn)維者而言都是極不友好的。這告訴我們一個(gè)什么樣的現(xiàn)實(shí)問題呢？代碼效率的瓶頸可能發(fā)生在時(shí)間或者空間兩個(gè)方面。如果是缺少計(jì)算空間，花錢買服務(wù)器就可以了。這是個(gè)花錢就能解決的問題。相反，如果是缺少計(jì)算時(shí)間，只能投入寶貴的人生去跑程序。即使你有再多的錢、再多的服務(wù)器，也是毫無用處。相比于空間復(fù)雜度，時(shí)間復(fù)雜度的降低就顯得更加重要了。因此，你會(huì)發(fā)現(xiàn)這樣的結(jié)論：空間是廉價(jià)的，而時(shí)間是昂貴的。程序優(yōu)化的最核心的思路第一步，暴力解法。在沒有任何時(shí)間、空間約束下，完成代碼任務(wù)的開發(fā)。第二步，無效操作處理。將代碼中的無效計(jì)算、無效

3、存儲(chǔ)剔除，降低時(shí)間或空間復(fù)雜度案例一體現(xiàn)）。第三步，時(shí)空轉(zhuǎn)換。設(shè)計(jì)合理數(shù)據(jù)結(jié)構(gòu)，完成時(shí)間復(fù)雜度向空間復(fù)雜度的轉(zhuǎn)移案例二體現(xiàn)）。說明：常用的降低時(shí)間復(fù)雜度的方法有遞歸、二分法、排序算法、動(dòng)態(tài)規(guī)劃等，而降低空間復(fù)雜度的方法就是數(shù)據(jù)結(jié)構(gòu)，核心思路就是，能用低復(fù)雜度的數(shù)據(jù)結(jié)構(gòu)能解決問題，就千萬不要用高復(fù)雜度的數(shù)據(jù)結(jié)構(gòu)。1/*0200*oauthor0佛大Java程序員*since1.0.0*/publicclassAlgorithmTest4publicstaticvoidmain(Stringargs)AlgorithmTest4algorithmTest4=newAlgorithmTest4();

4、algorithmTest4.s2_1();TOC o 1-5 h zSystem.out.println();algorithmTest4.s2_2();12/*000000*方法一0:時(shí)間復(fù)雜度為o(0n皿*/publicvoids2_1()intcount=0;for(inti=0;i(100/7);i+)for(intj=0;j(100/3);j+)for(intk=0;k=(100/2);k+)if(i*7+j*3+k*2=100)count+=1;/System.out.println(i:+i+j:+j+k:+k);TOC o 1-5 h zSystem.out.println(

5、方法一總共：+count+組合);3031/*32333435363738394041424344454647運(yùn)行結(jié)果案例二查找出一個(gè)數(shù)組中，出現(xiàn)次數(shù)最多的那個(gè)元素的數(shù)值。*方法二：時(shí)間復(fù)雜度為0(n*/publicvoids2_2()intcount=0;for(inti=0;i(100/7);i+)for(intj=0;j=0)count+=1;/System.out.println(i:+i+j:+j);System.out.println(方法二總共：+count+組合);方法一：使用3層的for循環(huán)。從結(jié)構(gòu)上來看，是很顯然的0（山）的時(shí)間復(fù)雜度。然而，仔細(xì)觀察就會(huì)發(fā)現(xiàn)，代碼中最內(nèi)層的

6、for循環(huán)是多余的。因?yàn)椋?dāng)你確定了要用i張7元和j張3元時(shí)，只需要判斷用有限個(gè)2元能否湊出100-7*i-3*j元就可以了。方法二：代碼的結(jié)構(gòu)由3層for循環(huán)，變成了2層for循環(huán)。很顯然，時(shí)間復(fù)雜度就變成了0（2）。這樣的代碼改造，就是利用了方法論中的步驟二,將代碼中的無效計(jì)算、無效存儲(chǔ)剔除，降低時(shí)間或空間復(fù)雜度。3232System.out.println（方法一，次數(shù)最多的那個(gè)元素的數(shù)值:+maxVal）;例如，輸入數(shù)組a=1,2,3,4,5,5,6中，查找出現(xiàn)次數(shù)最多的數(shù)值。從數(shù)組中可以看出，只有5出現(xiàn)了2次，其余都是1次。顯然5出現(xiàn)的次數(shù)最多，則輸出5。1/*author佛大Jav

7、a程序員*since1.0.0*/publicclassAlgorithmTest567891011121314151617181920212223242526272829303132publicstaticvoidmain(Stringargs)AlgorithmTest5algorithmTest5=newAlgorithmTest5();algorithmTest5.s2_3();algorithmTest5.s2_4();/*方法一：時(shí)間復(fù)雜度就是0(n*/publicvoids2_3()inta=1，2，3，4，5，5，6;/初始化最大值，最大次數(shù)，臨時(shí)記錄次數(shù)intmaxVal=0

8、，maxTime=0，tmpTime;for(inti=0;ia.length;i+)tmpTime=0;for(intj=0;jmaxTime)maxTime=tmpTime;maxVal=ai;3233/*rnrnn方法二：時(shí)間復(fù)雜度為ao(n)*/publicvoids2_4()inta=1,2,3,4,5,5,6;Mapd=newHashMap();for(inti=0;imaxTime)maxTime=d.get(key);maxVal=key;TOC o 1-5 h zSystem.out.println(方法二,次數(shù)最多的那個(gè)元素的數(shù)值:+maxVal);方法一：采用兩層的fOB

9、循環(huán)完成計(jì)算。第一層循環(huán)，對數(shù)組每個(gè)元素遍歷。第二層循環(huán)，則是對第一層遍歷的數(shù)字，去遍歷計(jì)算其出現(xiàn)的次數(shù)。這樣，全局再同時(shí)緩存一個(gè)出現(xiàn)次數(shù)最多的元素及其次數(shù)就可以了時(shí)間復(fù)雜度就是亞nm。而且代碼中，幾乎沒有冗余的無效計(jì)算。如果還需要再去優(yōu)化，就要考慮采用一些數(shù)據(jù)結(jié)構(gòu)方面的手段，來把時(shí)間復(fù)雜度轉(zhuǎn)移到空間復(fù)雜度乙方法二：定義一個(gè)Dk-va結(jié)構(gòu)的字典，用來存放元素出現(xiàn)次數(shù)的Dk-VD關(guān)系。那么首先通過一次循環(huán)，將數(shù)組轉(zhuǎn)變?yōu)樵爻霈F(xiàn)次數(shù)的一個(gè)字典。接下來，再去遍歷一遍這個(gè)字典，找到出現(xiàn)次數(shù)最多的那個(gè)元素，就能找到最后的結(jié)果了。代碼結(jié)構(gòu)上，有兩個(gè)fOB循環(huán)。不過，這兩個(gè)循環(huán)不是嵌套關(guān)系，而是順序執(zhí)行關(guān)系。其中，第一個(gè)循環(huán)實(shí)現(xiàn)了數(shù)組轉(zhuǎn)字典的過程，也就是0(n)D的復(fù)雜度。第二個(gè)循環(huán)再次遍歷字典找到出現(xiàn)次數(shù)最多的那個(gè)元素，也是一個(gè)ao(n)D的時(shí)間復(fù)雜度。因此，總體的時(shí)間復(fù)雜度為ao(n)D+ao(n)，就是ao(2