资源描述：
《物件导向资料结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、AnalyzingAlgorithmsBasedon:物件導向資料結構—使用Java語言,江振瑞著,松崗圖書公司,2005.IntroductiontotheDesignandAnalysisofAlgorithms--Astrategicapproach,2E,R.C.T.Leeet.al.,NcGrawHill,2005.IntroductiontoAlgorithms,Cormenet.al.,MITPress.AnalyzingalgorithmsAnalyzinganalgorithmhascometomeanpredictingth
2、eresourcesthatthealgorithmrequires.Resources:memory,communication,bandwidth,logicgate,time.WeusuallyassumethatthealgorithmisperformedonaprocessorwithRAMAnalyzingalgorithmsTherunningtimeofanalgorithmonaparticularinputisthenumberofprimitiveoperationsor“steps”executed.Itisconve
3、nienttodefinethenotionofstepsothatitisasmachine-independentaspossibleComplexity一般我們使用時間複雜度(timecomplexity)空間複雜度(spacecomplexity)來評估演算法的執行時間與所佔用記憶體空間，這些複雜度愈低，則表示演算法愈好。我們比較關注timecomplexity！ThreeCases演算法的時間複雜度分析分為以下三種：最佳狀況(bestcase)時間複雜度:考慮演算法執行時所需要的最少執行步驟數。最差狀況(worstcase)時間複雜度
4、:考慮演算法執行時所需要的最多執行步驟數。平均狀況(averagecase)時間複雜度:考慮所有可能狀況下演算法的平均執行步驟數。Usually,weconcentrateonfindingonlyontheworst-caserunningtimeReason:ItisanupperboundontherunningtimeTheworstcaseoccursfairoftenTheaveragecaseisoftenasbadastheworstcase.Forexample,theinsertionsort.Again,quadratic
5、function.Worst-caseandaverage-caseanalysisAnAlg.forTestingPrimes我們可以看出，輸入大於2的任意正整數n，若n是質數，則演算法Prime1需要執行整數除法求餘數(n%i)動作與整數比較((n%i)=0)動作n-2次之後，才可以知道n是質數。另外，若n不是質值，則演算法Prime1只要執行整數除法求餘數與整數比較動作1次，就可以知道n不是質數了。AlgorithmPrime1(n): Input:一個大於2的正整數nOutput:true或false(表示n是質數或不是質數) fori
6、←2ton-1do if(n%i)=0thenreturnfalse returntrue我們可以看出，輸入大於2的任意正整數n，若n是質數，則演算法Prime2需要執行整數除法求餘數(n%i)動作與整數比較((n%i)=0)動作-2次之後，才可以知道n是質數。另外，若n不是質值，則演算法Prime2只要執行整數除法求餘數與整數比較動作1次，就可以知道n不是質數了。AnotherAlg.forTestingPrimesAnalysisofPrime1Alg.因此，我們很容易看出來，在最壞狀況(worstcase)下，演算法Prime1的執行步驟
7、次數與輸入的正整數n成正比關係；而在最佳狀況(bestcase)下，演算法Prime1的執行步驟次數為與輸入的正整數n無關的某個常數。也就是說，演算法Prime1具有線性的(linear)最差狀況時間複雜度(正比關係即為線性關係)與常數的(constant)最佳狀況時間複雜度。AnalysisofPrime2Alg.我們也很容易看出來，在最壞狀況(worstcase)下，演算法Prime2的執行步驟次數相依於輸入的正整數n的平方根值；而在最佳狀況(bestcase)下，演算法Prime2的執行步驟次數為與輸入的正整數n無關的某個常數。也就是說，
8、演算法Prime2具有平方根的(squareroot)最差狀況時間複雜度與常數的(constant)最佳狀況時間複雜度。AsymptoticNotat
