4EIの授業と言うことで、情報構造論のガイダンスぅ～と思っていたけど、 担任クラスだしインターンシップの希望調査の説明を行う。 それと、体育祭の参加種目決めもできていないので、後半30分を明け渡し、 残った時間でガイダンス。

まずは、例年通りに「プログラムを作るために考慮すべき要因」を聞いてみる。 色々出てきたけど、この授業でのポイントは、「処理速度」と「メモリ消費量」と「プログラムの簡単さ」 が重要であることを示す。 簡単さの中には、「納期」といった重要性も関係することを話し、これらの３要因は、 「トレードオフ」の関係にあり、一つの要因を優先すると、他の要因に悪影響の出る関係を、 具体的に話す。そして、この授業では3要因を評価したうえで適切にアルゴリズムを選べるようになることが目標と解説する。

単純検索の処理速度の評価

まずは、速度の評価ということで、配列から特定値を検索する処理の説明を行う。

int search( int array[] , int size , int key ) {
   for( int i = 0 ; i < size ; i++ ) {
      if ( array[ i ] == key )
         return i ;
   }
   return 0 ;
}

このプログラムで、最悪のケースであれば、 式の処理回数は、「i=0」1回、「i<size」は N+1 回、「if(…)return」がN回となる。 これより、N件の場合の処理時間T(N)は、 で示される。

例えば、「データN=1000件の検索が0.01[sec]であった場合、N=10000件では、 何秒かかるか？」 そのまま前述の計算式を当てはめると、未知変数が の2つであるため、時間を求めることはできない。 しかし、処理速度の見積もりでは厳密な値を知りたい訳ではない。 は、Nが巨大な値では無視できるほど小さな値であることから、 0.01[sec]= で計算を見積もればいい。

次週は、このネタを2分探索法や、2重ループ処理に適用した場合の説明を予定。