下载掌阅APP，畅读海量书库
立即打开
在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）。