情報処理技術者試験の勉強をしていると、アルゴリズムとデータ構造の分野で出てくる計算量。
その中で「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を深追いするぐらいなら、テクノロジ系の計算問題を一問でも多く解きましょう!

コメント