2016-08-08 23:00:37
排序算法的核心思想就是，讓你幫助你認清自己最需要的是什麼，認清自己最想要的是什麼，然後根據這個去做選擇。
貪婪算法所謂貪婪算法，是一種在每一步選擇中都采取在當前狀態下最好或最優（即最有利）的選擇（註意：是當前狀態下），從而希望導致結果是最好或最優的算法。貪婪算法最經典的一個例子就是哈夫曼編碼。
對於人類來說，一般人在行為處事的時候都會使用到貪婪算法，
比如在找零錢的時候，如果要找補36元，我們一般會按這樣的順序找錢：20元，10元，5元，1元。或者我們在過十字路口的時候，要從到對角線的那個街區時，我們也會使用貪婪算法——哪邊的綠燈先亮瞭我們就先過到那邊去，然後再轉身90度等紅燈再過街。這樣的例子有很多。對於選擇中，大多數人都會選用貪婪算法，因為這是一個比較簡單的算法，未來太復雜瞭，隻能走一步看一步，在當前的狀況下做出最利於自己的判斷和選擇即可。
有的人會貪婪薪水，有的人會貪婪做的項目，有的人會貪婪業務，有的人會貪婪職位，有的人會貪婪自己的興趣……這些都沒什麼問題。貪婪算法並沒有錯，雖然不是全局最優解，但其可以讓你找到局部最優解或是次優解。其實，有次優解也不錯瞭。貪婪算法基本上是一種急功近利的算法，但是並不代表這種算法不好，如果貪婪的是一種長遠和持續，又未嘗不可呢？。
動態規劃但是我們知道，對於大部分的問題，貪婪法通常都不能找出最優解，因為他們一般沒有測試所有可能的解。因為貪婪算法是一種短視的行為，隻會跟據當前的形式做判斷，也就是過早做決定，因而沒法達到最佳解。
動態規劃和貪婪算法的最大不同是，貪婪算法做出選擇，不能回退。動態規劃則會保存以前的運算結果，並根據以前的結果對當前進行選擇，有回退功能。
動態規劃算法至少告訴我們兩個事：
1）承前啟後非常重要，當你準備去做遍歷的時候，你的上次的經歷不但能開啟你以後的經歷，而且還能為後面的經歷所用。你的每一步都沒有浪費。
2）是否可以回退也很重要。這意思是——如果你面前有兩個選擇，一個是A公司一個是B公司，如果今天你錯失瞭B公司，那到你明天還能不能找回來？
比如說：你有兩個offer，一個是Yahoo，一個是Baidu，上述的第一點會讓我們思考，Yahoo和Baidu誰能給我們開啟更大的平臺？上述的第二點告訴我們，是進入Yahoo後如果沒有選好，是否還能回退到Baidu公司？還是進入Baidu公司後能容易回退到Yahoo公司？
Dijkstra最短路徑最短路徑是一個Greedy + DP的算法。相當經典。這個算法的大意如下：
1）在初始化的時候，所有的結點都和我是無窮大，默認是達不到的。
2）從離自己最近的結點開始貪婪。
3）走過去，看看又能到達什麼樣的結點，計算並更新到所有目標點的距離。
4）再貪婪與原點最短的結點，如此反復。
這個算法給我們帶來瞭一些這樣的啟示：
有朋友和我說過他想成為一個架構師，或是某技術領域的專傢，並會踏踏實實的向這個目標前進，永不放棄。我還是鼓勵瞭他，但我也告訴他瞭這個著名的算法，我說，這個算法告訴你，架構師或某領域的專傢對你來說目前的距離是無窮大，他們放在心中，先看看你能夠得著的東西。所謂踏實，並不是踏踏實實追求你的目標，而是踏踏實實把你夠得著看得見的就在身邊的東西幹好。我還記得我剛參加工作，從老傢出來的時候，從來沒有想過要成為一個技術牛人，也從來沒有想過我的博客會那麼的有影響力，在做自己力所能及，看得見摸得著的事情，我就看見什麼技術就學什麼，學著學著就知道怎麼學更輕松，怎麼學更紮實，這也許就是我的最短路徑。有很多朋友問我要不要學C++，或是問我學Python還是學Ruby，是不是不用學前端，等等。這些朋友告訴我，他們不可能學習多個語言，學瞭不用也就忘瞭，而且術業有專攻。這並沒有什麼不對的，隻是我個人覺得，學習一個東西沒有必要隻有兩種狀態，一種是不學，另一種是精通。瞭解一個技術其實花不瞭多少時間，我學C++的目的其實是為瞭更懂Java，學TCP/IP協議其實是為瞭更懂Socket編程，很多東西都是連通和相輔相成的，學好瞭C/C++/Unix/TCP等這些基礎技術後，我發現到達別的技術路徑一下縮短瞭（這就是為什麼我用兩天時間就可以瞭解Go語言的原因）。這就好像這個算法一樣，算法效率不高，也許達到你的目標，你在一開始花瞭很長時間，遍歷瞭很多地方，但是，這也許這就是你的最短路徑。算法就是Trade-Off