今回の記事は、検索アルゴリズムやソートアルゴリズムの性能を評価する際に用いられる「O(オーダ)」の概念についてです。
「O」は情報処理技術者試験ではよく主題されるものの、業務系SE（特定の業務のシステム設計を得意とするSE）には無縁のものに思われがちです。
しかし、業務系SEでも「システム改修によりデータ量が○倍になるが、このバッチ処理は○分以内に終わらせないといけない」という形で性能面を考えた設計が必要になることがあります。
実際に本番と同じ環境・改修後のデータ量を用意してテストができれば良いのですが、それができない場合は本番環境の現状のデータ量・処理時間から改修後の処理時間を見積もる必要があります。
（この見積もりで求められる性能が出ない場合は、性能を向上させるための設計を考える必要が出てきます）
このような見積もりで、「O」という概念が必要になります。
下記に、代表的なアルゴリズムとそのオーダを記載します。
・線形検索
O(N)
・２分検索
O(logN)
・バブルソート、基本選択法、基本挿入法
O(N^2)
・クイックソート、マージソート、ヒープソート
O(NlogN)
ここで、Nはデータ量のことを指し、Oは処理時間のことを指します。
例えば、「O(N^3)」なら、処理時間はデータ量の増加の割合の３乗となります。
データ量が２倍になれば、処理時間は８倍(2^3)となります。
また、情報処理の分野では、logの底は2とされています。
そのため、「logN」とは、「2を何乗したらNになるのか」を指す値となります。
log2は1(2^1=2)、log4なら2(2^2=4)、log1024なら10(2^10=1024)となります。
例えば、２分検索の場合、階層が1深くなれば(処理回数が1回増えれば)２倍のデータを検索できるようになるので、「2^処理回数=データ量」の関係が成り立ち、O(logN)と表記できます。
例として、データ量が４倍になった時の処理時間の増加量を以下に示します。
・線形検索
4倍(N)
・２分検索
2倍(logN)
・バブルソート、基本選択法、基本挿入法
16倍(N^2)
・クイックソート、マージソート、ヒープソート
8倍(NlogN)
なお、実務で処理時間を見積もる際、OSや製品で用意されている検索・ソートアルゴリズムは原則として高速なものが用意されているので、２分検索やクイックソート・マージソート・ヒープソートと同じオーダで計算して良いでしょう。
いかがでしたでしょうか。
情報処理技術者試験で学んだ知識が本当に実務で役に立ったのが個人的に印象的だったので、記事として書きました。
これ以外にも実務で役に立つ知識は少なくないので、単に合格するために試験勉強するのではなく、実務で使える引き出しを増やすために勉強した方が良いと個人的には思っています。
これからも実務で使える/使えたことがあれば、記事として発信していきたいと思います！
コメント