前回のmalloc+freeの理解確認のための課題の２回目ということで、 課題時間とするが、この後の授業進行のために、配列の問題点を説明する。

配列の問題点

現在、mallocの課題で、動的メモリ上に確保した配列上にデータを保存しているが、 基本は以下のような処理だろう。

int data[ 100 ] ;
int size = 0 ;
while( 入力繰り返し判定 ) {
data[ size++ ] = 入力値 ;
}

このプログラムであれば、すでに入力済みの配列にデータ1件を追加する処理は、 配列末尾に入れて、size を増やすだけの一定処理。このため、 データ追加はO(1) となる。
一方、この配列の中から目的データを探すには、登録データがデータ順とデタラメで あれば、配列先頭からループで探すしかない。つまり、データ検索はO(N)となる。

これに比べ、高速な検索方法として紹介した、2分探索法は、比較の度毎に対象が 半分となることから、検索時間はO(log N)となる。
しかしながら、新たにデータを追加する場合は、 挿入すべき場所を探す処理O(log N)と、１件分の場所を確保するために、 以下のようなループでデータをずらす処理となり、その処理時間はO(N) となる。

int pos = データを入れる場所 ;
for( i = N ; i >= pos ; i-- ) {
data[ i + 1 ] = data[ i ] ; // 後ろからずらさなとダメ
}

このことからも、配列は途中にデータを入れる処理が苦手といえる。 また、配列を扱うプログラムでは、データの追加がめったに発生せず、 データを探す処理が中心であれば、２分探索法が効率が良い。 しかし、途中でデータが頻繁に追加され、検索中心でないのであれば、 最初の末尾追加の使い方で良い。