鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第一章:基本概念 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/

Slides:



Advertisements
Similar presentations
Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order
Advertisements

基本概論 Basic concepts.
Chapter 10 搜尋(search).
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
第1单元 操作系统概论 第一节 绪论 操作系统定义.
Introduction 基本概念 授課老師:蕭志明
第一章 資料結構導論 1-1 資料結構簡介 1-2 認識程式設計 1-3 演算法效能分析 1-4 物件導向程式設計與Java.
資料結構與演算法 課程教學投影片.
資料結構 第9章 搜尋.
第 九 章 搜尋(Search) 課程名稱:資料結構 授課老師:_____________.
Chapter 3 The Fundamentals : Algorithms, the Integers, and Matrices
動畫與遊戲設計 Data structure and artificial intelligent
算法设计与分析 李清勇 教授 办公室:第九教学楼北201.
计算学科的基本问题 本章首先介绍一个对问题进行抽象的典型实例——哥尼斯堡七桥问题。然后,通过“梵天塔”问题和“停机问题”分别介绍学科中的可计算问题和不可计算问题。从“梵天塔”问题再引出算法复杂性中的难解性问题、P类问题和NP类问题,证比求易算法,P=NP是否成立的问题。
数据结构(C语言版) Data Structure
Performance Evaluation
B081 LabVIEW 7.X 實用教本 第12章 程式架構.
The discipline of algorithms
第8章 字串與陣列 8-1 字串處理 8-2 一維陣列的處理 8-3 建立多維陣列 8-4 不規則陣列與參數傳遞 8-5 陣列排序與搜尋.
Minimum Spanning Trees
Chap4 Tree.
计算机问题求解 – 论题 算法的效率 2018年03月14日.
第8章 字元與字串處理 8-1 C語言的字元檢查函數 8-2 C語言的字串 8-3 字串的輸入與輸出 8-4 指標與字串
物件導向程式設計 (Object-Oriented rogramming)
計算方法設計與分析 Design and Analysis of Algorithms 唐傳義
Course 4 搜尋 Search.
第 1 章 演算法分析.
搜尋資料結構 Search Structures.
第七章 搜索结构 静态搜索结构 二叉搜索树 AVL树.
第12章 樹狀搜尋結構 (Search Trees)
程序设计期末复习 黎金宁
程式撰寫流程.
C 語言簡介 - 2.
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
CHAP13 演算法概論 高中資訊科技概論 松崗圖書公司.
重點 資料結構之選定會影響演算法 選擇對的資料結構讓您上天堂 程式.
Data Structure.
数据结构 第八章 查找.
第十章 指针.
樹 2 Michael Tsai 2013/3/26.
数据结构 第一章 绪论.
东北林业大学 陈宇 ACM程序设计 东北林业大学 陈宇
感謝同學們在加分題建議. 我會好好研讀+反省~
Chapter 5 Recursion.
作业 考核方式 书面作业:每个单元3-5个题,树、图和查找单元5-10个题。 上机作业:从第三周起每周一次 , 大约14次
第1章 概述 本章要点: C语言程序结构和特点 C语言程序的基本符号与关键字 C语言程序的编辑及运行 学习方法建议:
鄧姚文 資料結構 第五章:遞迴 鄧姚文
Week 2: 程式設計概念與 演算法的效能評估
Total Review of Data Structures
資料結構與C++程式設計進階 排序與搜尋 講師:林業峻 CSIE, NTU 6/ 14, 2010.
第1章 绪论 2019/4/16.
计算机算法基础 周中成 苏州科技学院应用数学系 2019/4/18.
資料結構與演算法 第一章 基本概念 徐熊健 資料結構與演算法 徐熊健.
Oop8 function函式.
資料結構使用Java 第9章 樹(Tree).
99高中資訊科選修課程 夥伴學習教師 專業進修研習 進階程式設計--演算法 教學示例與研討
演算法時間複雜度 (The Complexity of Algorithms)
講師:郭育倫 第2章 效能分析 講師:郭育倫
資料結構與C++程式設計進階 遞迴(Recursion) 講師:林業峻 CSIE, NTU 6/ 17, 2010.
資料結構簡介 綠園.
演算法的效率分析.
演算法分析 (Analyzing Algorithms)
累堆排序法 (Heap Sort).
挑戰C++程式語言 ──第9章 函數.
北一女中 資訊選手培訓營 遞迴、河內塔與merge sort Nan.
遞迴 Recursion.
《数据结构与算法设计》第一部分 面向对象的C++程序设计基础.
Data Structure.
JAVA 程式設計與資料結構 第十七章 Tree.
105-1 Data Structure Homework 4
Presentation transcript:

鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第一章:基本概念 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/

資料結構 資料(Data) 資料結構(Data Structure) 電腦處理的符號 資料之間的邏輯關係 著重問題需求和資料之間的關係 數值(Numerical) 字串(String) 多媒體(Multimedia) 資料結構(Data Structure) 資料之間的邏輯關係 表現方式(Representation) 處理方式(Manipulation) 著重問題需求和資料之間的關係

資料特性 識別(Identification) 順序(Sequential Order) 階層(Hierarchical Structure) 形狀 線性結構(Linear) 樹狀結構(Tree) 圖形結構(Graph)

演算法(Algorithm) 一組可完成特定工作的指令集合 必要條件: 輸入(Input):0~n個資料輸入 輸出(Output):至少一個輸出 明確(Definiteness):清楚而明確 有限(Finiteness):在有限的步驟內結束 有效率(Effectiveness):用紙和筆即可實踐之;可行(Feasible)

範例:找尋最大值 輸入:n個數字 輸出:這n個數字之中的最大值 步驟: 將n個數字排好成一列 令第1個數字為最大值max 若m比max大,則令max的值等於m 輸出max,這n個數字之中的最大值

範例:求函數f(x)的最大值 輸入:函數f(x) 輸出:f(x)的最大值 步驟: 令max為最小的實數 從0開始逐一嘗試每一個實數x 令y=f(x) 若y比max大,令max的值等於y 令z=f(-x) 若z比max大,令max的值等於z 輸出max,此即f(x)的最大值

演算法的表示方式 自然語言 虛擬碼(Pseudo Code) 流程圖(Flowchart) 結構性較好的程式語言 Pascal、C、C++、Java、C#、… 不要用稀有的語言,以免別人看不懂 演算法(Algorithm)與程式(Program)的差異: 演算法必須在有限步驟內停止,程式未必會停 不停的程式:作業系統、Email Server、Web Server、…

程式撰寫的流程 問題的需求與限制 思考與探索 資料結構與演算法設計 撰寫程式碼 驗證、測試與修改 結果輸出

演算法的效率分析 時間複雜度(Time Complexity) 空間複雜度(Space Complexity) 複雜度的表示法 所需的執行時間 Σ一行敘述的執行次數 × 一行敘述的執行時間 空間複雜度(Space Complexity) 所需的記憶體空間 複雜度的表示法 О、Ω、Θ

