第C#算法設計與分析詳解目錄1.什么是科學方法？？1.觀察2.將問題規模和運行時間的關系量化2.數學模型近似近似運行時間成本模型總結3.增長數量級的分類4.倍率實驗5.注意事項6.處理對于輸入的依賴7.內存1.對象2.鏈表3.數組4.字符串對象作為程序員，開發完一段代碼，實現了某個功能時，有必要知道：

我的程序需要多長時間？

是什么導致我的程序消耗很多內存？

比如，統計或者處理了一大批數據。影響這些問題的因素很多，例如，電腦的性能，數據的性質（值類型和引用類型的區別），使用的算法。想要為這些基礎問題提供答案需要通過科學方法。

1.什么是科學方法？？

它是科學家為獲取自然界知識所使用的一系列大家認同的方法。

1.細致地觀察真實世界的特點，通常還要精確的測量2.根據觀察結果提出假設模型3.根據模型預測未來的事件4.繼續觀察并核實預測的準確性5.如此反復直到確認預測和觀察一致

這里我們不需要深究它，我們會使用數學分析（科學方法的一種）為算法成本建立模型，并使用實驗數據驗證這些模型。

科學方法的一條關鍵原則是可重現的，可證偽的。

1.觀察

怎么定量測量程序的運行時間？

各種工具，谷歌瀏覽器...，計時器Stopwatch

我們一般只需要近似值就可以了。

對大多數程序的第一個定量觀察就是計算性任務的困難程度可以用問題的規模來衡量。什么是問題的規模？可以是輸入的大小或是某個命令行參數的值（開發預估時間）。

另一個定量觀察是運行時長和輸入本身相對無關，它主要取決于問題模型。就是說，同樣大小的輸入量，程序運行時間是差不多的。如果換一批同樣大小的數據，運行時長差很多，就需要控制運行時間對輸入的敏感度（比如把實驗數據存起來）。

2.將問題規模和運行時間的關系量化

1.生成實驗數據2.數據分析

根據問題規模和運行時長的數據繪制圖表

猜想

舉例ThreeSum實驗

publicstaticintThreeSum(int[]a)

intN=a.Length;

intcnt=0;

for(vari=0;ii++)

for(varj=i+1;jj++)

for(vark=j+1;kk++)

if(a[i]+a[j]+a[k]==0)

cnt++;

returncnt;

}

lg(T(N))=3lgN+lga--a是常數

T(N)=aN^3

這里猜想的時候用到冥次法則：T(N)=aN^b

2.數學模型

雖然有很多復雜的因素影響著程序的運行時間，但一個程序的運行的總時間主要有關的兩點是：

1.執行每條語句的時長（取決于計算機，編譯器和操作系統）2.執行每條語句的頻率（取決于程序本身和輸入）

計算執行每條語句的時長可以通過各種工具測出。

重點是判斷執行每條語句的執行頻率，有的語句很好判斷，比如一些賦值語句；有些需要深入分析，比如ThreeSum實驗中if語句的執行次數為N(N-1)(N-2)/6次（主要是要了解立方推導公式）。而且有些語句的執行次數取決于輸入的數據，例如計算和為0的三元組的數量的語句（0~N^3/6）。

近似

頻率分析可能會產生復雜冗長的數學表達式，例如：

N(N-1)(N-2)/6=N^3/6-N^2/2+N/3

我們使用波浪號逼近法，在其中我們丟棄使公式復雜化的低階項。我們寫?f（N）表示當N增長時除以f（N）接近1的任何函數。我們寫g（N）?f（N）表示當N增長時g（N）/f（N）接近1。

所以N^3/6-N^2/2+N/3的近似函數是N^3/6，增長數量級是N^3。

近似運行時間

大部分情況下，執行最頻繁的語句決定了程序執行的總時間-內循環，ThreeSum實驗中的內循環就是第三層循環和if語句。大部分程序的運行時間都只取決于某一小部分。

性質（猜想）：ThreeSum的運行時間~aN^3（a是常數），增長數量級是N^3。

成本模型

定義了所研究的算法的基本操作。

可以用一個成本模型來評估算法的性質。在這個成本模型下，我們可以用數字說明算法而非某個性質。

例如，ThreeSum的成本模型是數組的訪問次數（無論讀寫）。

性質：該算法訪問了~N^3/6個整數三元組中的所有3個整數。

通過明確成本模型使給定程序所需的運行時間的增長數量級和程序算法真正成本的增長數量級相同。

總結

大多數程序，得到運行時間的數學模型所需的步驟：

1.確定輸入模型，定義問題的模型（該任務的困難程度）2.識別內循環3.根據內循環中的操作確定成本模型4.對于給定的輸入，判斷這些操作的執行頻率

3.增長數量級的分類

我們使用一些結構原語（普通語句，條件，循環，嵌套和方法調用）來實現算法，因此，成本增長的數量級通常是問題規模N的幾個函數之一。

4.倍率實驗

步驟：

1.循環執行ThreeSum方法，并且每次N=2*N（2是比例，可以調整）

2.打印每次執行ThreeSum方法的運行時長和上一次的比

3.直到該比值趨近于2^b（b是常數）

publicstaticvoidRatioTest()

Randomrd=newRandom();

Stopwatchtimer=newStopwatch();

int[]a=newint[125];

for(vari=0;i125;i++)

a[i]=rd.Next(-1000,1000);

timer.Start();

varres=ThreeSum(a);

timer.Stop();

varprev=timer.ElapsedMilliseconds;

for(varN=250;true;N=2*N)

a=newint[N];

for(vari=0;ii++)

a[i]=rd.Next(-1000,1000);

