Chap 1 概論Overview.

Presentation on theme: "Chap 1 概論Overview."— Presentation transcript:

1 Chap 1 概論Overview

2 資料(Data) 資料 可以看成是一種沒有評估價值的基本項目或原素（atom），更簡單的說，資料是用來表達一個觀念或一個事件的一群文字、數字、圖形、符號、圖表…等。

3 資訊(Information)

4 演算法（Algorithm） 演算法（Algorithm）
為問題的解決過程中，先做問題的描述，有系統的規劃安排，最後再透過某種能與電腦溝通的介面來讓電腦來執行。 就是一種「計算方法或法則」。 或者也可以將演算法看成是解決某一個工作或問題，所需要的一些有限個數的指令或步驟。

5 演算法（Algorithm） 演算法需要具備以下五大基本原則： 有限性（Finiteness） 有效性（Effectiveness）
必須在有限的步驟內解決問題，不可造成無窮迴路。 有效性（Effectiveness） 每一個步驟或運算若交給人們用筆或紙計算，也能在有限時間內達成同樣效果。 明確性（Definiteness） 每一個步驟或指令必須要敘述的很清楚，不可以模糊不清。 輸入資料（Input） 演算法的輸入資料可有可無，零或一個以上都可以。 輸出資料（Output） 演算法的結果一定要有一或一個以上的輸出資料。

6 複雜度（Complexity ) 空間複雜度（Space Complexity）
執行程式需要使用的空間是下列組成的總和： 與輸入和輸出特性無關的固定部份：通常包含指令空間、簡單變數和固定大小組成變數、及常數所用的空間等。 可變部份：包括組成變數所用的空間、參考變數、和遞迴堆疊空間…等。

7 複雜度（Complexity ) 時間複雜度（Time Complexity）
執行時間 =執行的次數*執行每一行敘述所需的時間 如何計算一個程式從開始執行，到執行完成所用的時間呢？ 在程式中，影響執行敘述（statement）所需的時間有兩項因素：執行的次數與執行每一行敘述所需的時間，執行時間就是以上兩者相乘。

8 複雜度（Complexity ) 時間複雜度的表示法： Big-O O（1）：常數時間（constant time）。
O（log2n）：次線性時間（sub-linear time）。 O（n）：線性時間（linear time）。 O（nlog2n）：nlog2n（對數型）時間。 O（n2）：平方時間（quadratic time）。 O（n3）：立方時間（cubic time）。 O（2n）：指數時間（exponential time）。 O（1）＜ O（log2n）＜ O（n）＜ O（nlog2n）＜ O（n2）＜ O（n3）＜ O（2n）（n>=16）

9 資料的組織 陣列(Array) 鏈結串列(Linked List) 堆疊 (Stack) 佇列(Queue) 樹狀結構 (Tree)
從小學到中學，我們升旗時，司令台下那一班一班整齊的排序，不就如同「陣列」嗎？ 鏈結串列(Linked List) 火車進站時，不覺的車廂一節、一節的閃過，也就是「鏈結串列」囉！ 堆疊 (Stack) 而日前綜藝節目常見的樂高積木不就是一種「堆疊」了。 佇列(Queue) 搭公車、或下公車時！一個一個上去或下來的情況不也可以說成是一種「佇列」。 樹狀結構 (Tree) 代表中國人血脈相承的〝祖譜〞不用說必定是一種「樹狀結構」了

10 Schedule Overview 7/7(一) Array 7/8(二) Stack 7/14(一) Queue 7/15 (二)
Mid Term Exam 7/21 Linked List 7/21(一) Tree 7/22 (二) Graphic 7/28(一) Sorting Searching 7/29 (二) Review & Final Exam 7/30

11 Grade Mid Term Exam 30% Final Exam 30% Exercise 25% Present 15%