《一章节基本概念》由会员分享，可在线阅读，更多相关《一章节基本概念（29页珍藏版）》请在金锄头文库上搜索。
1、第一章基本第一章基本概念念資料結構與演算法徐熊健苹汗攘讹壮壕氮炉翟稗幅撼誊摔嚎渡孕莎丈幂粮坦鳖霓霜弯郁眼皑毗虱七一章节基本概念一章节基本概念資料結構與演算法 徐熊健1目錄目錄n1.1資料結構、演算法n1.2資料結構與演算法n1.3簡單的資料結構n1.4演算法初探n1.5演算法的效率分析诧儡戮镐材根浮鄂搐桨鞘泞刷凋酉准衰赋吏改英市鼠馈攒亿锨槽慌稚妨兄一章节基本概念一章节基本概念資料結構與演算法 徐熊健21.1資料結構、演算法資料結構、演算法n資料結構資料結構(data structure): 在在電腦中有效率地存放資料，使電腦中有效率地存放資料，使其方便處理的學問；其方便處理的學問；n演算法演算
2、法(algorithm):探討解決問題的策略。探討解決問題的策略。 兩者相輔相成兩者相輔相成!况喊宣梅腰蛔悉诫拳展饶藕渍裕臻冈法磋确跟遁享迪迅悲啸吭症傀返蔡鸡一章节基本概念一章节基本概念資料結構與演算法 徐熊健31.2資料結構與演算法資料結構與演算法n n電腦處理的對象稱電腦處理的對象稱為資料資料(data)，泛指所，泛指所有輸入至電腦中，即將、正在或已經被電腦有輸入至電腦中，即將、正在或已經被電腦程式處理的符號總稱；包括了數程式處理的符號總稱；包括了數值(numerical)資料、字串資料、字串(string)資料等等，資料等等，乃至於目前多媒體乃至於目前多媒體(multimedia)軟體所
3、處理軟體所處理的影像、聲音、視訊等多媒體資料。的影像、聲音、視訊等多媒體資料。n n當這些資料集合在一起時，會因處理需求的當這些資料集合在一起時，會因處理需求的不同而存在一種或多種彼此之間的特定關係，不同而存在一種或多種彼此之間的特定關係，這些資料之間的邏輯關係，就稱這些資料之間的邏輯關係，就稱為結構結構(structure)。研究資料的邏輯關係，探討這些究資料的邏輯關係，探討這些邏輯關係在電腦中的表現邏輯關係在電腦中的表現(representation)和和處理處理(manipulation)方式，即方式，即為資料結構資料結構。五库宰纺政袋卿迪无祖织遁但扣炳逾戒逼喘教质雌笼肋砚缕靡蹿擎祈刚靳
4、一章节基本概念一章节基本概念資料結構與演算法 徐熊健41.3簡單的資料結構簡單的資料結構生活中常見的資料相互關係：生活中常見的資料相互關係：生活中常見的資料相互關係：生活中常見的資料相互關係：(1)(1)校園中有一群人；校園中有一群人；校園中有一群人；校園中有一群人；(2)(2)每個中華民國國民皆有唯一的身分證字號；每個中華民國國民皆有唯一的身分證字號；每個中華民國國民皆有唯一的身分證字號；每個中華民國國民皆有唯一的身分證字號； (3)(3)每每每每位位位位同同同同學學學學在在在在班班班班上上上上皆皆皆皆有有有有唯唯唯唯一一一一的的的的座座座座號號號號、在在在在學學學學校校校校皆皆皆皆有有有有
5、唯唯唯唯一一一一的學號；的學號；的學號；的學號；(4)(4)在大學中的科系有系別、年級別、甚至於班別；在大學中的科系有系別、年級別、甚至於班別；在大學中的科系有系別、年級別、甚至於班別；在大學中的科系有系別、年級別、甚至於班別；(5)(5)排排排排隊隊隊隊的的的的時時時時候候候候，我我我我們們們們可可可可能能能能只只只只關關關關心心心心排排排排在在在在前前前前一一一一位位位位的的的的是是是是誰誰誰誰？有時可能還在意排在自己前面的共有多少人？有時可能還在意排在自己前面的共有多少人？有時可能還在意排在自己前面的共有多少人？有時可能還在意排在自己前面的共有多少人？(6)(6)外國旅行時，各景點間是否
6、有班機直飛？外國旅行時，各景點間是否有班機直飛？外國旅行時，各景點間是否有班機直飛？外國旅行時，各景點間是否有班機直飛？(7)(7)上上上上網網網網尋尋尋尋找找找找資資資資料料料料，網網網網頁頁頁頁間間間間的的的的鏈鏈鏈鏈結結結結，將將將將網網網網頁頁頁頁連連連連結結結結成成成成複複複複雜雜雜雜的全球性的網絡的全球性的網絡的全球性的網絡的全球性的網絡(world-wideweb)(world-wideweb)。慈审淑扣揭醒辫府算狭畔疙壬忻菩呵床虎接专硷产特穷派聪淆累革悍闸差一章节基本概念一章节基本概念資料結構與演算法 徐熊健51.4演算法初探演算法初探Horowitz,SahniHorowit
7、z,Sahni和和和和MehtaMehta，給予演算法的明確定義：，給予演算法的明確定義：，給予演算法的明確定義：，給予演算法的明確定義： 演演演演算算算算法法法法是是是是一一一一組組組組可可可可完完完完成成成成特特特特定定定定工工工工作作作作的的的的指指指指令令令令集集集集合合合合，並並並並且且且且所有的演算法都需滿足下列條件：所有的演算法都需滿足下列條件：所有的演算法都需滿足下列條件：所有的演算法都需滿足下列條件：(1)(1)輸入輸入輸入輸入(input)(input)：可以有多個其甚至是沒有輸入；：可以有多個其甚至是沒有輸入；：可以有多個其甚至是沒有輸入；：可以有多個其甚至是沒有輸入；(
8、2)(2)輸出輸出輸出輸出(output)(output)：至少：至少：至少：至少產產生一個輸出；生一個輸出；生一個輸出；生一個輸出；(3)(3)明確明確明確明確(definiteness)(definiteness)：每個指令都：每個指令都：每個指令都：每個指令都清清楚明確；楚明確；楚明確；楚明確；(4)(4)有限有限有限有限(finiteness)(finiteness)：在任何情況下，如果逐步追蹤演算：在任何情況下，如果逐步追蹤演算：在任何情況下，如果逐步追蹤演算：在任何情況下，如果逐步追蹤演算法的每個指令，演算法會在有限的步驟內結束；法的每個指令，演算法會在有限的步驟內結束；法的每個指
9、令，演算法會在有限的步驟內結束；法的每個指令，演算法會在有限的步驟內結束；(5)(5)有效率有效率有效率有效率(effectiveness)(effectiveness)：原則上每個指令都需：原則上每個指令都需：原則上每個指令都需：原則上每個指令都需基本到基本到基本到基本到人只需紙和筆即可實踐之，並且每個指令的運算人只需紙和筆即可實踐之，並且每個指令的運算人只需紙和筆即可實踐之，並且每個指令的運算人只需紙和筆即可實踐之，並且每個指令的運算不止如條件不止如條件不止如條件不止如條件(3)(3)般明確而已，還必須是可實行的。般明確而已，還必須是可實行的。般明確而已，還必須是可實行的。般明確而已，還必
10、須是可實行的。号礼虏携提贬篮常隐循胯涩线行昏督胃死峰搅赛烯珍幅头岿儿列渭踌窘寅一章节基本概念一章节基本概念資料結構與演算法 徐熊健61.4.1程式撰寫流程程式撰寫流程撰寫程式解決問題流程圖問題的需求或限制問題的需求或限制思考與探索思考與探索資料結構與演算法設計資料結構與演算法設計程式撰寫程式撰寫數學証明數學証明結果輸出結果輸出驗証、測試與修善驗証、測試與修善沛员晴熏尚那籽乏麦韦敬碉斜启稍志愁糯息峻抗贿粒牡储较棚抢醛救符锚一章节基本概念一章节基本概念資料結構與演算法 徐熊健7範例範例1-2挑選排序法挑選排序法思考與探索思考與探索：欲將整數由小至大排序，可把數字小者放在欲將整數由小至大排序，可把數
11、字小者放在左邊，數字小者放在右邊，左邊，數字小者放在右邊，n n可以挑出所有資料中最小者，做可以挑出所有資料中最小者，做為左邊第一左邊第一筆資料，接著再挑出剩下資料中最小者，放筆資料，接著再挑出剩下資料中最小者，放在左邊做在左邊做為第二筆資料，依此類推，直至全第二筆資料，依此類推，直至全部資料都排列完成。部資料都排列完成。n n若所有資料共計若所有資料共計n筆，則會執行筆，則會執行n次挑出最小次挑出最小的運算，其第的運算，其第i 次的運算，即次的運算，即為挑出未排序資挑出未排序資料中最小者料中最小者，其結果做，其結果做為第第i筆資料。筆資料。懦及坐核拈诗蕴狸事宪竿喂沟倾戍猩铣刀搪腑误珠吠喇俗物
12、佛应昆贞吭县一章节基本概念一章节基本概念資料結構與演算法 徐熊健8演算法演算法1-1挑選排序法：挑選排序法：輸入：輸入：輸入：輸入：data0, data1, data2, ,data0, data1, data2, , datan-1 datan-1，共，共，共，共 n n 筆整數資料筆整數資料筆整數資料筆整數資料輸出：輸出：輸出：輸出：data0, data1, datan-1data0, data1, datan-1；其中；其中；其中；其中 若若若若ijij，則，則，則，則dataidatai datajdataj，1 1 i,ji,j n nfor (i=0; in; i+)for (
13、i=0; in; i+) dataj = dataj = 挑出挑出挑出挑出dataidatai至至至至datan-1datan-1中最小者中最小者中最小者中最小者swap(datai, dataj)swap(datai, dataj)/ / 將將將將datai datai 和和和和 dataj dataj 對調對調對調對調 侄间急步缔永谩宠纤抱饵郭花羞浪痛撑宣垛邢奶桃终迫职佐腻俐茁栏厩裔一章节基本概念一章节基本概念資料結構與演算法 徐熊健9程式程式1-1挑選排序法：挑選排序法：void SelectionSort(int data, int n)void SelectionSort(int d
14、ata, int n) int i, j;int i, j;int min, temp;int min, temp;for (i=0; in; i+)for (i=0; in; i+) min = i; min = i; for (j=i+1; jn; j+) for (j=i+1; jn; j+) if (datajdatamin) min = j; if (datajdatamin) min = j; t temp = datai;emp = datai; datai = datamin; datai = datamin; datamin = temp; datamin = temp; 脏
15、韩脯泉扔沏轰足呐烁马寺猪祖恢氮牵燃妓葛企箭躲凸苦妄疼俯遵灯殿啸一章节基本概念一章节基本概念資料結構與演算法 徐熊健10程式的驗証、測試與修繕程式的驗証、測試與修繕n n數學証明數學証明最佳的驗証；比較困難。最佳的驗証；比較困難。n n測試測試輸入大量各式資料測試之。輸入大量各式資料測試之。若此若此為提供他人的程式，還應考慮輸提供他人的程式，還應考慮輸入正確性入正確性(inputvalidation)；若資料量；若資料量非常大，則資料儲存用的陣列，宜用非常大，則資料儲存用的陣列，宜用動態配置的技巧宣告使用動態配置的技巧宣告使用翻豆誉积角疹植蝎馁铡胃楞银些砚张狗疗连果曰渊盏醚避猎剁著褪葵烦递一章节
16、基本概念一章节基本概念資料結構與演算法 徐熊健111.4.2遞迴演算法遞迴演算法n n直直直直接接接接遞遞遞遞迴迴迴迴 (direct(directrecursion)recursion)：當當當當程程程程序序序序執執執執行行行行完完完完成成成成前前前前呼呼呼呼叫叫叫叫了自己這個程序。了自己這個程序。了自己這個程序。了自己這個程序。n n間間間間接接接接遞遞遞遞迴迴迴迴 (indirect(indirectrecursion)recursion)：在在在在程程程程序序序序執執執執行行行行完完完完成成成成前前前前呼呼呼呼叫了其叫了其叫了其叫了其它它會再度引用到自己的程序。會再度引用到自己的程序。
17、會再度引用到自己的程序。會再度引用到自己的程序。n n在在在在設設設設計計計計遞遞遞遞迴迴迴迴程程程程式式式式時時時時，切切切切記記記記終終終終結結結結條條條條件件件件 (termination(terminationcondition)condition)的設立，否則易造形成無窮迴圈的設立，否則易造形成無窮迴圈的設立，否則易造形成無窮迴圈的設立，否則易造形成無窮迴圈 。程序呼叫時流程的轉換 SS(int data,int n)void SS(int data,int n)劳捶翅力佛俗勉泛充抠旬奎幸计柬嚏补轻俏朵贯向哲腔舔既恋腹朝林茎兔一章节基本概念一章节基本概念資料結構與演算法 徐熊健12程
18、式程式1-2計算階乘計算階乘階乘的計算即可用遞迴的階乘的計算即可用遞迴的概念詮釋，請看：念詮釋，請看：n!=n (n-1)!於是可以寫一個計算階乘的程序於是可以寫一個計算階乘的程序X(int n)，它接受傳入的整數接受傳入的整數n，傳回，傳回n*X(n-1)int X(int n)if (n = 1) return 1;return n*X(n-1);爹姆敌速培警疽北眨耸幕拣本巧辟匠丈烃绰冻枫予咬灾锤闪窘因揉讽愿迄一章节基本概念一章节基本概念資料結構與演算法 徐熊健13程式程式1-3產生排列生排列void perm (char c, int k, int n) void perm (char
19、c, int k, int n) / / 產生產生產生產生 ck,.,cn-1 ck,.,cn-1 的所有排列的所有排列的所有排列的所有排列if (k = n-1) /if (k = n-1) /終結條件成立時輸出此項排列終結條件成立時輸出此項排列終結條件成立時輸出此項排列終結條件成立時輸出此項排列 for (int i = 0; i n; i+) for (int i = 0; i n; i+) cout ci ; cout ci ;cout endl; cout endl; else else / / 讓讓讓讓ckck固定不動，求固定不動，求固定不動，求固定不動，求 perm(c, k+1
20、, n)perm(c, k+1, n) for (i=k; in; i+)for (i=k; in; i+)/讓讓讓讓ckcn-1ckcn-1輪流當輪流當輪流當輪流當ckck char temp=ck; ck=ci; char temp=ck; ck=ci; ci=temp; ci=temp; perm(c,k+1,n); perm(c,k+1,n);/產生產生產生產生ak+1,ak+1, ,an-1,an-1的所有排列的所有排列的所有排列的所有排列 temp=ck; ck=ci; ci=temp; temp=ck; ck=ci; ci=temp;/還原原字元順序還原原字元順序還原原字元順序還
21、原原字元順序 ABCDABDCACBDACDBADCBADBCBACDBADCBCADBCDABDCABDACCBADCBDACABDCADBCDABCDBADBCADBACDCBADCABDACBDABC桨各啸仓游弘涝作坤茧筑演丘旧独基而菱隐围乏麦宝搂说矿砧拙街禁瘦烙一章节基本概念一章节基本概念資料結構與演算法 徐熊健141.5演算法的效率分析演算法的效率分析n n什什麼是有效率的演算法？電腦學家是有效率的演算法？電腦學家為此衡量此衡量準則提供了客觀的標準準則提供了客觀的標準分析演算法的執行分析演算法的執行時間和記憶體需求。以時間和記憶體需求。以時間複雜度時間複雜度或或空間複空間複雜度雜度來
22、討論演算法的效率來討論演算法的效率n n解決相同的問題，演算法所用的時間複雜度解決相同的問題，演算法所用的時間複雜度和空間複雜度愈少愈好。和空間複雜度愈少愈好。n n時時間間複複雜雜度度(timecomplexity)：一一個個程程式式或或演算法所需的執行時間；演算法所需的執行時間；n n空空間間複複雜雜度度(spacecomplexity)：一一個個程程式式或或演算法所需的記憶體空間。演算法所需的記憶體空間。房赏醇慈焊弱披茄拷往涨捌知净熟坑树隋窿智滁揉胆厦钻敲蕴顷级模诊瓮一章节基本概念一章节基本概念資料結構與演算法 徐熊健151.5.1演算法的執行次數演算法的執行次數程式程式程式程式1-41
23、-4陣列元素加總陣列元素加總陣列元素加總陣列元素加總int Sum(int data,int n) int Sum(int data,int n) int summation=0;int summation=0;for (int i=0; in; i+) summation += for (int i=0; in; i+) summation += datai;datai;return summation;return summation; 程式程式程式程式1-51-5陣列元素加總並計算所有指令執行的次數陣列元素加總並計算所有指令執行的次數陣列元素加總並計算所有指令執行的次數陣列元素加總並計算
24、所有指令執行的次數int count = 0;int count = 0;/ / 全域變數宣告全域變數宣告全域變數宣告全域變數宣告count+;count+;/ / 計算宣告計算宣告計算宣告計算宣告 int int 指令的執行指令的執行指令的執行指令的執行int Sum(int data,int n) int Sum(int data,int n) int summation=0;int summation=0;count+;count+;/ / 計算宣告計算宣告計算宣告計算宣告 int int 指令的執行指令的執行指令的執行指令的執行for (int i=0; in; i+) for (in
25、t i=0; in; i+) count+;count+;/ / 計算計算計算計算 for for 指令的執行次數指令的執行次數指令的執行次數指令的執行次數summation += datai;summation += datai;count+;count+;/ / 計算計算計算計算 = = 指令的執行次數指令的執行次數指令的執行次數指令的執行次數; ; count+;count+;/ / 計算最後一次計算最後一次計算最後一次計算最後一次 for for 指令的執行指令的執行指令的執行指令的執行count+;count+;/ / 計算計算計算計算 return return 指令的執行指令的執
26、行指令的執行指令的執行return summation;return summation; 程式程式程式程式1-41-4將傳入整數陣將傳入整數陣將傳入整數陣將傳入整數陣列列列列datadata中的中的中的中的n n個元素個元素個元素個元素 (data0datan-1)(data0datan-1)，總加至整數變數總加至整數變數總加至整數變數總加至整數變數summationsummation中傳出。中傳出。中傳出。中傳出。 在程式在程式在程式在程式1-41-4中中中中加入一全域加入一全域加入一全域加入一全域變數變數變數變數countcount，來加總所有來加總所有來加總所有來加總所有指令執行的指令
27、執行的指令執行的指令執行的次數；新的次數；新的次數；新的次數；新的程式將如程程式將如程程式將如程程式將如程式式式式1-51-5所示。所示。所示。所示。 咬痕或撑娇饮欣后件碱梗刹减莱螟霉腑效驯倡筒白溶铸州跳霹诡力荒卖匀一章节基本概念一章节基本概念資料結構與演算法 徐熊健161.5.1演算法的執行次數演算法的執行次數(續續)程式程式程式程式1-61-6計算計算計算計算陣列元素加總所有指令執行的次數陣列元素加總所有指令執行的次數陣列元素加總所有指令執行的次數陣列元素加總所有指令執行的次數count+;count+;int Sum(int data,int n) int Sum(int data,in
28、t n) count+;count+;/ / 計算宣告計算宣告計算宣告計算宣告 int int 指令的執指令的執指令的執指令的執行行行行for (int i=0; in; i+) for (int i=0; in7 7 後後後後 演算法演算法演算法演算法AA比比比比BB好好好好哦颓颊宪质观呐类贩还很傅咳镀您菇筋羡虑缠许驳胸贤铂骄褒挣币磅科耽一章节基本概念一章节基本概念資料結構與演算法 徐熊健18用大用大O表示時間複雜度表示時間複雜度f(n)指的是演算法的執行時間（步驟）指的是演算法的執行時間（步驟），我們希望能找到，我們希望能找到g(n)；只要在；只要在n n0後，後，c g(n)一定會大於或
29、等於一定會大於或等於f(n)，那那麼就可以用就可以用O(g(n)來表示來表示f(n)。定義：定義：f(n)=O(g(n)若且唯若存在兩若且唯若存在兩個正整數個正整數c和和n0，當，當n n0時，時，f(n) c g(n)。根横请搁读潦驱快赦脚萨宦吁蛆堪湃摔绑吉夜灾颠判讥荡衡叉篮肾锈负尽一章节基本概念一章节基本概念資料結構與演算法 徐熊健19請注意在上圖中，當請注意在上圖中，當n 14(=n0)之後，之後，c g(n)一定會大於或等於一定會大於或等於f(n)（5n2 4n2+174），），所以所以O(n2)足以代表足以代表4n2+174。谜卿腿势军聪娇屋良泊耗瓜盒省毯香祷悄砷乌郑凡晌惹淑聂爹揩建
30、练芜霜一章节基本概念一章节基本概念資料結構與演算法 徐熊健20範例範例1-7a)4n+12=O(n)，因，因為存在存在c=5，n0=12，使，使得得n 12後，後，4n+12 5n（或（或c=6，n0=6，使得，使得n 6後，後，4n+12 6n）；）；b)10n+25=O(n)，因，因為存在存在c=11，n0=13，使得使得n 13後，後，10n+25 11n；c)8n2+11n+18=O(n2)，因，因為存在存在c=9，n0=13，使得，使得n 13後，後，8n2+11n+18 9n2；d)62n+n2=O(2n)，因，因為存在存在c=7，n0=4，使得使得n 4後，後，62n+n2 72
31、n；孝握盅靡楔陇宪信窃胁羽均涉骨急草脯乙舞驰顽育郝芒橙崔卤贷熟远酣篙一章节基本概念一章节基本概念資料結構與演算法 徐熊健21範例範例1-7(續續)e)326=O(1)，因，因為存在存在c=327，n0可任可任取，使得取，使得n n0後，後，326 3271；f)9n2+n+11 O(n)，因，因為找不到適當的找不到適當的c和和n0，使得，使得n n0後，後，9n2+11 cn；g)100n3=O(n4)，因，因為存在存在c=16，n0=8，使得，使得n 8後，後，100n3 16n4。放茎团班乃狗袱译愿近熙遣晕闭接医晶案凑嘶宛距水约罐窖姐炯邪蹈剿浸一章节基本概念一章节基本概念資料結構與演算法
32、徐熊健22以大以大O表示法分辨演算法的優劣表示法分辨演算法的優劣O(1)稱稱為常數時間，即不論演法的步驟須需常數時間，即不論演法的步驟須需要多少指令，只要不像迴圈般重複執行，要多少指令，只要不像迴圈般重複執行，皆視皆視為常數時間；常數時間；O(n)稱稱為線性時間，取其執行步驟的增加線性時間，取其執行步驟的增加趨勢與趨勢與n的增加趨勢的增加趨勢為線性關係之意；線性關係之意；O(n2)為平方時間；依此類推，而平方時間；依此類推，而O(2n)則稱則稱為指數時間。指數時間。如此一來，我們會說如此一來，我們會說O(logn)的演算法比的演算法比O(n)來得有效率，來得有效率，O(n)比比O(n2)來得有
33、效率來得有效率。帮堰渭深虏庐峙撕旱剪财叮磅淫佯睫哦稚捻轨霞坊帖肮缔抓卫勤薯黍泪棕一章节基本概念一章节基本概念資料結構與演算法 徐熊健23大大O表示函數的優劣順序表示函數的優劣順序為：O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) O(2n)。腮迎辟柿匹个捧瞄畦监防州啼龙寥战哪宠宏很座栈檬西嗣素掂瞎指谰朵辕一章节基本概念一章节基本概念資料結構與演算法 徐熊健24大大O的符號是的符號是為了方便討論演算法的了方便討論演算法的複雜度而設計引用的；複雜度而設計引用的；則不然，則不然，它是是為了方便討論問題的難易程度而了方便討論問題的難易程度而設計引用的。其定義如下，假設設計
34、引用的。其定義如下，假設f,g 0：定義：定義：f (n)= (g (n)若且唯若若且唯若存在兩個正整數存在兩個正整數c和和n0，當，當n n0時，時，f (n) c g (n)。用用表示問題的難易程度表示問題的難易程度逮赁疗僳硒豢纲朱帧氛乐剐絮左烽莉合斗跨将粤铲纳娇录刺雁吩矽延篱窿一章节基本概念一章节基本概念資料結構與演算法 徐熊健25範例範例1-8(a)4n+12=(n)，因因為存存在在c=1，n0=1，使使得得n 1後，後，4n+12 n；(b)10n+25=(n)，因因為存存在在c=10，n0=1，使得使得n 1後，後，10n+25 10n；(c) 8n2+11n+18 = (n2)，
35、因因為存存在在c=1，n0=1，使得，使得n 1後，後，8n2+11n+18 n2；(d)62n+n2=(2n)，因因為存存在在c=1，n0=1，使得使得n 1後，後，62n+n2 12n；秧儒婪蜕窒宠隔讥淤胁壹映陕香赌开颊瘤胶阳杂澈癸块馁猪异卧杖厂陇贺一章节基本概念一章节基本概念資料結構與演算法 徐熊健26範例範例1-8(續續)(e)326=(1)，因因為存存在在c=1，n0可可任任取取，使得使得n n0後，後，326 11；(f)9n2+n+11 (n3)，因因為找找不不到到適適當當的的c和和n0，使使得得n n0後後，9n2+11 cn3；(g)100n3=(n2)=(n)=(1)，因，
36、因為存在存在c=1，n0=，使得，使得n 1後，後，100n3 n2 n 1。戴蜡墟碾免舜酷岛忠沪土额琼稀菌潞畴吨壁躇音成渍一抄拒榴黎巫啤中涝一章节基本概念一章节基本概念資料結構與演算法 徐熊健27最佳最佳(optimal)演算法演算法定義：定義：f (n)=(g (n)若且唯若存在若且唯若存在參個正整數參個正整數c1、c2和和n0，當，當n n0時，時，c1 g (n) f (n) c2 g (n)。如果如果既可找到演算法可找到演算法A 來解決問題來解決問題P，時間複，時間複雜度雜度為O(g(n)，且又能証明解決問題，且又能証明解決問題P 的最少的最少代價亦代價亦為(g(n)；則欲解決；則欲
37、解決P的時間，至多要的時間，至多要O(g(n)，至少，至少為(g(n)；不可能比多於；不可能比多於O(g(n)，也不可能少於，也不可能少於(g(n)（最多或最少都（最多或最少都只是只是g(n)的常數倍），則演算法的常數倍），則演算法A是解決問題是解決問題P的最佳的最佳(optimal)演算法。演算法。那蹭龄来狮失幕茁妻卖墅爸稼率与谁应莲口予姻翔豹蔽滞骤颊皆课里裹俭一章节基本概念一章节基本概念資料結構與演算法 徐熊健28範例範例1-9a)4n+12 =(n)，因因為存存在在c1=1、 c2=5， n0=12， 使使 得得n 12後後 ， 1 n 4n+12 5 n；b)8n2+11n+18=(n2)，因，因為存存在在c1=1、c2=9，n0=13，使得，使得n 13後，後，1 n2 8n2+11n+18 9 n2。恳匪洋做镶辩逗拇讫蒙样欣条条袱聂泅恳兆扫谩棕刨楷殖汗敏笔田旺订捂一章节基本概念一章节基本概念資料結構與演算法 徐熊健29
