先說說為什么寫這個吧,這個完全是由去阿里巴巴面試引起的一次慘目忍睹的血案。去面試的時候，由于面試前天晚上11點鐘才到阿里巴巴指定面試城市，找到旅館住下基本都1點多，加上晚上完全沒有睡好，直接導致第二天面試效果很不好(對于那些正在找工作的大蝦們不要向小蝦一下悲劇，提前做好準備還是很重要滴)，面試大概進行了一個多小時(面試結束回去的時候基本走路都快睡著了，悲催！！)，面試快結束的時候面試官問的我問題就是關于費波那西數列，當時頭腦完全漿糊，只知道要設置三個變量或者用List先初始化，當寫到for循環的時候，腦袋簡直漿糊的不能再漿糊了，沒寫出來，最后只能在面試官的步步誘導下寫出了下面的第一種方式，很不應該呀；從現在來看阿里只是把粗枝大葉的把整個應用的框架搭建起來了，真是變革、挖金的黃金期(有能力的大蝦趕緊去)，畢竟阿里巴巴手中99%的數據都是重要數據而向百度這類的主推搜索的巨頭99%數據都是垃圾相比，對于數據分析來說，阿里更能通過對手中掌握的多種多樣的用戶詳細數據進行分析，更能精確定位用戶的品味及需求，為精確推送和精準廣告推送提供更好的服務。如果說騰訊未來的夢想是做用戶生活中的水電氣的話，那阿里可能實現的未來夢想就是用戶的衣食住行外加代收水電氣等等，O(∩_∩)O~還是轉入正題吧。
對于優秀的算法設計員來說，在程序功能主體實現的基礎上無非關心兩個東西，一個設計算法的時間復雜度，一個是空間復雜度(說白了就是執行一個程序所用的時間和占用的內存空間)；在根據不同的應用場景的基礎上，一般充滿智慧的算法設計師會在時間和空間兩個相對矛盾的資源中尋求到平衡點，如實時性要求高的系統一般會以空間資源換取時間或者對于常用到的對象一般會常駐內存以提高響應時間(緩存技術和現在比較流行NoSQL中大多是內存數據庫都是如此)，對于內存資源比較寶貴的嵌入式系統而言一般會以時間上的延遲來換取時間。
下面從費波那西數列三個實現上來說說，怎么才能真正設計出真正符合實際應用場景的優秀算法
首先說說費波那西數列：
從文字上說，費波那西數列由0和1開始，之后的費波那西系數就由之前的兩數相加，數列形式如下：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946，………………
在數學上，是以遞歸的方法來定義：
F_0=0
F_1=1
F_n = F_{n-1}+ F_{n-2}
實現需求：輸入序號n返回得到對應費波那西數
程序實現1——函數自迭代
/**
* 函數自迭代
* @Title: fnType1
* @Description: TODO
* @param @param n
* @param @return
* @return int
* @throws Exception
*/
public int fnType1(int n)throws Exception{
if(n==0){
return 0;
}else if(n==1||n==2){
return 1;
}else if(n>2){
int temp=fnType1(n-1)+fnType1(n-2);
if(temp<0){
throw new Exception("Invalid value for int type, too larage");
}else{
return temp;
}
}else{
throw new Exception("IllegalArgument value for n,please enter n>=0 ");
}
}
此種方式缺點：大量迭代不斷消耗棧空間(搞web開發調試維護的都應該知道服務器棧資源的可貴，如果大量并發調用迭代導致服務器棧資源遲遲得不到回收，而導致web服務器崩潰)，效率底，函數自閉性比較弱(優秀的接口應該對輸入輸出可能出現的錯誤信息進行捕捉，并提供清楚明了的處理結果)，很容易出現錯誤，調試困難，實際應用中一般不建議使用這種方式，使用時迭代次數也不能超過3次；
程序實現2——時間換空間
/**
* 時間換空間
* @Title: fnType2
* @Description: TODO
* @param @param n
* @param @return
* @return int (n<0 return -1,beyond max int size return -2)
* @throws
*/
public int fnType2(int n){
int result=-1;
int temp1=0;
int temp2=1;
for(int index=0;index<=n;index++){
if(index==0){
result=temp1;
}else if(index==1){
result=temp2;
}else{
result=temp1+temp2;
if(result<0){
result=-2;
break;
}
temp1=temp2;
temp2=result;
}
}
return result;
}
此方法主要使用于:使用場景一：對于對象或變量使用次數比較少，使用一次以后就不會再使用的場景；使用場景二：對于內存資源比較稀缺的實時性要求不是太高的嵌入式系統設計中多會采用此種方式；
程序實現3——空間換取時間
private static List<Integer> fnData=new ArrayList<Integer>();
private static final int maxSize=50000;
/**
* 初始化器
* @Title: setFnData
* @Description: TODO
* @param
* @return void
* @throws
*/
private static void setFnData(){
int result=-1;
int temp1=0;
int temp2=1;
for(int index=0;index<=maxSize;index++){
if(index==0){
result=temp1;
}else if(index==1){
result=temp2;
}else{
result=temp1+temp2;
if(result<0){
result=-2;
break;
}
temp1=temp2;
temp2=result;
}
fnData.add(result);
}
}
/**
* 對外接口
* @Title: getFnData
* @Description: TODO
* @param @param n
* @param @return
* @return int <span style="font-family: sans-serif;">(n beyond fnData.size() and n<0 return -1)</span>
* @throws
*/
public int getFnData(int n){
if(fnData.size()==0){
setFnData();
}
if(fnData.size()>n&&n>=0){
return fnData.get(n);
}else{
return -1;
}
}
此方法一般用于：對象或變量在程序運行的整個生命周期都存在或頻繁調用的場景，如調用外部WebService接口、抽象持續化層、常用配置文件參數加載等等
測試用例：
package com.dbc.yangg.swing.test;
import java.util.ArrayList;
import java.util.List;
/**
* 輸入序號n返回得到對應費波那西數
* @ClassName: Init
* @Description: TODO
* @author [email protected]
* @date 2014年1月10日 下午7:52:13
*
*/
public class Init {
/**
* 函數自迭代
* @Title: fnType1
* @Description: TODO
* @param @param n
* @param @return
* @return int
* @throws Exception
*/
public int fnType1(int n)throws Exception{
if(n==0){
return 0;
}else if(n==1||n==2){
return 1;
}else if(n>2){
int temp=fnType1(n-1)+fnType1(n-2);
if(temp<0){
throw new Exception("Invalid value for int type, too larage");
}else{
return temp;
}
}else{
throw new Exception("IllegalArgument value for n,please enter n>=0 ");
}
}
/**
* 時間換空間
* @Title: fnType2
* @Description: TODO
* @param @param n
* @param @return
* @return int (n<0 return -1,beyond max int size return -2)
* @throws
*/
public int fnType2(int n){
int result=-1;
int temp1=0;
int temp2=1;
for(int index=0;index<=n;index++){
if(index==0){
result=temp1;
}else if(index==1){
result=temp2;
}else{
result=temp1+temp2;
if(result<0){
result=-2;
break;
}
temp1=temp2;
temp2=result;
}
}
return result;
}
private static List<Integer> fnData=new ArrayList<Integer>();
private static final int maxSize=50000;
/**
* 空間換時間
* @Title: setFnData
* @Description: TODO
* @param
* @return void
* @throws
*/
private static void setFnData(){
int result=-1;
int temp1=0;
int temp2=1;
for(int index=0;index<=maxSize;index++){
if(index==0){
result=temp1;
}else if(index==1){
result=temp2;
}else{
result=temp1+temp2;
if(result<0){
result=-2;
break;
}
temp1=temp2;
temp2=result;
}
fnData.add(result);
}
}
/**
*
* @Title: getFnData
* @Description: TODO
* @param @param n
* @param @return
* @return int (n beyond fnData.size() and n<0 return -1)
* @throws
*/
public int getFnData(int n){
if(fnData.size()==0){
setFnData();
}
if(fnData.size()>n&&n>=0){
return fnData.get(n);
}else{
return -1;
}
}
/**
*
* @Title: main
* @Description: TODO
* @param @param argv
* @return void
* @throws
*/
public static void main(String[] argv){
Init init=new Init();
int n=46;
try {
System.out.println("Type1="+init.fnType1(n));
} catch (Exception e) {
// TODO Auto-generated catch block
System.out.println(e.getMessage());
}
System.out.println("Type2="+init.fnType2(n));
System.out.println("Type3="+init.getFnData(n));
}
}
輸出結果：
Type1=1836311903
Type2=1836311903
Type3=1836311903
對于算法設計，不要盲目遵循概念，概念是死的，人是活的（在這個需要crazy man的時代，有想法比循規蹈矩更有優勢），只用結合具體的應用場景才能設計出優秀的算法和結構。
吐槽一下：個人認為優秀的數據結構設計可以簡化算法設計的復雜度提高代碼的可讀性、程序的擴展性及執行效率；
再吐槽一下：做需求分析的時候應該遵循三點原則：1.從用戶角度及其思維方式分析；2.用戶說的不一定是他們真正想要的；3.用戶說的不一定是對的。做程序開發遵循原則：積極提升自身品味，站在用戶使用角度和使用場景分析功能；例如你做后臺接口開發，你的用戶就是接口調用者，你應該考慮接口功能是什么，使用者在什么情況下會調用，傳入參數可能導致哪些異常，你的接口實現中可能出現哪些異常并對可能出現的異常進行捕獲，清楚明了的輸出，良好的函數自閉性；如果你是搞前臺，那你應該在保證業務實現的基礎上從用戶使用習慣等方面把自己當做使用者來設計UI。很有意思對不，需求、開發多了自然就明白了O(∩_∩)O~。
