第 1 章　基本觀念

假設我們要發展一個可以將一組 $n$ 個整數排序的程式，$n \ge 1$。下列是一個簡單的解法：

雖然這個敘述足以描述排序問題，它並不是一個演算法，因它還留有數個沒有回答的問題：它沒有告知原始的整數儲存在何處、以何種方式儲存，以及結果應儲存在何處。我們可假設整數儲存在一個陣列 list 中，使得第 $i$ 個整數存放在 list[i] 內，且 $0 \le i \lt n$。

for (i = 0; i < n; i++) {
  Examine list[i] to list[n-1] and suppose that the
  smallest integer is at list[min];

  Interchange list[i] and list[min];
}

程式 1.1：Selection sort 演算法（部份以 C 語言，部份以英文編寫）

要將程式 1.1 轉變成真正的 C 程式，仍然需要清楚地定義兩個子任務：找到最小的整數與將它和 list[i] 交換。後者可用一個函數（程式 1.2）或一個巨集來解決。

void swap(int *x, int *y)
/* both parameters are pointers to ints */
{
   int temp = *x;   /* declares temp as an int and assigns
                       to it the contents of what x points to */
   *x = *y;         /* stores what y points to into the location
                       where x points */
   *y = temp;       /* places the contents of temp in location
                       pointed to by y */
}

程式 1.2：swap 函數

#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))

巨集版本 —— 函數的程式碼比巨集容易閱讀，但巨集可用於任何資料型態。

#include <stdio.h>
#include <math.h>
#define MAX_SIZE 101
#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))
void sort(int [],int);   /* selection sort */
void main(void)
{
   int i,n;
   int list[MAX_SIZE];
   printf("Enter the number of numbers to generate: ");
   scanf("%d",&n);
   if( n < 1 || n > MAX_SIZE) {
     fprintf(stderr, "Improper value of n\n");
     exit(1);
   }
   for (i = 0; i < n; i++) {/*randomly generate numbers*/
     list[i] = rand() % 1000;
     printf("%d  ",list[i]);
   }
   sort(list,n);
   printf("\n Sorted array:\n ");
   for (i = 0; i < n; i++) /* print out sorted numbers */
     printf("%d  ",list[i]);
   printf("\n");
}
void sort(int list[],int n)
{
   int i, j, min, temp;
   for (i = 0; i < n-1; i++)  {
     min = i;
     for (j = i+1; j < n; j++)
       if (list[j] < list[min])
         min = j;
     SWAP(list[i],list[min],temp);
   }
}

程式 1.3：Selection sort 完整程式

假設有 $n$ 個不同的整數，$n \ge 1$，已經排序並儲存在陣列 list 中，亦即 $\texttt{list[0]} \le \texttt{list[1]} \le \cdots \le \texttt{list[n-1]}$。我們必須指出整數 searchnum 是否在此串列中；如果它在，傳回一個索引 $i$ 使得 list[i] = searchnum；如果不在，傳回 $-1$。

令 left 和 right 分別代表所要搜尋的串列之左端和右端。一開始設定 left = 0、right = n-1。令 middle = (left+right)/2 為串列的中央位置。將 list[middle] 和 searchnum 相互比較，可得下列三種結果之一：

1. searchnum < list[middle]：若 searchnum 在串列中，它必在 $0$ 與 middle-1 之間。因此將 right 設定為 middle-1。
2. searchnum == list[middle]：傳回 middle。
3. searchnum > list[middle]：若 searchnum 在串列中，它必在 middle+1 與 n-1 之間。因此將 left 設定為 middle+1。

while (there are more integers to check ) {
  middle = (left + right) / 2;
  if (searchnum < list[middle])
    right = middle - 1;
  else if (searchnum == list[middle])
         return middle;
       else left = middle + 1;
}

程式 1.4：搜尋一個已排序的串列

比較的工作可藉一個函數或一個巨集來達成。我們採用 C 函數庫的規則：第一個數值小於第二個 → 傳回負值 $(-1)$；相等 → 傳回 $0$；大於 → 傳回正值 $(+1)$。

int compare(int x, int y)
{
/* compare x and y, return -1 for less than, 0 for equal,
1 for greater */
   if (x < y) return -1;
   else if (x == y) return 0;
        else return 1;
}

程式 1.5：比較兩個整數值

#define COMPARE(x,y) (((x) < (y)) ? -1: ((x) == (y))? 0: 1)

巨集版本 —— 本書採用巨集，因為它適用於任何資料型態。

