《可視化計(jì)算》第2章算法設(shè)計(jì)與可視化(A)

1、可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A) 第2章 算法設(shè)計(jì)與可視化 PART A 可視化計(jì)算 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)2 學(xué)習(xí)目標(biāo) 程序與算法有哪些異同? 算法有哪些基本特性？ 算法的效率如何度量？ RAPTOR如何實(shí)現(xiàn)計(jì)算可視化？ 如何為算法設(shè)計(jì)做準(zhǔn)備？ 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)3 算法定義 算法是在有限步驟內(nèi)求解某一問題所使用算法是在有限步驟內(nèi)求解某一問題所使用 的一組定義明確的規(guī)則。的一組定義明確的規(guī)則。 通俗來說，就是通過計(jì)算來解決問題的過程，通俗來說，就是通過計(jì)算來解決問題的過程， 在這個(gè)過程中，無論是形成解題思路還是編寫在這個(gè)過程中，無論是形成解題思

2、路還是編寫 程序，都是在實(shí)施某種算法程序，都是在實(shí)施某種算法 不同的是：前者是推理實(shí)現(xiàn)的算法，后者是操不同的是：前者是推理實(shí)現(xiàn)的算法，后者是操 作實(shí)現(xiàn)的算法作實(shí)現(xiàn)的算法 所以，程序是使用計(jì)算機(jī)實(shí)現(xiàn)的算法；而算法所以，程序是使用計(jì)算機(jī)實(shí)現(xiàn)的算法；而算法 則不一定需要有計(jì)算機(jī)才能實(shí)現(xiàn)則不一定需要有計(jì)算機(jī)才能實(shí)現(xiàn) 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)4 算法的特性 算法具有五個(gè)基本特性： 輸入（具有零個(gè)或多個(gè)輸入） 輸出（一或多個(gè)輸出） 有窮性（自動(dòng)結(jié)束而不會(huì)出現(xiàn)無限循環(huán)） 確定性（每一步驟的含義，不會(huì)出現(xiàn)二義性） 可行性（能夠通過執(zhí)行有限次數(shù)完成） 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)5

3、算法設(shè)計(jì)的要求 正確性正確性 可讀性可讀性 健壯性健壯性 時(shí)間效率高時(shí)間效率高 存儲(chǔ)量需求低存儲(chǔ)量需求低 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)6 正確性正確性的層次的層次 算法程序沒有語法錯(cuò)誤; 算法程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)能夠產(chǎn)生滿 足要求的輸出結(jié)果; 算法程序?qū)τ诜欠ǖ妮斎霐?shù)據(jù)能夠得出滿 足規(guī)格說明的結(jié)果; 算法程序?qū)τ诰倪x擇的，甚至刁難的測(cè) 試數(shù)據(jù)都有滿足要求的輸出結(jié)果。 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)7 可讀性可讀性 為了便于閱讀、理解和交流，可讀性要素： 增加算法文件名、子圖、子程序、算法樣本數(shù) 據(jù)文件名的可讀性； 在算法語句中增加注釋語句，說明重要變量、 決策語句的用

4、途； 將算法有關(guān)的文檔整理在一個(gè)目錄中 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)8 健壯性健壯性 能對(duì)輸入數(shù)據(jù)不合法的情況做合適的處理 比如輸入的時(shí)間或者距離不應(yīng)該是負(fù)數(shù) 算法的健壯性表現(xiàn)在當(dāng)輸入數(shù)據(jù)不合法時(shí)，算 法也能做出相關(guān)處理，而不是產(chǎn)生異?；驘o法 解釋的結(jié)果 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)9 時(shí)間效率高和存儲(chǔ)量需求低時(shí)間效率高和存儲(chǔ)量需求低 對(duì)于同一個(gè)問題，如果有多個(gè)算法能夠達(dá) 到同樣的問題解決標(biāo)準(zhǔn)，執(zhí)行時(shí)間最短的 算法效率最高 存儲(chǔ)量需求指的是算法在執(zhí)行過程中需要 的最大存儲(chǔ)空間，主要指算法程序運(yùn)行時(shí) 所占用的內(nèi)存或外部硬盤存儲(chǔ)空間，越少 越好 可視化計(jì)算第2章 算法設(shè)計(jì)與

