《资料与资讯》PPT课件

《《资料与资讯》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章Introduction導論1.1資料與資訊◎資料(data)的定義：〝用具體符號表示，而能夠被計算機處理的資訊(information)〞◎資料強調符號本身，而資訊則強調資料所呈現出來，經過人們分析、理解並領會的事實◎我們將在資料結構這門課中探討計算機系統所儲存以及處理的資料，並且學習如何組織這些資料，以及處理這些資料的方法1.2演算法與資料結構◎演算法(algorithm)的定義：“在有限步驟內解決數學問題的程序”。在計算機科學的領域中，演算法泛指“適合被實作為計算機程式的解題方法”◎演算法通常具有以下五個特性：一‧輸入(Input)二‧明確性(Definiteness)三‧正

2、確性(Correctness)或稱有效性(Effectiveness)四‧有限性(Finiteness)五‧輸出(Output)例1.3歐幾里得演算法計算兩個自然數的最大公因數(GreatestCommonDivisor,GCD)演算法描述如下：步驟1.輸入兩個自然數A,B步驟2.A除以B，餘數為R步驟3.如果R為零，則跳至步驟5步驟4.A←B，B←R，跳至步驟2步驟5.B即為GCD這些敘述符合演算法的特性：一‧輸入(Input)：兩個自然數A,B二‧明確性(Definiteness)：以逐步追蹤法一步一步執行敘述，不造成混淆三‧正確性(Correctness)：以兩組A,B代入執行均得

3、到正確結果四‧有限性(Finiteness)：A,B,R在第二圈以後都會愈來愈小。由於他們都是正整數，所以R終會等於零五‧輸出(Output)：A,B的最大公因數R=AMODBA←BB←R開始是輸入自然數A,BR=0?B為GCD結束否用流程圖來描述這個演算法：1.3程式的分析一個好的程式，通常必須滿足下列的條件：一‧正確達到目的：通常以具有代表性的多組輸入來測試驗證二‧可維護性高：程式的可維護性牽涉到編寫程式的方法和風格，以下是幾項檢驗項目：檢驗項目一：編寫程式是否符合模組化的原則，提供由上而下(Top-Down)的理解思路？檢驗項目二：所有的常數變數及函式(functio

4、n)名稱是否有意義？檢驗項目三：所有函式的輸入、輸出及功能是否被明確地定義？檢驗項目四：是否在適當的地方加上註解？檢驗項目五：說明文件是否詳實完備？三‧效率高：計算程式的時間複雜度來分析效率並尋求改良之道四‧記憶體需求低：在不影響效率的情況下，需求愈低愈好計算n階層(n!)的函式如下：intfactor(intn){intresult,i;1result=1;2i=1;3while(i<=n)4{5result=result*i;6i=i+1;7}8returnresult;}頻率計數的計算我們計算每一行敘述被執行的次數：行號n>0時n<=0時1112113n15n06n0811總次數3

5、n+34如果n>0，頻率計數為3n+3次，如果n<=0，頻率計數為4次for迴圈的計數A.單層迴圈1for(i=1;i

6、ΣΣ1=Σ(n-1)=Σn–Σ1=n2-n=n*(n-1)i=1j=1i=1i=1i=1C.雙層迴圈、內圈不固定次數1for(i=1;i<=n;i++)2for(j=i+1;i<=n;j++)3result=result+1;由於內圈迴圈計數器j的範圍，是隨著外圈迴圈計數器i的範圍改變的，因此我們針對迴圈計數器i的變化來分析：數學模式：nn-1nn總次數＝ΣΣ1=Σ(n-1-(i+1)+1)=Σ(n–i)=n2-n*(n+1)/2=n*(n-1)/2i=1j=i+1i=1i=1i的值j的範圍第3行執行次數12……nn-123……nn-234……nn-3……n-1n……n1nn+1……n0

7、總次數＝n*(n-1)/2Big-O符號Big-O符號的數學定義為：若且唯若f(n)=O(g(n))則存在大於0的常數c和n0，使得對所有的n值，當n≧n0時，f(n)≦c*g(n)均成立。用數學式表示為：f(n)=O(g(n))c,n0>0n≧n0,f(n)≦c*g(n)用口語解釋為：f(n)取Big-O符號為O(g(n))，當n夠大的時候，g(n)相當於是f(n)的上限nn0f(n)c*g(n)用圖示可表達為：◎5n2+