int binsearch(int list[], int searchnum, int left,
                                          int right)
{
/* search list[0] <= list[1] <= ... <= list[n-1] for
searchnum. Return its position if found. Otherwise
return -1 */
   int  middle;
   while (left <= right)  {
     middle = (left + right)/2;
     switch (COMPARE(list[middle], searchnum)) {
       case -1: left = middle + 1;
                break;
       case  0: return middle;
       case  1: right = middle - 1;
     }
   }
   return -1;
}

程式 1.6：搜尋一個有序串列 —— 迴路式二分搜尋法

仔細檢查程式 1.6 可以發現有兩種方法可以終止搜尋：一個是搜尋成功的訊號（list[middle] == searchnum），另一個是搜尋失敗的訊號（左指標和右指標交叉而過）。

程式因搜尋成功而終止的程式碼不必改變。但是，用來觸發搜尋失敗的 while 指令必須以一個對等的 if 指令取代它，此指令的 then 子句遞迴地引用函數。

int binsearch(int list[], int searchnum, int left,
                                          int right)
{
/* search list[0] <= list[1] <= ... <= list[n-1] for
searchnum. Return its position if found. Otherwise
return -1 */
   int middle;
   if (left <= right) {
     middle = (left + right)/2;
     switch (COMPARE(list[middle], searchnum)) {
       case -1: return
           binsearch(list, searchnum, middle + 1, right);
       case  0: return middle;
       case  1: return
           binsearch(list, searchnum, left, middle - 1);
     }
   }
   return -1;
}

程式 1.7：二分搜尋法的遞迴實作法

應注意，雖然程式碼已改變，但遞迴的函數呼叫與迴路式的函數呼叫是相同的。

對於一個有 $n$ 個元素的集合，$n \ge 1$，印出此集合所有可能的排列組合。例如集合為 $\{a,b,c\}$，則排列組合為

有 $n$ 個元素就有 $n!$ 個排列組合。再探討集合 $\{a,b,c,d\}$，可以發現一個用來產生排列組合的簡易演算法：

1. $a$ 之後接著 $(b,c,d)$ 所有的排列
2. $b$ 之後接著 $(a,c,d)$ 所有的排列
3. $c$ 之後接著 $(a,b,d)$ 所有的排列
4. $d$ 之後接著 $(a,b,c)$ 所有的排列

遞迴解法的線索是「接著所有的排列組合」這句話。它暗示如果有一個可以在 $n-1$ 個元素的集合上有效的演算法，就可以解決具有 $n$ 個元素的集合上的問題。

void perm(char *list, int i, int n)
/* generate all the permutations of list[i] to list[n] */
{
   int j, temp;
   if (i == n) {
     for (j = 0; j <= n; j++)
       printf("%c", list[j]);
     printf("    ");
   }
   else {
   /* list[i] to list[n] has more than one permutation,
   generate these recursively */
     for (j = i; j <= n; j++) {
       SWAP(list[i],list[j],temp);
       perm(list,i+1,n);
       SWAP(list[i],list[j],temp);
     }
   }
}

程式 1.8：遞迴的排列產生器 —— 啟始呼叫為 perm(list,0,n-1);

注意那對成雙的 SWAP：第二個 SWAP 把陣列還原，否則下一輪迴圈的交換基準就被破壞了。i 的值會隨著每一次的呼叫而改變，但 n 則不會；參數 list 為一個陣列的指標，其值也不會隨著呼叫而改變。

結構的定義以結構名稱和其名稱縮寫為首。定義中有兩大部份：物件（objects）和函數（functions）。符號「::=」應讀成「定義為」。

structure Natural_Number is
  objects: an ordered subrange of the integers starting at zero
    and ending at the maximum integer (INT_MAX) on the computer
  functions:
    for all x, y in Nat_Number; TRUE, FALSE in Boolean
    and where +, -, <, and == are the usual integer operations

    Nat_No  Zero( )          ::=  0
    Boolean Is_Zero(x)       ::=  if (x) return FALSE
                                  else return TRUE
    Nat_No  Add(x, y)        ::=  if ((x + y) <= INT_MAX) return x + y
                                  else return INT_MAX
    Boolean Equal(x, y)      ::=  if (x == y) return TRUE
                                  else return FALSE
    Nat_No  Successor(x)     ::=  if (x == INT_MAX) return x
                                  else return x + 1
    Nat_No  Subtract(x, y)   ::=  if (x < y) return 0
                                  else return x - y

end Natural_Number

結構 1.1：抽象資料型態 Natural_Number

注意定義中用到了其他資料型態（Boolean、整數集合上的 $+,-,\lt,==$）。這暗示了「為了要定義一種資料型態，我們也許需要使用其他資料型態中的運算」。