5、可視化(A)10 算法效率的度量 一個(gè)用高級(jí)程序語言編寫的程序在計(jì)算機(jī) 上運(yùn)行時(shí)所消耗的時(shí)間取決于下列因素： 編譯產(chǎn)生的代碼質(zhì)量； 算法采用的策略、方法； 問題的輸入規(guī)模； 機(jī)器執(zhí)行指令的速度。 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)11 一個(gè)完全數(shù)算法 在RAPTOR中，一個(gè)算法的 執(zhí)行語句的次數(shù)，可以通 過估算，統(tǒng)計(jì)出來 RAPTOR自身，也可以統(tǒng)計(jì) 計(jì)算過程中，含有表達(dá)式 的語句的執(zhí)行次數(shù) （1014070 symbols evaluated） 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)12 測(cè)定運(yùn)行時(shí)間的可靠方法 RAPTOR計(jì)算對(duì)運(yùn)行時(shí)間有消耗的基本符號(hào) 的執(zhí)行次數(shù) 算法運(yùn)行時(shí)間與這

6、個(gè)計(jì)數(shù)值成正比 這個(gè)執(zhí)行次數(shù)可以與估算的次數(shù)相互印證 和比對(duì) 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)13 算法的效率分析的客觀性 算法的效率分析可以獨(dú)立于所實(shí)現(xiàn)的語言 和計(jì)算機(jī) 所關(guān)心的是算法設(shè)計(jì)中所考慮的策略 甚至可以忽略數(shù)據(jù)的輸入與輸出等次要環(huán) 節(jié)上的時(shí)間花費(fèi)，關(guān)注主要算法邏輯上的 設(shè)計(jì)思路與合理性 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)14 算法復(fù)雜度算法復(fù)雜度 判斷一個(gè)算法的優(yōu)劣，只通過少量的數(shù)據(jù) 是不能做出準(zhǔn)確判斷的 根據(jù)算法案例的分析和實(shí)驗(yàn)可以發(fā)現(xiàn)，通 過比對(duì)針對(duì)同一問題的幾個(gè)不同算法的關(guān) 鍵執(zhí)行次數(shù)函數(shù)的漸近增長(zhǎng)性，基本就可 以分析出： 某個(gè)算法，隨著n的增大，它會(huì)越來越優(yōu)于

7、另一 算法 或者越來越遜色于另一算法 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)15 函數(shù)的漸近增長(zhǎng) 常見的算法求解問題的輸入量被稱為問題 的規(guī)模(Size)，一般用一個(gè)整數(shù)表示 搜索問題的規(guī)模是線性表或集合的大小 矩陣乘積問題的規(guī)模是矩陣的階數(shù) 而圖論問題的規(guī)模則是圖中的頂點(diǎn)數(shù)或邊數(shù) 指給定兩個(gè)函數(shù)f（n）和g（n） 如果存在一個(gè)整數(shù)N，當(dāng)n N時(shí)，所有的f（n）都大 于g（n），那么，我們說f（n）的漸近增長(zhǎng)快于g（n） 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)16 算法時(shí)間復(fù)雜度 進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù)T（n） 是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T（n） 隨n的變化情況并確定T（n

8、）的數(shù)量級(jí) 算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量 度，記作： T（n）= O(f(n) 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)17 常見算法復(fù)雜度 執(zhí)行次數(shù)的函數(shù)執(zhí)行次數(shù)的函數(shù)階階非正式術(shù)語非正式術(shù)語 12O(1)常數(shù)階 2n+3O(n)線形階 3n2+2n+1O(n2)平方階 5log2n+20O(logn)對(duì)數(shù)階 6n3+2n2+3n=4O(n3)立方階 2nO(2n)指數(shù)階 這樣用大寫O( )來體現(xiàn)算法時(shí)間復(fù)雜度的記法， 稱之為大O記法(Big O notation)。 一般情況下，隨著n的增大，T(n)增長(zhǎng)最慢的算 法為最優(yōu)算法 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)18 可行的算

