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