float abc(float a, float b, float c)
{
   return a+b*b*c +(a+b-c)/(a+b)+4.00;
}

程式 1.9：簡單算術函數

此函數接受三個簡單變數當成輸入，以傳回一個簡單值當成輸出。根據上述類別，此函數只有固定空間需求，因此 $S_{abc}(I) = 0$。

float sum(float list[], int n)
{
   float tempsum = 0;
   int i;
   for (i = 0; i < n; i++)
     tempsum += list[i];
   return tempsum;
}

程式 1.10：計算數值加總的迴路式函數

雖然輸出為單一數值，輸入卻包含了一個陣列。因此，可變的空間需求視陣列如何傳遞到函數而定。

float rsum(float list[], int n)
{
   if (n) return rsum(list,n-1) + list[n-1];
   return 0;
}

程式 1.11：計算數值加總的遞迴式函數

用此種方法時，編譯程式必須為每一次的遞迴呼叫保存參數、區域性變數，以及返回位址。在 80386 電腦上，整數和指標都需要 2 byte 儲存空間，浮點數需要 4 byte。

圖 1.1：程式 1.11 每次遞迴呼叫所需的空間

如果 MAX_SIZE = 1000，遞迴式程式所需要的可變空間為 $6 \times 1000 = 6000$ byte。迴路式程式則沒有可變空間需求。正如所見的，遞迴式程式比其相對的迴路式程式有較多的負擔（overhead）。

float sum(float list[], int n)
{
   float tempsum = 0;  count++; /* for assignment */
   int i;
   for (i = 0; i < n; i++)  {
     count++;               /* for the for loop */
     tempsum += list[i]; count++;  /* for assignment */
   }
   count++; /* last execution of for */
   count++; /* for return */  return tempsum;
}

程式 1.12：程式 1.10 加入計數指令

注意，我們只關心可執行的指令，所以函數頭、第二個變數宣告都自動地不列入考慮。因為主要的目的在決定最後的計數，可從程式 1.12 中將大多數的程式指令消除，得到化簡後的程式 1.13：

float sum(float list[], int n)
{
   float tempsum = 0;
   int i;
   for (i = 0; i < n; i++)
     count += 2;
   count +=3;
   return 0;
}

程式 1.13：程式 1.12 簡化版

因此，每次呼叫 sum，一共執行 $2n+3$ 步驟。

float rsum(float list[], int n)
{
   count++;      /* for if conditional */
   if (n) {
     count++;    /* for return and rsum invocation */
     return rsum(list,n-1) + list[n-1];
   }
   count++;
   return list[0];
}

程式 1.14：程式 1.11 加入計數指令

首先必須指出臨界條件 $n=0$ 時的步驟計數：當 $n=0$ 時只有 if 條件指令和第二個 return 指令會執行，因此全部的步驟計數為 $2$。對於 $n \gt 0$，if 條件指令與第一個 return 指令會執行，所以每一個 $n \gt 0$ 的遞迴呼叫的步驟計數加 $2$。因為一共有 $n$ 次的函數呼叫，其後再執行一次 $n=0$ 的函數呼叫：

void add(int a[][MAX_SIZE], int b[][MAX_SIZE],
              int c[][MAX_SIZE], int rows, int cols)
{
   int i, j;
   for (i = 0; i < rows; i++)
     for (j = 0; j < cols; j++)
       c[i][j] = a[i][j] + b[i][j];
}

程式 1.15：矩陣加法

void add(int a[][MAX_SIZE], int b[][MAX_SIZE],
              int c[][MAX_SIZE], int rows, int cols)
{
   int i, j;
   for (i = 0; i < rows; i++) {
     count++;  /* for i for loop */
     for (j = 0; j < cols; j++) {
       count++; /* for j for loop */
       c[i][j] = a[i][j] + b[i][j];
       count++; /* for assignment statement */
     }
     count++; /* last time of j for loop */
   }
   count++; /* last time of i for loop */
}

程式 1.16：矩陣加法加入計數指令

void add(int a[][MAX_SIZE], int b[][MAX_SIZE],
              int c[][MAX_SIZE], int rows, int cols)
{
   int i, j;
   for (i = 0; i < rows; i++) {
     for (j = 0; j < cols; j++)
        count += 2;
     count += 2;
   }
   count++;
}

程式 1.17：簡化的程式 1.16

也請注意這些成立但不夠緊的敘述：$3n+3=\Omega(1)$；$10n^2+4n+2=\Omega(n)$；$6\cdot 2^n+n^2=\Omega(n^{100})$、$\Omega(n^{50.2})$、$\Omega(n^2)$、$\Omega(n)$、$\Omega(1)$。

