Computer Knowledge and Image Processing

2014年4月7日星期一

巨集與函式的差異

設計程式時，有很多地方可使用含有引數的巨集或是使用函式，到底應選擇哪種方式撰寫，我們可由時間(Time)和空間(Space)兩方面來考慮：

1. 由於巨集在編譯前先進行前處理時，會將巨集進行代換變成程式中的敘述。若巨集引數稍微使用不當易引起副作用。至於函式則不會發生此種現象。

2. 若在程式中使用到多次巨集，在進行編譯前，前置處理器會進行取代的動作，因此較費時一點。但執行時不必像呼叫函式時，必須跳到函式所在處，待執行完再返回原呼叫處的下一個敘述，因此巨集執行時間較快，但程式空間加長。

3. 若在程式中呼叫函式多次，卻只要在程式中留下一份函式的拷貝，呼叫函式時跳到函式所在處，待執行完再返回原呼叫處的下一個敘述，因此函式比巨集較花費時間，也就是說函式執行時間較慢，但程式長度不會長。

4. 函式在編譯時會做參數檢查；巨集指引編譯前己變成敘述，所以不會做參數檢查。

編譯前經過前置處理器會將程式中的巨集直接轉換成所指定的敘述。和函式比較起來，使用巨集可以省掉程式執行時再去呼叫函式的時間，以縮短程式的執行時間，增加程式的可讀性及效率。因此定義巨集可以替代一些簡單的運算式或單行的簡單函式，而函式則適用於較複雜的功能。

巨集　(macro)
優點：執行速度快，沒有堆疊的 push 和 pop 動作的需要，減少時間的耗損。

缺點：巨集被呼叫多次以後，會耗損存放及使用大量的記憶體空間。

函數　(call function/call subroutine)
優點：即使函數被呼叫多次，在記憶體中仍只有一份實體，較節省記憶體空間。能節省存放及使用的記憶體空間。

缺點：執行速度較慢，需花費時間在堆疊的 push 和 pop 動作上。

參考資料：C & C++ 程式設計經典

2014年4月6日星期日

Search Algorithms

1.循序搜尋法(sequential searching)

又稱線性搜尋法(linear search)，為一筆一筆資料依序比對，直到找到所要搜尋的記錄為止。

時間複雜度為O(n)

平均搜尋長度= ( 1 + 2 +3 + ...... + n ) / n = ( n + 1 ) / 2

Example

int seqsearch(int a[], const int key, const int n){

int i;

for(i = 0 ; i < n ; i++)

if(a[i] == key) return i;

return -1;

}

2.二元搜尋法(binary searching)

   取中間值與搜尋值比對

   時間複雜度為O(log2n)

  差的情況下， n / 2 ^ m = 1 ，m = log2n，n個串列，m次比對。

須事先予以排序

   中間值：mid = ( low + high ) / 2

Example

//a[] is an sorted integer array

int binarysearch(int a [], const int x, const int n){

int left = 0, right = n - 1;

while (left <= right){

int middle = (left + right) / 2;

if(x > a[middle]) left = middle + 1;

else if(x < a[middle]) right = middle - 1;

else return middle;

}

return -1;

}