·1.1.1_總是可行的枚舉。?
假設(shè)有一組數(shù)：{1,8,9,7,5,6,1,10,6}，需要得到其中最大的數(shù)的值，對(duì)于人來說，顯然，最大的數(shù)的值為10。但對(duì)于計(jì)算機(jī)來說，它并不能“一眼看”出這組數(shù)的最大值。
有一個(gè)比較好的且易于理解的方法便是先記錄前m個(gè)數(shù)的最大值max_number，然后再插入第m+1個(gè)數(shù)，對(duì)比max_number與第m+1個(gè)數(shù)的值之間的大小，如果max_number是較小數(shù)，則將第m+1個(gè)數(shù)的值賦于max_number，max_number遍成為前m+1個(gè)數(shù)的最大值。
? 這個(gè)方法是可行且容易證明其可行性的。（下面的證明過程可以不看。）
證明，設(shè) N[i]為一組數(shù)中的第i個(gè)數(shù)。
因?qū)τ谝粋€(gè)數(shù)N[1]來說，最大值與最小值就是這個(gè)數(shù)本身，則max_number的值等于N。
此時(shí)，前1個(gè)數(shù)的最大值max_number與N[2]對(duì)比，無論對(duì)比的結(jié)果如何，max_number都為前2個(gè)數(shù)的最大值。
由此類推，當(dāng) i 等于 N 時(shí)，max_number則為前N個(gè)數(shù)的最大值。由此，此算法成立并且由于進(jìn)行了N-1次判斷，時(shí)間復(fù)雜度為O（N-1）
而上述方法，便是稱為枚舉法。其基本思想為，一個(gè)不漏地查看所有可能的情況。
? 是不是和一種修辭手法舉例子很像呢？枚舉法可以看成 舉出所有例子的一種手法嘛。
·1.1.2_枚舉的局限性。
? ?枚舉在大多數(shù)情況下都可行，但畢竟沒有萬能的方法，更何況是一個(gè)如此直觀又易于理解的方法呢。此節(jié)的名稱是暴力的枚舉，有一句話云，暴力出奇跡，這句話顯示了暴力是一個(gè)可以創(chuàng)造奇跡的方法，但是暴力在大多數(shù)情況下都是不可取的阿！
? ?枚舉的局限性：枚舉是一種很笨的方法，他僅適用于一些規(guī)模很小的問題。
·1.1.3_枚舉的優(yōu)點(diǎn)。
? ? 在實(shí)際做題中，特別是比賽當(dāng)中，我們沒有更多事件去思考是不是有更優(yōu)的解決方法，所以，我們很多時(shí)候是會(huì)選擇一個(gè)看似可行的方法。這時(shí)候，作為最容易讓人想起的方法——枚舉法，便大有可為了。
? ?看到這里，如果讀者您或者想到，枚舉法的優(yōu)點(diǎn)就只有簡單嗎？那您真的是too young too simple了。（此處拒絕續(xù)命。
其實(shí)枚舉法還是一個(gè)可控性比較強(qiáng)的方法。對(duì)于可控性，我是這樣想的，這個(gè)方法是實(shí)際應(yīng)用中相對(duì)難以出錯(cuò)的算法，無論是邏輯上的錯(cuò)誤還是個(gè)人低級(jí)錯(cuò)誤（例如寫錯(cuò)變量之類的）。他只需要相對(duì)短小精悍的代碼來實(shí)現(xiàn)，而且優(yōu)化起來靈活。
·1.1.4_更好地枚舉。
上一點(diǎn)提到了枚舉的優(yōu)化起來比較靈活，此處簡單介紹幾種枚舉的常見優(yōu)化方法和應(yīng)用例子。
? ? ? ①減少不可能情況。有一些情況是顯而易見不可能的，所以可以除去。
? ? ??②選擇更好的數(shù)據(jù)結(jié)構(gòu)進(jìn)行儲(chǔ)存。用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)解決適當(dāng)?shù)膯栴}便是數(shù)據(jù)結(jié)構(gòu)的意義所在。
? ? ??③適當(dāng)?shù)赜每臻g換取時(shí)間。在算法比賽中（OJ刷題中），給出的空間往往是很充裕的，某些情況下，用空間換取時(shí)間是很好的選擇。
? ? ??④N元方程的優(yōu)化。在某些N元方程中，我們往往只需要計(jì)算N-1元。
一個(gè)例子。給定長度為n的數(shù)組S，判斷數(shù)組中的元素知否存在a,b,c,使得a+b+c=0。找出所有滿足條件的元素并輸出。
對(duì)于此問題，我們枚舉所有所有可能方案，由所有可能方案則為S中任意三個(gè)元素的組合，則為 n*(n-1)*(n-2)/(2*3) 個(gè)可能方案。但這是可以優(yōu)化的，用方法④。
? 假設(shè)，A[x]為a取S中第x個(gè)數(shù)，B[y]為b取S中第y個(gè)數(shù)，C[z]為c取S中第z個(gè)數(shù)。(x != y != z)
我們就可以得到，此問題轉(zhuǎn)化為求 A[x]+B[y]+C[z] = 0時(shí)，x,y,z的值。
? ?再轉(zhuǎn)化一下，則變?yōu)?A[x] + B[y] = -C[z]，則我們只需要枚舉 A[x] + B[y]的值是否有存在一個(gè)其的相反數(shù)c在數(shù)組S中且不為第x或第y個(gè)數(shù)即可。
等等，假如你是機(jī)智可愛的小讀者，你就會(huì)聰明的發(fā)現(xiàn)，這有優(yōu)化么，喵喵喵喵喵喵喵？還需要判斷一次c是否存在哇！這復(fù)雜度沒變過阿。
(=u=)，機(jī)智可愛的讀者們說得沒錯(cuò)，但畢竟，我們還有其他方法不是么。
由于現(xiàn)在我們需要解決的問題是判斷數(shù)組S中剩余的數(shù)是否存在第c，所以，這就可以用方法②和方法③來解決了！這里我選擇開一個(gè)散列表來解決。只要我們往散列表中，將S的所有數(shù)作為key來put進(jìn)HashMap中，那么我們就可以僅付出O(1)的代價(jià)來查詢 數(shù)c是否存在于數(shù)組S中了不是么？
所以，時(shí)間復(fù)雜度便從 O(n*(n-1)*(n-2)/6) 優(yōu)化成了 O(n*(n-1)/2)，這可是 O(n的3次方) 級(jí)別到 O(n的2次方) 級(jí)別的飛躍阿！
此栗子舉例了方法②③④在枚舉中的應(yīng)用，關(guān)于①方法，讀者可以自己去嘗試一下，亦可在后續(xù)文章中聽本蒻進(jìn)行講解。
這里是葉攻攻。