$3n+2 \ge 3n$ 當 $n\ge 2$，且 $3n+2 \le 4n$ 當 $n\ge 2$，所以 $c_1=3$、$c_2=4$、$n_0=2$，則 $3n+2=\theta(n)$ 成立。

其他成立的：$10n^2+4n+2=\theta(n^2)$；$6\cdot2^n+n^2=\theta(2^n)$；$10\log n+4=\theta(\log n)$。

不成立的：$3n+2\ne\theta(1)$；$3n+3\ne\theta(n^2)$；$10n^2+4n+2\ne\theta(n)$；$10n^2+4n+2\ne\theta(1)$；$6\cdot2^n+n^2\ne\theta(n^2)$、$\ne\theta(n^{100})$、$\ne\theta(1)$。

圖 1.5：矩陣相加之時間複雜度

建立圖 1.5 的表格實際上比建立圖 1.4 的表格容易。舉例而言，要獲得第 5 行的確實步驟計數 $\textit{rows}\cdot(\textit{cols}+1)$ 比將第 5 行看成一個漸近式複雜度 $\theta(\textit{rows}\cdot\textit{cols})$ 要困難得多了。另一種方法：因程式的行數是固定的（即與實體的特性無關），我們只要取得最大的指令行複雜度即可。

採用的實體特性是串列中的元素個數 $n$。while 迴圈每一次需時 $\theta(1)$。

因為使用漸近式分析，我們不需要如此精確的最差狀況下迴路執行次數之計算。除了最後一次，每一次迴路執行時會將必須搜尋的串列範圍減半 —— 也就是說，right - left + 1 的值在每一次迴路中以 2 為因數遞減一半。

最佳狀況複雜度為 $\theta(1)$，即在最好的狀況下 searchnum 於第一次執行 while 迴路時就被找到。（可以證明 while 迴圈最多重作 $\lceil\log_2(n+1)\rceil$ 次。）

重新考慮函數 perm（程式 1.8）。當 $i=n$，需時 $\theta(n)$。當 $i \lt n$，則執行 else 子句。在此子句中的 for 迴路進入的次數為 $n-i+1$ 次。此迴路每次執行需時 $\theta(n+T_{\text{perm}}(i+1,n))$。因此，當 $i \lt n$：

又因為當 $i+1 \le n$ 時 $T_{\text{perm}}(i+1,n)$ 最少為 $n$，我們可獲得對 $i \lt n$：

解此遞迴運算式，可得：

魔術方陣是一 $n \times n$ 的矩陣，其中填入 $1$ 到 $n^2$ 之間的整數，使得各行、各列，以及兩個主對角線上的元素和均相等。下圖為一個 $n=5$ 的魔術方陣，加總同為 65。

圖 1.6：$n=5$ 之魔術方陣

#include <stdio.h>
#define MAX_SIZE  15 /* maximum size of square */
void main(void)
/* construct a magic square, iteratively */
{
   static int square[MAX_SIZE][MAX_SIZE];
   int i, j, row, column;   /* indices */
   int count  ;             /* counter */
   int size;                /* Square size */

   printf("Enter the size of the square: ");
   scanf("%d", &size);
   /* check for input errors */
   if (size < 1 || size > MAX_SIZE + 1) {
     fprintf(stderr, "Error! Size is out of range\n");
     exit(1);
   }
   if (!(size % 2)) {
     fprintf(stderr, "Error! Size is even\n");
     exit(1);
   }
     for (i = 0; i < size; i++)
       for (j = 0; j < size; j++)
         square[i][j] = 0;
   square[0][(size-1) / 2] = 1; /* middle of first row */
   /* i and j are current position */
   i = 0;
   j = (size - 1) / 2;
   for (count = 2; count <= size * size; count++) {
     row = (i-1 < 0) ? (size - 1) : (i - 1); /*up*/
     column = (j-1 < 0) ? (size - 1) : (j - 1); /*left*/
     if (square[row][column])  /*down*/
       i = (++i) % size;
     else {                    /* square is unoccupied */
       i = row;
       j = (j-1 < 0) ? (size - 1) : --j;
     }
     square[i][j] = count;
   }
   /* output the magic square */
   printf(" Magic Square of size %d : \n\n",size);
   for (i = 0; i < size; i++) {
     for (j = 0; j < size; j++)
       printf("%5d", square[i][j]);
     printf("\n");
   }
   printf("\n\n");
}

程式 1.22：魔術方陣程式

令 $n$ 代表魔術方陣的大小（即程式 1.22 中變數 size 之值）：