timer.Start();

var_res=ThreeSum(a);

timer.Stop();

vartime=timer.ElapsedMilliseconds;

varratio=(decimal)time/prev;

//Console.WriteLine(a.Length+"\t"+time+"\t"+ratio);

Console.WriteLine(ratio);

prev=time;

//Thread.Sleep(1000);

}

根據冥次法則公式可以推導出該比例是以2為底的對數。并且可以得出增長數量級的近似模型（N^b）：

a為比例數，c為極限比值，b為該算法增長數量級的指數。這里b=3。

這個實驗對于比值沒有極限的算法無效。

該方法可以簡單地預測程序地性能并判斷它們的運行時間大致的增長數量級。

使用該方法可以評估解決大型問題的可行性，比如可以預估一個大型問題的程序運行時間。同時也可以評估使用更快的計算機所運行的時間。

5.注意事項

在對程序的性能進行分析時，得到不一致或者有誤導性的結果的原因有很多：

1.大常數

在去近似時，我們一般會忽略低階項，但如果低階項的系數很大時（例如10^3或10^6），該近似就是錯誤的。所以我們要對可能的大常數敏感。

2.非決定性的內循環

內循環是決定性因素的假設并不總是正確的。錯誤的成本模型可能無法得到真正的內循環，問題的規模也許沒有大到對指令的執行頻率的首項大大超過其他低階項并可以忽略他們的程度。有些程序在內循環之外也有大量指令需要考慮。換句話說，成本模型需要改進。

3.指令時間

由于大多數計算機系統都會使用緩存技術，所以每條執行所需的時間并不是總是相同。

4.系統因素

如果計算機同時運行很多程序，會產生爭奪資源的情況，這會影響實驗結果。

5.對輸入的強烈依賴

在研究程序的運行時間的增長數量級時，我假設運行時間和輸入相對無關。當這個條件不滿足時，會得到不一致或者錯誤的結果。例如，ThreeSum返回的不是三個整數為0的對數，而是是否存在。如果前三個整數就滿足，該程序的運行時間的增長數量級為常數；如果輸入不含有這樣的三個整數，程序的運行時間的增長量級為立方級別。

6.多個問題參量

ThreeSum性能分析是僅需要一個參量的函數來衡量程序的性能，參量一般是輸入的規模。但是，多個參量也是有可能的。例如白名單（一個整數列表M個，一個白名單整數列表N個，返回整數列表中有多少個整數在白名單中存在）,運行時間一般和MlogN成正比。

6.處理對于輸入的依賴

輸入模型：我們可以仔細模擬要處理的輸入的種類。這種方法具有挑戰性，因為該模型可能是不現實的。

最壞情況下的性能保證：不管輸入什么，程序的運行時間都小于一定的范圍（取決于輸入大小）。這種保守的方法可能適用于運行核反應堆或心臟起搏器或汽車制動器的軟件。

隨機算法：提供性能保證的一種方法是引入隨機性，例如快速排序和哈希。每次您運行算法時，都會花費不同的時間。這些保證不是絕對的，但是它們無效的機會小于您的計算機被閃電擊中的機會。因此，這種保證在實踐中與最壞情況的保證一樣有用。

操作序列：對于許多應用程序，算法輸入可能不僅是數據，還包括客戶端執行的操作順序。

均攤分析：提供性能保證的另一種方法是通過記錄所有操作的總成本并除以操作總數來將成本均攤。

7.內存

計算程序對內存的使用情況和運行時間一樣重要。計算機中電路的很大一部分作用就是幫助應用程序保存一些值并在使用時取出。保存的值越多，需要的電路越多，需要的內存也越多。

.net內存分配系統已經幫我們解決了內存問題。

.net使用8位（64位）表示字節，每個基本類型需要的內存：

1.對象

一個對象所使用的內存，需要將所有實例變量使用內存與對象本身的開銷（一般是16字節，這些開銷包括一個指向對象的類的引用，垃圾回收信息和同步信息）以及4個填充字節相加。

當我們說一個引用所占的內存時，指的是它所指向的對象所占的內存。對象的引用通常是一個內存地址，因此使用8個字節的內存（在64位計算機上）。

2.鏈表

嵌套的非靜態類需要額外的8字節。例如，如果Node類是嵌套類，基于鏈表的棧中一個Node對象需要40字節（16字節的對象開銷，兩個對象引用各需8字節，還有8字節的額外開銷。為什么不需要填充字節）。

因為一個Integer對象需要24字節，所以一個含有N個整數的基于鏈表的表需要32+64N字節（Stack對象開銷16字節，引用類型實例變量8字節，int類型實例變量4字節，4個填充字節，每個元素64字節（一個Node對象40字節和一個Integer對象24字節））

3.數組

C#中數組是引用類型，一般都會因為記錄長度需要額外的內存。一個基礎類型的數組一般需要24字節的頭信息（16字節的對象開銷，4字節用于保存長度以及4填充字節）再加上保存值所需的內存。例如一個含有N個int值的數組需要24+4N(會被填充為8的倍數)

4.字符串對象

String的標準實現含有4個實例變量：一個指向字符數組的引用（8字節）和三個int值（各4字節）。第一個int值描述的是字符數組中的偏移量，第二個int值是字符串的長度。第三個值是一個散列值，它在某些情況下可以節省計算。總共需要40字節，這是除字符數組之外字符串所需的內存空間，加上字符數組的話是40+24+2N=64+2N。

但是，字符數組常常是在多個字符串之間共享的。因為String對象是不可變的，這種設計使String的實現能夠在多個String對象中都含有相同的字符數組時節