Order of Magnititude O(n) O(n3) for (x = 0; x < n; x++) { do_something(); } for (x = 0; x < n; x++) { for (y = 0; y < n; y++) { for (z = 0; z < n; z++) { do_something(); } O(n2) for (x = 0; x < n; x++) { for (y = 0; y < n; y++) { do_something(); }

Big-O 演算法的複雜度 定義: 若且唯若存在兩個正整數 c 和 n0 當 n ≥ n0 時, 意義:Upper Bound 上限

範例:

範例:

時間複雜度分析範例: 循序搜尋(Sequential Search) 最佳狀況 Best Case:1 搜尋目標在陣列一開頭就找到了 最壞狀況 Worst Case:n 找完整個陣列才知搜尋目標不在其中 平均狀況 Average Case:n/2 平均搜尋次數: 若搜尋成功之機率為 p:

循序搜尋 (Sequential Search) int sequential_search(int data[], int target, int n) { int i; for (i = 0; i < n; i++) { if (target == data[i]) { return i; } return -1;

Big-O 順序 O(1):常數時間(Constant Time) O(log2n):次線性時間(Sub-linear Time) O(n):線性時間(Linear Time) O(nlog2n): n 對數時間 O(n2):平方時間(Quadratic Time) O(n3):立方時間(Cubic Time) O(2n):指數時間(Exponential Time) O(n!):階乘時間 大

Big-Ω 問題的難易程度 定義: 若且唯若存在兩個正整數 c 和 n0, 當 n ≥ n0 時, 意義:Lower Bound 下限

範例:

Θ 最佳解(Optimal Solution) 定義: 若且唯若存在三個正整數 c1、c2、n0, 當 n ≥ n0 時

二元搜尋 (Binary Search) 輸入: 輸出: n 筆已排序資料(從小排到大) 欲尋找之資料 target 1 2 3 4 5 6 7 8 9 找 5 大 小 中

二元搜尋(Binary Search) int binary_search(int data[], int n, int target) { int left = 0, right = n-1, mid; while (left <= right) { mid = (left + right) / 2; if (target == data[mid]) { return mid; } else if (target > data[mid]) { left = mid + 1; } else { right = mid - 1; } return -1;

二元搜尋(Binary Search) 遞迴版(Recursive) int bin_search(int data[], int left, int right, int target) { int mid = (left + right) / 2; if (left > right) return -1; if (target == data[mid]) return mid; if (target > data[mid]) { return bin_search(data, mid+1, right, target); } else { return bin_search(data, left, mid-1, target); } 用法: bin_search(data, 0, n-1, target)

二元搜尋(Binary Search) 時間複雜度:O(log n) 搜尋範圍從 n 筆資料開始 每完成一次比較,搜尋範圍縮小一半 停止的時機: 找到目標 搜尋範圍的大小<1(Worst Case) n 連續除以 2,連除 m 次之後 < 1

費氏數列(Fibonacci Series) 問題:給定一個 n 值,求解費氏數列第 n 項的值。

費氏數列(Fibonacci Series) 遞迴版 int fibon(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibon(n-1) + fibon(n-2); } 時間複雜度:O(2n/2)

費氏數列(Fibonacci Series) 遞迴版時間複雜度分析

費氏數列(Fibonacci Series) 迴圈版 int fibonacci(int n) { int fn, fn_1 = 1, fn_2 = 0, i; if (n < 2) return n; for (i = 2; i <= n; i++) { fn = fn_1 + fn_2; fn_2 = fn_1; fn_1 = fn; } return fn; 時間複雜度:O(n)

Tower of Hanoi

Tower of Hanoi

Tower of Hanoi 宣告與用法 #define PEG_A "PEG_A" #define PEG_B "PEG_B" #define PEG_C "PEG_C" int main(int argc, char* argv[]) { … hanoi_move(n, PEG_A, PEG_B, PEG_C); }

Tower of Hanoi 主要邏輯 void hanoi_move(int n, char* from, char* to, char* via) { if (n == 1) { printf("Move ring 1 from %s to %s\n", from, to); } else { hanoi_move(n-1, from, via, to); printf("Move ring %d from %s to %s\n", n, from, to); hanoi_move(n-1, via, to, from); }

Tower of Hanoi 執行結果 1: Move ring 1 from PEG_A to PEG_B 2: Move ring 2 from PEG_A to PEG_C 3: Move ring 1 from PEG_B to PEG_C 4: Move ring 3 from PEG_A to PEG_B 5: Move ring 1 from PEG_C to PEG_A 6: Move ring 2 from PEG_C to PEG_B 7: Move ring 1 from PEG_A to PEG_B

Tower of Hanoi 時間複雜度分析