9、法復(fù)雜度 常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大 依次是： O(1) O(logn) O(n) O(nO(1) O(logn) O(n) O(n2 2) O(n) O(n3 3) O(2) O(2n n)O(n!)O(n)O(n!)O(nn n) ) 算法設(shè)計(jì)中，O(n) 、O(n2) 等最為常見 O(1) 、O(logn) 則是設(shè)計(jì)優(yōu)良的算法 O(n3)等過大的n都會(huì)使得算法的實(shí)現(xiàn)變得不現(xiàn)實(shí) O(2n)和O(n!)等除非是很小的n值，若n=100，try it？ 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)19 算法比較 假設(shè)算法需要N個(gè)數(shù)據(jù)值來處理。 如果每個(gè)操作執(zhí)行時(shí)間為1s，運(yùn)行100個(gè) 數(shù)

10、據(jù)值的算法用多少微秒 1s（微秒）= 1百萬分之一秒 算法的計(jì)算次數(shù)為： 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)20 算法比較 在已知的宇宙中的質(zhì)子數(shù)在已知的宇宙中的質(zhì)子數(shù)1079 宇宙大爆炸以來的微秒數(shù)宇宙大爆炸以來的微秒數(shù)1024 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)21 推算大O階方法 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù) 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高 階項(xiàng) 如果最高階項(xiàng)存在并且不是1，則去除與這 個(gè)項(xiàng)相乘的常數(shù)。得到的結(jié)果就是大O階 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)22 常數(shù)階常數(shù)階 一般指順序結(jié)構(gòu)算法的時(shí)間復(fù)雜度 注意：不管順序結(jié)構(gòu)算法的語句有多長(zhǎng)，我們 都記作

11、O(1) 對(duì)于分支結(jié)構(gòu)而言，無論決策語句判斷的 結(jié)果是真，還是假，執(zhí)行的次數(shù)都是恒定 的，所以單純的分支結(jié)構(gòu)，其時(shí)間復(fù)雜度 也是O(1) 例如，某些哈希查找過程是一個(gè)常數(shù)階的運(yùn)算 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)23 常數(shù)階常數(shù)階圖示圖示 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)24 線性階線性階 線性階一般來自循環(huán)結(jié)構(gòu)。要確定某個(gè)算 法的階次，常常需要確定某個(gè)特定語句或 某個(gè)語句集運(yùn)行的次數(shù) 例如，對(duì)于無序數(shù)列進(jìn)行的關(guān)鍵字查找是一個(gè) 線性階的過程，時(shí)間復(fù)雜性與數(shù)列的長(zhǎng)度成正 比 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)25 線性階線性階圖示圖示 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A

12、)26 平方階平方階 通常來自循環(huán)嵌套，它的內(nèi)循環(huán)在前面已 經(jīng)分析過，時(shí)間復(fù)雜度為O(n) 而對(duì)于外層的循環(huán)，不過是對(duì)內(nèi)部的時(shí)間復(fù)雜 度為O(n)的語句，再循環(huán)n次。所以這段代碼的 時(shí)間復(fù)雜度為O(n2) 如果外循環(huán)的循環(huán)次數(shù)改為了m，時(shí)間復(fù)雜度 就變?yōu)镺(mn) 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)27 平方階平方階圖示圖示 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)28 對(duì)數(shù)階對(duì)數(shù)階 對(duì)數(shù)階的算法往往來自一些分治算法，例 如，折半查找，每查一次，所求解的空間 就會(huì)減少一半 而這些算法往往與有效地利用遞歸有關(guān) 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)29 對(duì)數(shù)階對(duì)數(shù)階圖示圖示 可視化計(jì)算第

13、2章 算法設(shè)計(jì)與可視化(A)30 空間復(fù)雜性的大空間復(fù)雜性的大O O階階 空間復(fù)雜度(Space Complexity)是對(duì)一個(gè) 算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間臨時(shí)占用存儲(chǔ)空間大小 的量度。 注意：該空間與輸入數(shù)據(jù)的規(guī)模沒有關(guān)系 有的算法只需要占用少量的臨時(shí)工作單元，而 且不隨問題規(guī)模的大小而改變； 有的算法需要占用的臨時(shí)工作單元數(shù)與解決問 題的規(guī)模n有關(guān)，它隨著n的增大而增大 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)31 空間復(fù)雜性空間復(fù)雜性的參考案例的參考案例 一些排序方法，如快速排序的數(shù)據(jù)本身在 原地不動(dòng)（in-place），運(yùn)行該算法要為 遞歸程序執(zhí)行過程所需堆棧提供輔助空間， 所以

