Introduction.

Presentation on theme: "Introduction."— Presentation transcript:

1 Introduction

2 為何要學演算法（1/2） 排序問題（sorting）: 11, 7, 14, 1, 5, 9, 10 ↓sort
1, 5, 7, 9, 10, 11, 14  Insertion sort Quick sort …..

3 為何要學演算法（2/2） 生物科技近來相當熱門，你知道如何利用電腦來幫助解決生物上的問題嗎？你知道生物資訊嗎？
你在研究多媒體資料壓縮嗎？你知道VQ(Vector Quantization)與Voronoi diagram的關係嗎？你知道你的壓縮方法是heuristic嗎？ 如果要下棋，你知道有哪些策略可以搜尋棋步嗎？

4 演算法的目標 演算法是電腦科學研究的基礎 如果沒學過演算法，電腦科學的研究就無法深入

5 資料結構和演算法 資料結構和演算法要用程式語言來描述，才能交由電腦執行，至於要用那一種程式語言；並沒有特別規定

6 演算法定義 由有限步驟所構成的集合，可以用於解決某一個特定的問題。

7 演算法必須滿足五個條件 輸入(input)：可以由外界輸入0個、1個或多個以上的資料。 輸出(output)：至少要有1個以上的輸出。
明確性(definiteness)：每個步驟都必須是明確而不含糊的。 有限性(finiteness)：必須在有限步驟內結束。 有效性(effectiveness)：每一個步驟必須是基本的(可行的)，也就是說，即使我們僅僅具有紙和筆也可以執行這些步驟。

8 搜尋 n 陣列大小 ｘ要搜尋目標 ｊ返回值 binsrch(int A[], int n, int x, int j) {
lower = 1; upper = n; while (lower <= upper) mid = (lower + upper) / 2; if (x > A[mid]) lower = mid + 1; else if (x < A[mid]) upper = mid – 1; else { j = mid; return; } n 陣列大小 ｘ要搜尋目標 ｊ返回值 Binary search

9 Array n 陣列大小 void mul(int a[ ][ ], int b[ ][ ], int c[ ][ ], int n) {
int i, j, k, sum; for (i=0; i < n; i++) for (j=0; j < n; j++) sum = 0; for (k=0; k < n; k++) sum = sum+a[i][k]*b[k][j]; c[i][j] = sum; } n 陣列大小 矩陣相乘

10 Recursive(1/2) int fact(int n) { int x, y; x = n-1; y = fact(x);
return(n*y); } /* end fact */ 無窮回圈

11 Recursive(2/2) int fact(int n) { int x, y;
if (n == 0) // boundary condition return(1); x = n-1; y = fact(x); return(n*y); } /* end fact */ N!

12 演算法衡量 影響程式執行時間的因素，最簡單的有 機器的速度 演算法的好壞 演算法(algorithm)是一解決問題的有限步驟之程序。
演算法的好壞，必須做複雜度的分析(complexity analysis)。 分析演算法的複雜度，必須先求出程式中每一敘述的 執行次數，並加總起來，然後求出其Big-O。