【经管类】基本概论

《【经管类】基本概论》由会员分享，可在线阅读，更多相关《【经管类】基本概论（89页珍藏版）》请在金锄头文库上搜索。

1、基本概論,Basic concepts,學習目標,在學習本章之後，讀者們要能夠瞭解： 1.何謂資料結構 2.認識演算法和資料結構在資訊科學領城扮演的角色。 3.學習用程式語言來撰寫各種資料結構。 4.瞭解資料結構的實際應用。,資料、資訊 與 資料結構,資料(Data),是用來表達一個觀念或一個事件的一群文字、數字、符號或圖表 例如股票行情、火車時刻表及報章雜誌等上的文字、數字及圖表 從計算機處理的觀點來看，所謂資料就是指可以輸入到計算機中，並且被程式處理的文字、數字、符號或圖表。 包括了數值資料、字串資料及多媒體資料(影像、聲音及視訊),資訊(information),利用大量的資料，經過有系

2、統的整理、分析、篩選處理而提鍊出來 具有參考價格及提供決策依據的文字、數字、符號或圖表 將有用資料作整理、歸納與分析。,資料結構(Data Structure),資料元素不是獨立存在的，它們之間存在著某稱的邏輯關係 資料結構應包括兩部分：資料和結構 資料是指資料元素的有限集合 結構則是指資料元素間關係的集合 資料結構的目的主要有二 節省資料儲存的所需的空間 是加快資料處理的速度,資料、資訊與資料結構,資料結構 演算法 與程式,資料結構和演算法是有著密切關係的，選擇一個好的資料結構，有助於製造一個好的演算法，寫出一個好的程式。一個好的資料結構應便於有效地進行資料的追加、刪除和檢索，應能簡潔的表現

3、複雜的結構 我們的目標在於將抽象的資料結構及演算法轉換成具體的電腦程式，用來解決問題。,資料、資訊與資料結構,資料結構(Data Structure)+ 演算法(Algorithms)=程式(Program) 資料結構、演算法可以說是一切程式設計的基礎。 只要有良好的資料結構和演算法，就可以設計出一個好的程式 資料結構研究的方向就是如何讓電腦能快速地從記憶體中，拿出我們所需的資料 資料結構和演算法對一個執行有效率的程式來說，扮演著非常重要的角色。,資料結構,常見的資料結構,集合 線性結構 樹狀結構 圖形結構,定義及特性,指相互之間存在一種或多種特定關係的資料元素的集合，而根據資料元素之間關係的

4、不同特性 相關資料的組合，以某種方式組識而成，讓我們能把這樣的組合對應到某種抽象的觀念或是實際的事物。 資料結構可能非常單純，也可能非常的複雜,資料結構的定義分成兩部分來討論： 一是資料定義與組識的邏輯(logical)結構 另一個是和資料操作有關的實體(Physical)結構。 資料結構可定義成：如何安排資料以配合適當的演算法解決問題的學問。 資料結構簡化了解決問題的程序,基本結構,集合(Set)： 即數學中的集合關係一樣，資料元素的關係就是一個集合，它們之間沒有任何先後次序的關係，並著重在資料是否存在或屬於集合的問題。,線性結構： 資料元素之間存在一對一的關係，我們稱之為有序的集合(Ord

5、ered set) ，也就是資料與資料之間是有先後次序的 例如陣列(Array)、串列(List)、堆疊(Stack)與佇列(Queue)等 這樣的結構不僅要知道資料是否存資料集合中，還要確定資料儲存的位置和前後資料之間的順序 Chapter2,3,4,5章,樹狀結構： 結構中元素存在一對多的關係，如二元搜尋樹(binary search tree)、累堆(heap)也就是說資料具上下關係的階層化組織 第6,7章,圖形結構： 資料元素彼此間存在多對多關係，所謂的先後和上下關係，在此類的資料結構中，變得更模糊了 第8章,演算法,定義,演算法描述解決問題的方法，而且是以程序式的描述為主，讓人一看就