14、是O (logn) 歸并排序和基數(shù)排序需要建立新的數(shù)組來 存放排序后的數(shù)據(jù)，所需輔助空間較多， 為O(n) 在動(dòng)態(tài)規(guī)劃算法中，需要保存大量的算例 結(jié)果，所以其空間復(fù)雜性O(shè)(n2) 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)32 計(jì)算的可視化問題 如果按一般方法學(xué)習(xí)算法設(shè)計(jì)的歷程，一 般需要經(jīng)歷程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、離散數(shù) 學(xué)等課程的鋪墊 引入可視化的程序設(shè)計(jì)環(huán)境，其目標(biāo)則是 通過縮短現(xiàn)實(shí)世界中的行為與程序設(shè)計(jì)之 間的概念距離來減少學(xué)習(xí)上的認(rèn)知負(fù)擔(dān) 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)33 可視化計(jì)算 設(shè)計(jì)可視化（用連接基本圖形符號(hào)來創(chuàng)建 算法） 運(yùn)行可視化（可以選擇單步執(zhí)行或以連續(xù) 執(zhí)行的模式

15、、可以直觀地顯示當(dāng)前執(zhí)行符 號(hào)（語句）所在的位置，以及所有變量的 內(nèi)容） 結(jié)果可視化（基于Ada Graph的簡(jiǎn)單圖形庫， 所求解的問題的呈現(xiàn)和計(jì)算的結(jié)果，也是 可以是可視化的） 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)34 設(shè)計(jì)可視化 在編輯子程序調(diào) 用語句時(shí)， RAPTOR會(huì)自動(dòng)提 示已經(jīng)存在的子 程序的名稱 流程圖是完全可 視化的算法設(shè)計(jì) 工具 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)35 運(yùn)行可視化 在執(zhí)行過程中，目 前正在執(zhí)行的符號(hào) 語句顯示為綠色 所有的變量的狀態(tài) 顯示在屏幕左下角 的窗口中 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)36 調(diào)試方法 在運(yùn)行程序之前，用戶可使用鼠標(biāo)右鍵

16、單 擊任何語句，調(diào)出菜單選擇“Toggle Breakpoint”選項(xiàng)，設(shè)置程序運(yùn)行的斷點(diǎn) 可以按“F10”鍵，單步執(zhí)行語句 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)37 結(jié)果可視化 通過主控制臺(tái)（Master Console）輸出文 字性的計(jì)算結(jié)果和表達(dá)式運(yùn)行計(jì)數(shù)值 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)38 結(jié)果可視化 一些計(jì)算問題和結(jié)果，如迷宮、棋盤甚至 三維立體圖形都可以通過圖形界面輸出 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)39 RAPTOR與流程圖規(guī)范 由于RAPTOR設(shè)計(jì)考慮了程序設(shè)計(jì)初學(xué)者的 因素，一些特殊設(shè)計(jì)與傳統(tǒng)的流程圖有差 異 所以： RAPTOR 流程圖 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)40 認(rèn)識(shí)RAPTOR 流程圖 了解和認(rèn)識(shí)正式的流程圖規(guī)范，以便在書 面應(yīng)用中不至于出現(xiàn)與標(biāo)準(zhǔn)沖突的問題 了解RAPTOR的特殊性，以便借鑒來從其他 文獻(xiàn)的流程圖算法，進(jìn)行比對(duì)和移植 深入了解RAPTOR以后，可以方便的從其他 高級(jí)語言編制的算法中，進(jìn)行移植和使用 可視化方法驗(yàn)證算法 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)41 RAPTOR與流程圖規(guī)范的差異 RAPTOR使用的流程圖符號(hào)較規(guī)范中的少且 有差異； 可視化計(jì)算第2章 算法設(shè)計(jì)與可視化(A)42 RAPTOR與流程圖規(guī)范的差異 RAPTOR流程 圖中循環(huán)語 句的決策出 口