• 檢查 $n$ 值是否錯誤的 if 指令需時 $\theta(1)$。
• 巢狀的 for 迴圈（初始化）複雜度為 $\theta(n^2)$。
• 下一個 for 迴圈每次執行需時 $\theta(1)$，此迴圈執行 $\theta(n^2)$ 次，所以其複雜度為 $\theta(n^2)$。
• 輸出魔術方陣的巢狀 for 迴圈也是需時 $\theta(n^2)$。

選取排序（selection sort）的最差狀況發生在元素以相反的順序排列時 —— 亦即，要將目前為降冪排列的一個陣列以升冪排序。為進行時間測試，將陣列的大小改變，由 $0, 10, 20, \ldots, 90, 100, 200, \ldots, 1600$。

#include <stdio.h>
#include <time.h>
#define MAX_SIZE 1601
#define ITERATIONS 26
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void main(void)
{
   int i,j,position;
   int list[MAX_SIZE];
   int sizelist[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90,
   100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100,
   1200, 1300, 1400, 1500, 1600};
   clock_t start, stop;
   double duration;
   printf("     n        time\n");
   for (i = 0; i < ITERATIONS; i++) {
     for (j = 0; j < sizelist[i]; j++)
       list[j] = sizelist[i] - j;
     start = clock();
     sort(list,sizelist[i]);
     stop = clock();
     /* CLK_TCK = number of clock ticks per second */
     duration = ((double) (stop-start)) / CLK_TCK;
     printf("%6d    %f\n",sizelist[i], duration);
   }
}

程式 1.23：Selection sort 函數的呼叫時間計算程式

圖 1.11：Selection Sort 最差狀況之效率（以秒為單位）

當我們想計算一個只需要很少的時間即可完成的函數之時間時，用來計算選取排序之直接的計時方法是不足的。本例要考慮一種更為精確的計時方法。

int seqsearch(int list[], int searchnum, int n)
{
/*search an array, list, that has n numbers. Return i,
if list[i] = searchnum. Return -1, if searchnum is not in
the list */
   int i;
   list[n] = searchnum;
   for (i = 0; list[i] != searchnum; i++)
     ;
   return ((i < n ) ? i : -1);
}

程式 1.24：Sequential Search 函數（注意 list[n] = searchnum; 這個哨兵寫法，讓迴圈裡不必再檢查 i < n）

這程式從陣列的第一個元素開始，以所要搜尋的數值 searchnum 和陣列中的每一個元素比較，直到 searchnum 被找到或是到達陣列的結尾才停止。如果要找的數不在陣列中，則出現此種搜尋的最差狀況 —— 陣列中所有的元素都經過比較，而迴圈反覆執行了 $n+1$ 次。

因為搜尋所需時間比排序少，即使對小的陣列，程式 1.23 所有的計時策略在此是不夠的。解法：對每一種陣列的大小，多次呼叫搜尋函數。因為在陣列的大小比較小時，函數執行速度較快，我們對小的陣列重覆搜尋之次數比對大的陣列還多。

#include <stdio.h>
#include <time.h>
#define MAX_SIZE 1001
#define ITERATIONS 16
int seqsearch(int [], int, int);
void main(void)
{
   int i, j, position;
   int list[MAX_SIZE];
   int sizelist[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90,
                     100, 200, 400, 600, 800, 1000};
   int numtimes[] = {30000, 12000, 6000, 5000, 4000, 4000,
                     4000, 3000, 3000, 2000, 2000,
                     1000, 500, 500, 500, 200};
   clock_t start, stop;
   double duration,total;
   for (i = 0; i < MAX_SIZE; i++)
     list[i] = i;
   for (i = 0; i < ITERATIONS; i++) {
     start = clock();
     for (j = 0; j < numtimes[i]; j++)
       position = seqsearch(list, -1, sizelist[i]);
     stop = clock();
     total = ((double)(stop-start))/CLK_TCK;
     duration = total/numtimes[i];
     printf("%5d %d  %d %f %f\n", sizelist[i], numtimes[i],
                            (int)(stop-start), total,
     duration);
     list[sizelist[i]] = sizelist[i]; /* reset value */
   }
}

程式 1.25：Sequential Search 的計時程式

圖 1.13：Sequential Search 之最差狀況效率（IBM PS/2 Model 50，Turbo C）

對於較大的 $n$ 值，時間和陣列大小之間的線性相關即變得更清楚。這是因為常數的加成因素，對小的 $n$ 值是有較大的優勢。（看最右欄：$n$ 從 100 到 1000 增加 10 倍，每次執行時間從 0.000495 到 0.004945 也大約增加 10 倍 —— 線性。）