6、知道是怎麼一回事 可以用某種程式語言來撰寫演算法所代表的程序，並由電腦來執行這個程式 在演算法中，必須以適當的資料結構來描述問題中抽象或具體的事物，有時還得定義資料結構本身有那些操作。,演算法(Algorithm)代表一系列為達成某種目標而進行的工作，通常演算法裡的工作都是針對資料所做的某種處理 有很多日常生活或工作中的事務可以用演算法來描述 電腦科學中所談的演算法是比較嚴謹的,特性或條件(criteria),輸入(Input)： 演算法通常是接受一些輸入，加以處理或運算，而 產生一些輸出值。這些輸入必須有清楚的型別和個數描述。 輸出(Output)： 結果的描述，至少輸出一個結果。,有限的(

7、Finiteness)： 演算法必須要能在有限的步驟內完成或終止，而且所使用的資料量也是有限的。我們不需要知道執行步驟的確實數目，但必須知道執行此演算法的步驟(或時間)不會超過某個上限。 有效的(Effectiveness)： 清楚而不造成混淆，並且能讓使用者用紙筆來執行。,表示法,代數的表示法： 表格式的表示法： 利用像陣列或矩陣的結構也可以描述演算法 例如申報所得稅時所用的累進稅表，從表格中的資訊可計算出應該繳的所得稅。 假如用列表方式就能達到目的，其實並不需要複雜的表示法。,資料流程圖(DFD，Data flow diagram),很多應用系統以資料的處理為核心，適合用資料流程圖(DFD

8、，Data flow diagram)來表示系統的功能 DFD算是一種半正式的表示法，早在1970年代就被很多人所接受和採用。,控制流程圖： 資料流程(Data flow)和控制流程(Control flow)是演算法一體之兩面 資料流程說明各操作之間交換的資料 控制流程則強調各操作進行的順序，所以資料流程圖比較適合用來描述演算法的功能，而控制流程圖則說明各功能是如何達成的。 控制流程圖（CFD，Control-flow diagram）可採用圖的符號來表示，這些基本符號說明了操作除了能按順序進行外，也可以因某些條件成立與否而改變執行的順序。,CFD表示法所用的圖形符號,虛擬碼 虛擬碼兼具文字

9、描述及流程圖的優點，虛擬碼的方式是用文字加程式語言來描述演算法的過程。 下面即是描述如何進入學生選課系統的操作流程：,設計演算法的目標與條件,正確性(correctness)： 根據輸入的資料內容，便能得到預期的資料輸出，也就是可以正確的執行，這是對演算法的基本要求。 可讀性(readability)： 演算法的主要目的是為了讓使用者易於閱讀電腦程式處理的流程，如此才有助於程式日後的維護與修改。 健全性： 對於資料的錯誤輸入與輸出，演算法仍能適當的反應或處理，而不至於使程式或電腦當掉，這就是演算法的健全性。 效率性 (performance)： 面對同樣的問題，不同的演算法所需的時間會有佷大的

10、差別，故一個好的演算法，其執行時間效率必須控制在可以容忍範圍內。 記憶體需求低： 資料的處理會佔用記憶體資源，所佔用的空間則愈小愈好。,程式語言,評估準則,正確性：是否完成所有的事項，並正確的解決問題。 可讀性：是否讓人容易了解程式之原意。 易維護性：是否具有程序、結構化與模組化的基礎。 清晰性：程式中的變數及程序等名稱是否具有意義。 文書性：是否有完備的程式說明文件。 效率性：是否簡單明暸直接表示程式的意圖，以最簡要的程式碼，最快的執行速度來完成。,程式的編寫原則：,程式要段落分明，並以有條不紊的階層式區塊排列； 識別字或變數的命名須有意義； 須簡單且直接表達程式的意義，儘可能使用內建函數；

11、 撰寫結構化程式，引用基本的控制流程結構； 少用GOTO，避免不必要之分支。 多使用副程式以使程式單元化；因為副程式可以重複使用，且程式的測試工作亦容易多了。 善用物件導向程式繼承、封裝與多型等，將軟體IC化可以提昇軟體開發的生產力。 儘量將輸入與輸出、處理邏輯與資料儲存分開來設計。 不要將程式的效率性擺第一，先考慮程式的正確性、清晰性、易讀性及可維護性。 程式必須加上註解，以提升程式的可讀性。,演算法的效率,Performance Measurement,演算法的效率,演算法是否要具有某種結構？ 在設計上有那些考量？ 同一問題是不是可用多種演算法來提供解答？ 我們要如何比較不同演算法的優劣？

12、,分析方式,空間複雜度(Space complexity) 空間複雜度是指演算法使用的記憶體空間的大小，當電腦執行一個演算法時，其實就是在執行一個程式，這個程式所需要的空間包含了程式的指令，變數與常數等，假如占用的空間太大，程式在執行時的效率可能會受到很明顯的影響。 時間複雜度(Time complexity)兩方面來分析。 決定於演算法執行完成所用的時間。在程式設計中，決定某程式區段的步驟計數是程式設計師在控制整體程式系統時間的重要因素，不過要決定精確的次數卻也真是個困難的工作。由於並無法精確的預知一個程式的細部行為，只能以漸近式(Asymptotic Notation) 來討論其複雜度，再

