最初の授業ということで、シラバスなどのガイダンスに交えて、 「プログラムを作る時、何を考慮して書くべきか」という質問をしてみた。 こちらとしては、プログラムでのアルゴリズム評価の観点ということで、 「処理速度」、「使用メモリ量」、「アルゴリズムの複雑さ」という答えを 期待していたんだけれど、プログラムの見易さについての返答ばかり。 「処理速度」という答えがでるまでに随分と時間がかかってしまった。

速度・メモリ・複雑さの3つは、それぞれ速度優先のアルゴリズムは、メモリを大量消費したり、 プログラムが複雑になるなど、一方を優先すれば他方に悪影響のでる トレードオフの関係にあることを解説。 単純検索・2分探索法・全データメモリーマップなどの方法を例に挙げて説明を行う。 プログラム開発では、トレードオフの関係にあるからこそ、 その状況に応じたアルゴリズムを選択(デザイン)できるためにも、 速度・メモリ・複雑さを客観的に評価できる必要性がある。

速度の評価

まず手始めに、N件のデータを配列の中から探す処理で説明。

int  data[ N ] ;
int  key = ??? ;
for( int i = 0 ; i < N ; i++ ) {
   if ( data[ i ] == key )
      break ;
}

このプログラムの実行時間を考えると、最悪のケースでは、式の実行回数は、 i=0 | 1回、i < N | N+1回、i++,if(==) | N回となる。 よって、処理時間は、以下の式で示される。

このプログラムで、1000件で1msecの時間を要した場合、 10000件であれば、何秒かかるか？という問題があった場合、2変数1式であり 通常では処理時間を求めることができない。しかし、 処理速度の見積もりでは、大抵データ件数Nは巨大な場合がほとんどであり、 も、1回の初期化の時間であり、きわめて小さい値が一般的であり、無視できる。 よって、 から、10000件では、10msecという予想時間を求めることができる。

次に、もう少し複雑な例ということで、データの並び替えで最大選択法の プログラムを示し、処理時間を議論する。

int  data[ N ] ;
int  i , j , m , t ;
for( i = 0 ; i < N-1 ; i++ ) {
   m = i ;
   for( j = i+1 ; j < N ; j++ )
      if ( data[ m ] < data[ j ] )
         m = j ;
   t = data[ m ] ;
   data[ m ] = data[ i ] ;
   data[ i ] = t ;
}

内部のjのループの実行回数は、(N-1-i) 回であり、 これを外側iのループで回すため、以下のような式で示される。