N-淡江大学.ppt

演算法則淡江大學 資訊管理系侯 永 昌.tw/~ychou .tw/Prof_Hou;教科書︰R. Neapolitan and K. Naimipour, Foundations of Algorithms – Using C++ Pseudocode, Jones and Bartlett Publishers, 2004, 新月圖書代理;第一章演算法簡介(Introduction);演算法;變數的左值和右值;指標(Pointer);指標與取址符號;循序搜尋(Sequential Search);時間複雜度;二元搜尋(Binary Search);時間複雜度;時間複雜度;時間複雜度;Fibonacci polynomial(遞迴版);Fibonacci的運算次數;Fibonacci的運算次數;證明Fibonacci的運算次數 2n/2;Fibonacci polynomial (非遞迴版);時間複雜度的比較(Order);Order︰O(f (n));Order︰?(f (n));Order︰?(f (n)) ;Order︰o(f (n));時間複雜度︰O(f(n));時間複雜度︰O(f(n));時間複雜度︰O(f(n));Properties of Order;利用極限來決定運算的複雜度;利用極限來決定運算的複雜度;第二章個個擊破法(Divide-and-Conquer);Divide-and-Conquer;個個擊破法的求解步驟;二元搜尋法(Binary Search);Binary Search(遞迴版);Binary Search(非遞迴版);Binary Search的時間複雜度;合併(Merge);合併(Merge);合併(Merge);合併排序法(Merge Sort);Merge Sort;Merge;合併排序的時間複雜度;討論;快速排序法(Quick Sort);快速排序法(Quick Sort);快速排序法(Quick Sort);快速排序法(Quick Sort);快速排序法(Quick Sort);快速排序的時間複雜度;快速排序的時間複雜度(Average-case);快速排序的時間複雜度(Average-case);補充︰快速排序法(Quick Sort)-I;補充︰快速排序法(Quick Sort)-II;Matrix Multiplication;Matrix Multiplication;Matrix Multiplication;Strassen’s Matrix Multiplication;Strassen’s Matrix Multiplication;Strassen’s Matrix Multiplication;討論;大整數的運算;大整數的運算－另解;何時不適用個個擊破法;第三章動態規劃法(Dynamic Programming);Dynamic Programming;動態規劃法的求解步驟;二項式係數(Binominal Coefficient);二項式係數(Binominal Coefficient);二項式係數(Binominal Coefficient);二項式係數(Binominal Coefficient);圖形(Graph);圖形(Graph);圖形(Graph);圖形(Graph);圖形(Graph);鄰接矩陣(Adjacent Matrix);鄰接串列(Adjacent List);加權圖表示法(Weighted Graph);鄰接串列(Adjacent List);最短路徑(Shortest Path);最短路徑(Shortest Path);最短路徑(Shortest Path);最短路徑(Shortest Path);最短路徑(Floyd’s Algorithm);最短路徑(Floyd’s Algorithm);追蹤最短路徑(Floyd’s Algorithm);例︰;W;最短路徑(Floyd’s Algorithm);最佳化原則(Principle of Optimality);最佳化原則(Principle of Optimality);多矩陣乘法(Chained Matrix Multiplication);多矩陣乘法(Chained Matrix Multiplication);例︰多矩陣乘法;例︰多矩陣乘法;多矩陣乘法;多矩陣乘法的時間複雜度;追蹤多矩陣乘法的分段點;二元搜尋樹(Binary Search Tree);二元搜尋樹的建立;二元搜尋樹的建立;二元搜尋樹的建立;二元搜尋樹的建立;二元搜尋樹(Binary Search Tree);二元搜尋樹(Binary Search Tree);二元搜尋樹(Binary