java 算法基礎

1、算法概要     

     算法是用于計算、資料處理和自動推理使用的。算法主要是做精确計算和表示一個有限長列的有效方法。算法一般包含清晰定義的指令用于計算函數。基本上也屬于一種思考最簡潔的方式。

2、算法特征

     算法主要包含五個特征

     2.1、有窮性；

           是指算法必須能在執行有限個步驟後終止；

     2.2、确切性；

           算法的每一個步驟必須有确切的定義；

     2.3、輸入項；

           一個算法輸入有0或多個輸入，以刻畫預算對象的初始情況，所謂0就是初始化條件；

     2.4、輸出項；

           回報對資料加工後的結果。沒有輸出的算法無意義。

     2.5、可行性；

           算法中執行的任何計算都可以分步驟進行，每個步驟并在有限時間内完成。

3、算法常用的設計模式

      主要有十個設計模式

      3.1、完全周遊法     

            在驗證一個問題集合時，且以驗證正确性和最優性的時候，就會采用完全周遊法。但在便利的過程中就會消耗大量的記憶體。

      3.2、不完全周遊法

             當便利時占用的記憶體空間特别龐大時，可以使用不完全周遊法來實作。例如各種規則算法和搜尋算法即是。

      3.3、分治法

            把一個問題分區成互相獨立的部分，分别求解。分治法的好處在于可以并行計算。

               分治法所能解決的問題一般具有以下幾個特征：

               (1) 該問題的規模縮小到一定的程度就可以容易地解決；

               (2) 該問題可以分解為若幹個規模較小的相同問題，即該問題具有最優子結構性質；

               (3) 利用該問題分解出的子問題的解可以合并為該問題的解；

               (4) 該問題所分解出的各個子問題是互相獨立的，即子問題之間不包含公共的子子問題。

      3.4、動态規劃法

            當問題整體的最優解是由局部最優解組成的時候，會經常采用這種規劃方法。用于求解包含重疊子問題的最優化問題的方法。

      3.5、貪婪算法（也叫貪心算法）

            常見的近似求解思路。當問題的整體最優解不是（或無法證明是）由局部最優解組成，且對解的最優性沒有要求的時候，可以采用的一種方法。

      3.6、線性規則法

            問題是目标函數和限制條件都是線性的最優化

      3.7、簡并法

            把一個問題通過邏輯或數學推理，簡化成與之等價或者近似的、相對簡單的模型，進而求解的方法。

      3.8、窮舉法

            窮舉法，或稱為暴力破解法，其基本思路是：對于要解決的問題，列舉出它的所有可能的情況，逐個判斷有哪些是符合問題所要求的條件，進而得到問題的解。它也常用于對于密碼的破譯。

      3.9、分枝界限法

             分枝界限法是一個用途十分廣泛的算法，運用這種算法的技巧性很強，不同類型的問題解法也各不相同。分支定界法的基本思想是對有限制條件的最優化問題的所有可行解（數目有限）空間進行搜尋

      3.10、回溯法

             運用這種算法的技巧性很強，不同類型的問題解法也各不相同。分支定界法的基本思想是對有限制條件的最優化問題的所有可行解（數目有限）空間進行搜尋。

6、複雜度

      6.1、時間複雜度

      時間複雜度是指着算法需要消耗的時間資源。一般來說，計算機算法說問題模型n的函數f(n),算法的時間複雜度因是以被記做

            t(n)=o(f(n))   

           算法執行時間的增長率與f(n) 的增長率正相關，稱作漸近時間複雜度（asymptotic time complexity），簡稱時間複雜度。

           常見的時間複雜度有：常數階o(1),對數階o(log2n),線性階o(n), 線性對數階o(nlog2n),平方階o(n2)，立方階o(n3),...， k次方階o(nk),指數階o(2n)。随着問題規模n的不斷增大，上述時間複雜度不斷增大，算法的執行效率越低。

      6.2、空間複雜度

            算法的空間複雜度是指算法需要消耗的空間資源。其計算和表示方法與時間複雜度類似，一般都用複雜度的漸近性來表示。同時間複雜度相比，空間複雜度的分析要簡單得多。

      6.3、非确定性多項式時間複雜度（np）

            非定常多項式（英語：non-deterministic polynomial，縮寫np）時間複雜性類，或稱非确定性多項式時間複雜性類，包含了可以在多項式時間内，對一個判定性算法問題的執行個體，一個給定的解是否正确的算法問題。

      6.4、複雜度特性

            所有算法都需要符合這三種特性正确性、可讀性以及健壯性。    

7、算法分類

     算法可大緻分為基本算法、資料結構的算法、數論與代數算法、計算幾何的算法、圖論的算法、動态規劃以及數值分析、加密算法、排序算法、檢索算法、随機化算法、并行算法，厄米變形模型，随機森林算法。

     算法可以宏泛的分為三類：

     一，有限的，确定性算法 這類算法在有限的一段時間内終止。他們可能要花很長時間來執行指定的任務，但仍将在一定的時間内終止。這類算法得出的結果常取決于輸入值。

     二，有限的，非确定算法 這類算法在有限的時間内終止。然而，對于一個（或一些）給定的數值，算法的結果并不是唯一的或确定的。

     三，無限的算法 是那些由于沒有定義終止定義條件，或定義的條件無法由輸入的資料滿足而不終止運作的算法。通常，無限算法的産生是由于未能确定的定義終止條件。

8、幾個算法基礎小實踐

     8.1、求最大值算法

 8.2、求最大公約數

 8.3、兔子問題

 8.4、猴子吃桃子

8.5、乒乓球比賽

8.6、數列求和

    8.7、2的問題

 8.8、自由落體球

 8.9、累乘

 8.10、遞歸求5！

9、資料分享

     1、算法筆記（可以看看裡面有很多比較有意思的算法） http://www.csie.ntnu.edu.tw/~u91029/

     2、20世紀十大算法http://www.uta.edu/faculty/rcli/topten/topten.pdf

     3、維基算法百科：http://zh.wikipedia.org/wiki/%e7%ae%97%e6%b3%95

     4、百度算法百科：http://baike.baidu.com/link?url=5ssycikkqgncq7qdef3jkmkxbyfbzoljmjqfqup51nnhz3zbj_xtrdmifnkwlrex

     5、麻省理工大學算法公開課：http://v.163.com/special/opencourse/algorithms.html

     6、算法部落格：http://www.iteye.com/blogs/tag/%e7%ae%97%e6%b3%95

     7、十三個經典算法研究與總結     http://blog.csdn.net/v_july_v/article/details/6305212