course1演算法效率、分析与量级algorithmsefficiency,

《course1演算法效率、分析与量级algorithmsefficiency,》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Course1演算法:效率、分析與量級Algorithms:Efficiency,Analysis,andOrder▓Outlines本章重點AlgorithmDef.與5個性質PseudocodeTheImportanceofDevelopingEfficientAlgorithmsAnalysisofAlgorithmsSpacecomplexityTimecomplexityAsymptoticNotation(漸近式表示)Order,,,o,UsingaLimittoDetermineOrder2通常在針對某一問題開發程式時，都會經過下列步

2、驟：Step1:明確定義問題Step2:設計演算法，並評估其執行效率Step3:撰寫程式，並加以測試Example:計算大學入學考試中，某一單科分數之高標明確定義：計算所有考生在該科中前25%成績之平均。演算法：Step1:將所有考生英文成績排序(由高至低)Step2:將排名在前面1/4的成績資料相加後，再除以1/4的人數撰寫程式：...▓Algorithm3當我們使用某種技巧解決一個問題時，會產生一種逐步執行的程序(step-by-stepprocedure)來解決問題，該種逐步執行的程序即稱為解決這個問題的演算法。Def:完成特定功能之有限個指令之集合

3、。需滿足下列5個性質：Input:外界至少提供0個輸入Output:Algorithm至少產生1個輸出結果Definiteness(明確):每個指令必須是ClearandUnambiguousFiniteness(有限性):Algorithm在執行有限個步驟後，必定終止Effectiveness(有效性):用紙跟筆即可追蹤Algorithm中執行的過程及結果4Pseudocode(虛擬碼)Oneofthemostcommontoolsfordefiningalgorithmsispseudocode,whichispartEnglish,partStr

4、ucturedCode.Note:5問題1:搜尋問題範例:ExampleofPseudocode6問題演算法:7Nostandardforpseudocode可以寫得很像英文敘述也可以寫得很像程式語句8▓發展有效率演算法的重要性不管電腦變得多快，記憶體變得多便宜，效率(Efficiency)仍然是設計演算法時最重要的考量.排序問題(Sortingproblem):將一組資料以遞增(increasing)或以遞減(decreasing)的順序加以排列.11,7,14,1,5,9,10↓sort1,5,7,9,10,11,14欲比較的兩個演算法:Inserti

5、onsort(插入排序法):O(n2)Quicksort(快速排序法):O(nlogn)9兩個演算法所安裝之系統:QuickSort:IBMPC/XT(1983年產品，以Intel8088CPU為核心)InsertionSort:VAX8800(DEC超級迷你電腦)10▓演算法的分析若要得知一個演算法解決一個問題有效率的程度，我們必須分析(Analyze)該演算法。一個Algorithm的好壞，通常有兩個評估因子：Space(空間):SpaceComplexity記憶體複雜度(MemoryComplexity)Time(時間):TimeComplexity

6、11時間複雜度(TimeComplexity)一般來說，對一個演算法進行時間複雜度分析就是求得：在每個不同的輸入大小(thesizeoftheinput)之下，該演算法所執行的基本運算次數(howmanytimessomebasicoperationisdone)。分析方式：我們要分析一個演算法的效率，是將該演算法在每個不同的輸入大小之下，所執行的基本運算次數設定成一個函數(Function;或稱Timefunction,Complexityfunction亦可)T(n)。T(n)被定義為在大小為n的輸入範例下，某一個演算法所執行的基本運算次數。(then

7、umberoftimesthealgorithmdoesthebasicoperationforaninstanceofsizen.)12範例每行指令的執行次數程式01n+1n1floatsum(floatlist[],intn){inti;floattempsum=0;for(i=0;i

8、始值，指派的動作就會有相對應的執行碼產生以供程式執行時使用。13有