Week 2: 程式設計概念與 演算法的效能評估

Slides:



Advertisements
Similar presentations
多元評量與 Greenfoot 簡介 南港高中高慧君. 演講大綱 多元評量 高中階段程式設計教學目標與困境 Greenfoot 快速入門 – 袋熊吃樹葉 – 沙灘螃蟹 Greenfoot 臺灣社群介紹 2.
Advertisements

3.2 Java的类 Java 类库的概念 语言规则——程序的书写规范 Java语言 类库——已有的有特定功能的Java程序模块
Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order
基本概論 Basic concepts.
数据结构 杨鹏宇 QQ: 版权所有,转载或翻印必究
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
Introduction 基本概念 授課老師:蕭志明
第一章 資料結構導論 1-1 資料結構簡介 1-2 認識程式設計 1-3 演算法效能分析 1-4 物件導向程式設計與Java.
迴圈 迴圈基本觀念 while迴圈 do 迴圈 for迴圈 巢狀迴圈 迴圈設計注意事項 其他控制指令 迴圈與選擇的組合.
算法设计与分析 李清勇 教授 办公室:第九教学楼北201.
第5章 回溯法 欢迎辞.
四資二甲 第三週作業 物件導向程式設計.
C#程序设计案例教程 第3章 程 序 结 构.
数据结构(C语言版) Data Structure
南京理工大学 第2章 Java基本语法 本章我们将学习Java编程语言的基本语法,包括变量、操作符、表达式、语句、字符串、数组、控制流以及如何使用帮助文档。 使用下面的编程框架: public class Test{ public static void main(String []args){ //以下添加测试代码.
Performance Evaluation
D、結構化技術 主要的結構化技術 結構化程式設計 (Structured Programming)
Recurrences 給定T(n)=T(n/2) + O(n) 我們該如何得到 T(n) = O(nlogn)?
第二章 JAVA语言基础.
第三章 控制结构.
计算机问题求解 – 论题 算法的效率 2018年03月14日.
程式設計實作.
Q1: 追蹤程式: 印出結果? 搶答 while (i<=n) { p=p*i; i=i+2; }
2.1 基本資料型別 2.2 變數 2.3 運算式與運算子 2.4 輸出與輸入資料 2.5 資料型別轉換 2.6 實例
控制流程 邏輯判斷 迴圈控制.
C++Primer 3rd edition 中文版 Chap 5
程式敘述執行順序的轉移 控制與重複、方法 Lecturer:曾學文.
第3章 語法入門 第一個Java程式 文字模式下與程式互動 資料、運算 流程控制.
第 1 章 演算法分析.
新世纪计算机专业系列教材 数据结构 C++实现 第一章 缪淮扣 顾训穰 沈 俊 编著 科 学 出 版 社.
程式設計實作.
第四章 基本輸出入 Java應用程式的輸出入介面有三種,分別是命令提示字元視窗、AWT元件、及Swing元件。本單元先介紹命令提示字元視窗,AWT請看第16、17章,Swing請看第20章。 輸入 輸出.
第2章回顾 标识符:不用记,动手 关键字:if, else, switch, for, while, do, break, continue, void, …… 局部变量和成员变量 ①变量作用域 ②内存布局 基本数据类型 ①4类8种 ②互相转换 流程控制语句 ①分支 if……else, switch.
程式撰寫流程.
新觀念的 VB6 教本 第七章 讓程式轉彎的控制敘述.
程式語言Visual Basic 重複結構 黃瀧輝 老師 Long Hwai,Huang.
實作輔導 3 日期: 4/14(星期六) 09:10~12:00、13:10~16:00
3.1 数据类型 3.2 标识符与关键字 3.3 常量 3.4 变量 3.5 运算符与表达式 3.6 一个编程实例
2019/1/17 Java语言程序设计-程序流程 教师:段鹏飞.
数据结构 第一章 绪论.
计算机算法设计与分析(第3版) 王晓东 编著 电子工业出版社.
4.2通讯服务模块线程之间传递信息 信息工程系 向模军 Tel: QQ:
第三章 C# 基础知识.
鄧姚文 資料結構 第一章:基本概念 鄧姚文
《JAVA程序设计》 语音答疑 辅导老师:高旻.
實作輔導 2 日期: 3/24(星期六) 09:10~16:00 地點:臺北市立大學 臺北市中正區愛國西路一號 (中正紀念堂站7號出口)
第二章Java基本程序设计.
第1章 绪论 2019/4/16.
資料結構與演算法 第一章 基本概念 徐熊健 資料結構與演算法 徐熊健.
第二章 Java基本语法 讲师:复凡.
第1章 绪论(二) 教学目标 理解算法的特性及评价标准 掌握算法时间复杂度和空间复杂度的分析方法 1/
7.1 C程序的结构 7.2 作用域和作用域规则 7.3 存储属性和生存期 7.4 变量的初始化
演算法時間複雜度 (The Complexity of Algorithms)
<编程达人入门课程> 本节内容 为什么要使用变量? 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ:
第二章 Java语法基础.
第二章 Java基本语法 讲师:复凡.
資料結構簡介 綠園.
演算法的效率分析.
演算法分析 (Analyzing Algorithms)
龍老師我不會Debug QQ.
#include <iostream.h>
第二章 Java基本语法 讲师:复凡.
Open topic2: 大O( Θ ,Ω)和小o( θ ,ω)有什么区别? 3/19/18 黄秉焜
PPT注意事项: 当前PPT课件文件必须和提供的源代码文件夹“代码”在同一目录中即不要移动文件夹“代码”的默认位置。
迴圈(重複性結構) for while do while.
判斷(選擇性敘述) if if else else if 條件運算子.
第三章 流程控制 程序的运行流程 选择结构语句 循环结构语句 主讲:李祥 时间:2015年10月.
第二章 Java基础语法 北京传智播客教育
輸出執行結果到螢幕上 如果要將執行結果的文字和數值都「輸出」到電腦螢幕時,程式要怎麼寫? class 類別名稱 {
第二章 Java基本语法 讲师:复凡.
Presentation transcript:

Week 2: 程式設計概念與 演算法的效能評估

學習目標 能說出好程式的條件 能寫出結構化程式主要的三個流程結構 能描述兩大類評估演算法效能的方式 能以三種時間複雜度的表示法評估一個演算法的執行次數 能判斷不同等級的時間複雜度之順序

程式設計的概念 程式是資料結構與演算法的實作 程式設計的步驟 Step 1: 分析所要解決的問題 Step 2: 設計解題的步驟 (演算法) 了解需求,確定輸入與輸出資料 Step 2: 設計解題的步驟 (演算法) 使用文字敘述、流程圖或虛擬碼來表示 Step 3: 撰寫程式 Step 4: 上機測試、偵測錯誤 Step 5: 編寫程式說明書

演算法和程式的差異 「演算法」是以「人」為主,亦即「任何人都可以閱讀的程式碼」,因此,必須特別強調「可讀性」 以流程圖或虛擬碼來說明 「程式」則是以「電腦」為主,它強調程式的執行結果正確性、可維護性及執行效率

為什麼要撰寫程式 我們為什麼要花那麼多時間來撰寫程式呢? 主要目的:它可以快速解決「複雜的問題」

好程式的條件 正確性(Correctness) 效率性(Performance) 可維護性(Maintainable) 基本要求 以頻率計數(Frequency Count)來計算程式被執行的次數,評估程式的效率,例如: 可維護性(Maintainable) 程式設計方法和風格—結構化程式設計、縮排、註解、變數命名、程式說明書等等

結構化程式設計 結構化程式設計由Dijkstra (1969)提出: 利用「由上而下」的技巧,將程式分解成多個具有獨立功能的模組 1. 消除程式因goto而造成如麵條式的混亂狀態 2. 強調任何程式邏輯均可由三種結構組成 利用「由上而下」的技巧,將程式分解成多個具有獨立功能的模組 主系統 獨立功能 模組1 獨立功能 模組2 獨立功能 模組3

三個基本結構 循序(Sequence):簡單命令式的指令如 COMPUTE, READ, WRITE 與代數指令如X=Y+Z 選擇(Condition):需做決策時,用 IF-THEN-ELSE 指令與CASE 指令 重複(Repetition):當需反覆時,用 DO-WHILE 與DO-UNTIL 指令

循序結構 程式由上而下逐一執行 最基本的結構 開始 敘述1 敘述2 ............ 敘述n 結束 import java.io.*; public class test { public static void main(String[] args) float Average=0; int score1=60,score2=70; Average = (float)(score1+score2)/2 ; System.out.println("平均:" + Average); } 敘述2 ............ 敘述n 結束

選擇結構 又可稱為決策結構,在某種條件成立時才執行某些敘述,不成立時則執行另一種敘述 import java.io.*; public class test { public static void main(String[] args) int score=80; if (score<60) System.out.printf(“不及格”); else System.out.printf(“及格”); } True 條件式 False 敘述1 敘述2

重複結構 讓某一段程式反覆執行多次的敘述的結構,稱為「迴圈結構」或「重複結構」 例如: for 迴圈結構 i=1 import java.io.*; public class test { public static void main(String[] args) int sum=0; for (int i=1; i<=100; i++) sum+=i; } i<=100 False True sum+=i i++

重複結構 (續) 讓某一段程式反覆執行多次的敘述的結構,稱為「迴圈結構」或「重複結構」 例如: while 迴圈結構 i=1 import java.io.*; public class test { public static void main(String[] args) int sum=0, i=1; while (i<=100) { sum+=i; i++; } }} i<=100 False True sum+=i i++

演算法的效能評估 用來計算某些演算法所撰寫的程式,在經過編譯之後實際執行所需要的時間 但是,實務上有可能因為程式編譯的過程或是電腦設備的差異使得效率分析會因電腦的軟硬體不同而有不同的結果 因此,效能的評估方式可分為兩大類: 空間複雜度(Space Complexity) 時間複雜度(Time Complexity)

空間複雜度 指從呼叫程式開始到完成之過程,所佔用的記憶體空間 例如:變數宣告、函數呼叫、參數傳遞等 由於記憶體和儲存媒體愈來愈大,也愈來愈便宜,程式執行所需空間比較不是問題,因此,時間複雜度比空間複雜度來得重要 通常評估程式或演算法的效率,較常以時間複雜度來評估

時間複雜度 指程式開始執行到結束所花費的時間 影響程式執行時間的因素 演算法的優劣 電腦的執行速度(CPU速度) 執行時間 = 執行次數 × 每次執行所需時間 執行每一行程式所需時間必須考慮到電腦CPU執行速度及編譯器的功能,在評估上比較不客觀。因此,通常只考慮執行的次數,執行次數的多寡,往往是用來決定演算法效率的好壞。

如何計算程式執行次數? 計算程式的執行次數,亦可稱為頻率計數(Frequency Count)指每一行程式的執行次數,或者更精確一點說,是每一個敘述的執行次數,兩者皆有學者採用 public sum() { int s=0; for (int i=1; i<=100; i++) s+=i; } 執行次數 頻率計數 1次 1次 101次 1+101+100次 100次 100次 202次 303次 本教材使用頻率計數

頻率計數的計算規則 只計算可執行的程式碼 同一個運算式只算一次 未指定初值的變數宣告不算 註解不算 程式區塊的左右大括號 { 和 } 都不算 例如: a=a+1雖然有兩個運算(=和+),但只算一次 未指定初值的變數宣告不算 註解不算 程式區塊的左右大括號 { 和 } 都不算

舉例1 例如:下列程式的頻率計數為多少? 1次 2次 3次 4次 //這是一個測試程式 int a=4, b=6, c; c=a+b; <PowerClick><Answer>3</Answer><Option>4</Option><Point>1</Point></PowerClick>

舉例2 假設一個運算所花費的時間為一個單位時間,分析下面程式的執行時間 int s=0; 1 for (int i=1; i<=100; i++) s+=i; System.out.println(“s=“+s); 1 1+101+100 100 1 共需 304 單位時間

分析程式時,資料量通常以無線大的情形來考慮,即n值很大時 舉例3 假設一個運算所花費的時間為一個單位時間,分析下面程式的執行時間 int s=0, n; for (int i=1; i<=n; i++) s+=i; System.out.println(“s=“+s); 1 1+(n+1)+n n 1 分析程式時,資料量通常以無線大的情形來考慮,即n值很大時 共需 3n+4 單位時間

舉例4 假設一個運算所花費的時間為一個單位時間,分析下面程式的執行時間 for (int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { System.out.println(i*j); } 1+(n+1)+n n×(1+(n+1)+n) n×n×1 共需 3n2+4n+1 單位時間 通常會定義執行時間為一個函式T(n) T(n) = 3n2+4n+1

時間複雜度的概算 雖然評估演算法愈精準愈好,但耗費很大功夫計算真正的執行次數是沒有意義的,因此我們常使用「概量」(漸進式表示法)來衡量 三種時間複雜度概量表示法 O (Big-O)…以最多時間來概算(上限) Ω(Omega)…以最少時間來概算(下限) Θ(Theta)…以恰好時間來概算(同時為上限和下限) 最常使用

時間複雜度: O (Big-O) Big-O可視為時間複雜度的最壞表現,或稱為理論上限(Upper bound) 定義:某程式的執行時間為T(n) ,若存在兩個常數c和n0,當n≧n0時,使得T(n)≦cf(n) ,則此程式的時間複雜度是O(f(n))

時間複雜度: O (Big-O) 例如:請證明T(n)=4n2+174 的時間複雜度可用O(n2)表示 ∵ 欲證明 T(n)=O(n2) ∴ f(n)=n2 預找到某 c 使得T(n)≦cf(n) 亦即 4n2+174 ≦ c * n2 ∴ (c-4) n2 ≧ 174 ∴ 我們可找到 c=5 時,n2 ≧174,對所有n > n0 = 14 使得 4n2+174 ≦ 5 * n2,所以 T(n)= O(n2)

時間複雜度: O (Big-O) 原理說明 假設某一演算法的估算時間函式T(n)=4n2+174,則我們預估其時間複雜度為O(n2) ,亦即f(n)=n2 當n ≧14 (=n0) 之後,5×f(n) 一定會大於或等於T(n),所以O(n2)足以代表4n2+174 <Operate>

時間複雜度: O (Big-O) 例如:下列程式的時間複雜度Big-O為何? for (int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { System.out.println(i*j); } 1+(n+1)+n n+n×(n+1)+n×n n×n 共需 3n2+4n+1 單位時間 ‖ T(n) 想想看: 假設f(n)=n2,我們是否能找到適當的常數c和n0,使得n≧n0且T(n)≦cf(n)? 我們可找到c=8, n0=1,使T(n)≦cf(n) ,故其時間複雜度Big-O為 O(n2)

時間複雜度: O (Big-O) 簡易規則:取執行時間函數T(n)中指數最高的項目,並移除係數即可 for (int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { System.out.println(i*j); } 1+(n+1)+n n×(1+(n+1)+n) n×n×1 共需 3n2+4n+1 單位時間 T(n)= 3n2+4n+1 ,取指數最高項3n2,並移除係數得 n2,因此,此程式的時間複雜度Big-O為 O(n2)

指數時間(exponential time) 常見的 Big-O 函式 如何比較兩個程式的效率哪一個好? 將兩個程式皆以 Big-O 函式表示其時間複雜度,再進行比較 常見的Bio-O函式如右: O(1) 常數時間 (constant time) O(n) 線性時間 (linear time) O(log2n) 次線性時間 (sub-linear time) O(nlog2n) 線性乘對數時間 O(n2) 平方時間(quadratic time) O(n3) 立方時間 (cubic time) O(2n) 指數時間(exponential time) best worst

常見 Big-O 函式效能比較

練習 請使用Big-O表示下列時間函數的時間複雜度 T(n) = 4n+12 T(n) = 10n+25 T(n) = 8n2+11n+18

解答 T(n) = 4n+12 = O(n),因為存在 c=5,n0=12,使得n ≧ 12後,4n+12 ≦ 5n(或 c=6,n0=6,使得n ≧ 6後,4n+12 ≦ 6n) T(n) = 10n+25 = O(n),因為存在c=11,n0=13,使得n ≧ 13後,10n+25 ≦ 11n; T(n) = 8n2+11n+18 = O(n2),因為存在c=9,n0=13,使得n ≧ 13後,8n2+11n+18 ≦ 9n2 T(n) = 6×2n+n2 = O(2n),因為存在c=7,n0=4,使得n ≧ 4後,6×2n+n2 ≦ 7×2n

解答(續) T(n) = 326 = O(1),因為存在 c=327,n0可任取,使得n ≧ n0後,326 ≦ 327×1; T(n) = 9n2+n+11 = O(n),因為找不到適當的 c 和 n0,使得n ≧ n0後,9n2+11 ≦ cn; T(n) = 100n3 = O(n4),因為存在c=16,n0=8,使得 n ≧ 8後,100n3 ≦ 16n4

時間複雜度: Ω (Omega) Omega(Ω)可視為時間複雜度的最佳表現,或稱為理論下限(Lower bound) 定義:某程式的執行時間為T(n) ,若存在兩個常數 c 和 n0,當n≧n0時,使得T(n)≧cf(n) ,則此程式的時間複雜度是Ω(f(n)) 通常Big-O用來討論演算法的時間複雜度,而Ω則是用來討論演算法的難易度

時間複雜度: Ω (Omega) 例 1:證明 T(n)=3n+2 ,可以用Ω(n)來表示 已知 f(n) = n 欲證明 T(n) ≧ c*f(n) 亦即 3n+2 ≧ c * n ∴ (3-c) * n ≧ -2 ∴ 當 c = 3,n0=1 時上式可成立 亦即c = 3,n0=1 時 T(n)= Ω(n)

時間複雜度: Ω (Omega) 例 2:某程式的執行所花費的時間函數T(n)=6n2+3n+2,請利用Ω來表示T(n)的時間複雜度 ∴ 6n2+3n+2 ≧ c * n2 ∴ (6-c) n2+3n+2 ≧ 0 ∴ 存在 c=6 ,對所有的 n ≧ 1 , 使得 6n2+3n+2 ≧ 6n2, 所以 f(n)= Ω(n2)

練習(Ω) 請用Ω表示下列時間函式 T(n) = 4n+12 T(n) = 10n+25 T(n) = 8n2+11n+18

解答 4n+12=Ω(n),因為存在c=1,n0=1,使得n1後,4n+12  n 8n2+11n+18=Ω(n2),因為存在c=1,n0=1,使得n1後,8n2+11n+18  n2 6×2n+n2=Ω(2n),因為存在c=1,n0=1,使得n1後,6×2n+n2  1×2n

時間複雜度: Theta (Θ) Theta (Θ)可視為時間複雜度的平均表現,既是上限,也是下限 定義:某程式的執行時間為T(n) ,若存大於0的正常數c1、c2和n0,讓所有n值在n≧n0時,使得c1f(n)≦T(n)≦c2f(n),則此程式的時間複雜度是Θ(f(n)) 即 f(n) 既是 T(n) 的上限,也是下限,是 T(n) 的最佳解 (Optimal solution)

時間複雜度: Theta (Θ) 例1:證明 T(n) = 3n+2 ,可以用Θ(n)表示 已知 f(n) = n 欲求 c1f(n)≦T(n)≦c2f(n) 亦即 c1n ≦ 3n+2 ≦ c2n 存在 c1=3,c2=4 當 n ≧ 1 時,滿足3n+2≧3n 當 n ≧ 2 時,滿足3n+2≦4n 結論 3n+2=Θ(n)

時間複雜度: Theta (Θ) 例2:證明T(n)=10n2+4n+6,可以用Θ(n2)表示 已知 f(n) = n2 欲求 c1f(n)≦T(n)≦c2f(n) 亦即 c1n2 ≦ 10n2+4n+6 ≦ c2n2 存在 c1=10,c2=11 當 n ≧ 1 時,滿足 10n2+4n+6 ≧10n2 當 n ≧ 6 時,滿足 10n2+4n+6 ≦11n2 結論3n+2=Θ(n2)

練習 請用Θ表示下列時間函式 4n+12 8n2+11n+18

解答 4n+12 = Θ(n),因為存在c1=1、c2=5,n0=12,使得n≧12後,1×n ≦ 4n+12 ≦ 5×n 8n2+11n+18 = Θ(n2),因為存在c1=1、c2=9,n0=13,使得n≧13後,1×n2 ≦ 8n2+11n+18 ≦ 9n2

本章節結束