アルゴリズムの計算量|対数関数logをなんとなく復習

試験勉強 情報処理技術者関連
この記事は約2分で読めます。

情報処理技術者試験の勉強をしていると、アルゴリズムとデータ構造の分野で出てくる計算量。
その中で「log」が出てきますが、高校で習う数学なんて忘れまくっているので、少し基礎から復習してみます。

アルゴリズムの計算量とlog

ソートやサーチのアルゴリズム。
その効率を示す手段として用いられるのが計算量という考え方。

計算量:N個のデータを処理して目的の結果を得るまでの最大の処理回数を示します

アルゴリズムの中でも、下記のアルゴリズムの計算量が「N*logN」となります

・マージソート(marge:結合)
・クイックソート(quick:速い)
・ヒープソート(ヒープデータ構造)

もう一つ、下記アルゴリズムが「logN」となります

・二分探索法(にぶんたんさくほう)

分かり易い数字を入れて考える

8個のデータを二分探索法でソートしていく計算量は「log8
実際にソートすると、8個→4個→2個→1個と、3回2分割を繰り返します。その結果

3=log8

となります。実はlogの右下には小さい定数「2」が隠れていて(2の場合は省略可能)、2を3乗すると8になることを表しています。

2分割を繰り返す、二分探索法は、逆に計算すると2乗を繰り返すことを意味しています。

これ以上は、深追いしない

なんとなくの意味が分かった所で、log(指数関数)についての深追いは辞めておきましょう。
今回は情報処理技術者試験を受かればOK。高校の数学のテストをしている訳じゃありませんからね。

logを深追いするぐらいなら、テクノロジ系の計算問題を一問でも多く解きましょう!

コメント

タイトルとURLをコピーしました