13、根據函數的成長率來判斷演算法的優劣。,時間複雜度,Time Complexity,定義,在程式設計中，決定某程式區段的步驟計數是程式設計師在控制整體程式系統時間的重要因素 往往以一種概量的精神來做為衡量的準則，稱為時間複雜度(Time complexity)。,定義一個T(n) 表示在一個完全理想狀態的計算機中程式所執行的實際指令次數。 時間複雜度是輸入量為n的一種函數 一個程式的執行時間並不完全和輸入量有關，演算法的好壞也會影響 對輸入量n而言，它的最大執行時間就是時間複雜度(Time complexity)的衡量標準。,時間複雜度可包含程式的編譯時間與執行時間 一個程式只要編譯一次即可執行

14、多次 通常我們會比較在意程式的執行時間 常用所謂的漸近式表示法(Asymptotic Notation)來簡化時間複雜度的表示法。,常見的時間複雜度,按照複雜度排序 O(1) O(n) O(n) O(nn) O(n2 ) O(n3 ) O(2 n ) O(1)：常數時間 O(n)：線性時間 O(logn)：次線性時間 O(nlogn)：對數線性時間 O(n2)：平方時間 O(n3)：立方時間 O(2n)：指數時間,程式執行的次數(Frequency count),程式執行所花費的執行次數 有些程式並非每一次執行次數皆相同 當不同的輸入值而有不同的次數。 這樣的情況要將程式分為最佳狀況與最壞狀況

15、 最佳狀況就是1次，最壞狀況是無窮次(n次)。,分析模式,最佳狀況 平均狀況 最壞狀況,最佳狀況 分析演算法對何種輸入資料，所需花費的時間最少。 程式最低的時間複雜度,稱為Omega(W) 也就是程式執行的次數一定相等或大於最佳狀況。 平均狀況(Average-Case) 分析演算法在所有可能的輸入組合下，平均所需要的時間。 程式平均的時間複雜度,稱為Theta(Q) 程式執行的次數介於最佳與最壞狀況之間。,最壞狀況(Worst-Case) 分析演算法在所有可能的輸入組合下，最多所需要的時間。 程式最高的時間複雜度,稱為Big-O 就是程式執行的次數一定相等或小於最壞狀況 較常以Big-Oh來

16、表示演算法的執行效率。,何謂Big-O,定義 f(n) O(g(n) 若存在正的常數和n0，則對所有n n0，必使得得0f(n) Cg(n)的條件成立。 實例說明 假設下列多項式各為某程式片斷或敘述的執行次數，請利用Big-Oh來表示時 間複雜度。 (a) 3n+2 (b) 10n2+5n+1 (c) 7*2n+n2+n 【解析】 (a) 3n+2O(n)，我們可找到c=4，n0=2，使得3n+2 ?4n (b) 10n2+5n+1O(n2)，我們可找到c=11，n0=6，使得10n2+5n+1 ?11n2 (c) 7*2n+n2+n=O(2n)，我們可找到c=8，n0=4，使得7*2n+n2

17、+n ?8*2n,常見Big-Oh的幾種情形,1、 O(1)或O(c)：常數時間 (constant time) 這表示演算法則的執行時間是一個常數倍，而忽略資料集合大小的變化。一個例子是在電腦中它存取RAM所花的時間，在記憶體中去讀取及寫入所用的時間是相同的，而不考慮整個記憶體的數量。如果有這樣的演算法則存在，則我們可以在任何大小的資料集合中自由的使用，而不需要擔心時間或運算的次數會一直成長或變得很高。 2、 O(n)：稱為線性時間 (linear time) 它執行的時間會隨資料集合的大小而線性成長。我們可以找到一個例子是在一個沒有排列過的資料集中要找一個最大元素，且我們以簡單的方式去解釋

18、其內容，直到我們將所有的資料都找過並且找到最大值為止。 3、 O(log2n)：稱為次線性時間 (sub-linear time) 這一種函式的成長速度比線性的程序還慢，而此常數(它是不成長的)的情形還快。 4、 O(n2)：稱為平方時間 (quadratic time) 演算法則執行時間會成二次方的成長，這種會變的不切實際，特別是當資料集合的大小變的很大時。 5、 O(n3)：稱為立方時間 (cubic time) 演算法則執行時間會成三次方的成長，這種會變的不切實際，特別是當資料集合的大小變的很大時。 6、 O(2n)：稱為指數時間 (exponential time) 7、 O(n1og2n)：介於線性及三次方成長的中間之行為模式。,