ホーム » スタッフ » 斉藤徹 » ループ処理とオーダ記法

2009年4月
« 3月   5月 »
 1234
567891011
12131415161718
19202122232425
2627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

ループ処理とオーダ記法

ループ処理の時間

先週の、単純検索の処理時間が、 T(N)=Ta+Tb*N、 2分探索のループ回数が、 m=log(N)の説明に続き、 その処理時間は、 T(N)=Ta+Tb×log(N) であることを示す。

もう少し複雑になった事例ということで、2重ループを含む最大選択法による並べ替えは、 最内ループ回数が m=∑(i=1~N-1){ i }となることを示し、 最大選択法の処理時間は、 T(N)=Ta+Tb*N+Tc*N^2で示されることを説明する。


その他の公式

オーダ記法

前述の処理時間の式では、処理時間に関する定数が沢山でてくる。 また、Nが大きく変化した時の処理時間のおおよその予測の際には、 Nの次数の低い項は無視する場合が多い。

このためプログラムのアルゴリズムの効率(処理時間)を議論するときは、 Nが巨大になった時の最も値の大きい項の変化式の部分だけで、 大まかな処理時間の予測ができる。この式でアルゴリズムを表現したものを オーダ記法(ビッグオー記法)と呼ぶ。

よって、 単純検索は、、 2分探索は、、 最大選択は、で示されることを説明する。

処理時間の予測

2分探索法で、データ(N)が100件の時の処理時間が1msecであった場合、 データが1000件の場合どのくらいの処理時間となると予想されるか?

オーダ記法では、 は、 なので、 より、 (ただしlogの底は10とする)。 よって、

授業の最後に、複数の項のNの次数が微妙で増加速度の判断が困難な場合の オーダーを求める手法として、ロピタルの定理を用いた方法なども説明する。