2-5　思考數組的優缺點

在2-3-2節，筆者說過當發生數組空間不足時，必須移動整個數組到新的內存空間，如果常常移動數組會造成程序的執行效率降低，為了避免這類情況發生，可以使用為數組多預留空間的方法。

例如，假設有5個數據，我們可以要求先預留10個數據的內存空間給此數組使用，這樣就不會為了要插入新的數據，必須將數組數據移動。不過這時也會有下列缺點：

（1）如果未來數組擴充至超過10個數據時，此數組數據仍必須在內存內移動。

（2）如果未來程序沒有使用到多余的內存空間，此內存空間就會被浪費，因為別的程序也無法使用。

所以雖然數組數據結構簡單好用、容易理解、讀取數組內容速度很快，所需時間是O（1）相當于是瞬間就可以找到數據，但是仍不是最好的方法。下列是數組結構相關的時間復雜度。

至于常用的搜尋功能，如果我們不對數組做任何處理，所需的搜尋時間是O（n），但是如果先將數組執行排序，使用二分法做搜尋，所需的時間是O（log n），第10章筆者將會用程序說明。假設有一排序數組如下：

1， 2， … ， 50， 51， …， 99

所謂的二分法是將欲搜尋的數字與中間50做比較，如果大于50就往右與75做比較，如果小于50就往左與25做比較，依此概念持續下去，可以很快找出所搜尋的數字。這時所需要的搜尋時間的時間復雜度是O（log n）。