技術とか戦略とか

証券レガシーシステムを8年間いじった普通のSEによるブログ。技術のみではなく趣味の戦略考察についても。

オーダ(O)

目次

https://1drv.ms/b/s!AivF3bzWXOzuhG1Xk5hscKYqkLkM

-------------------------------
今回は、検索アルゴリズムやソートアルゴリズムの性能を評価する際に用いられるオーダ(O)について書きます。
 
実務で検索アルゴリズムやソートアルゴリズムを自力で実装することはOSやフレームワークを開発する職種でない限りまずないと思いますが、オーダは処理時間の見積もりの際に使用することがあります。
情報処理技術者試験でもオーダに関する問題は出題されることがあります。
 
下記に、代表的なアルゴリズムとそのオーダを記載します。

ここで、Nはデータ量のことを指し、オーダは処理時間のことを指します。
例えば、「O(N^3)」なら、処理時間はデータ量の増加の割合の3乗となります。
データ量が2倍になれば、処理時間は8倍(2^3)となります。
 
また、情報処理の分野では、logの底は2とされています。
そのため、「logN」とは、「2を何乗したらNになるのか」を指す値となります。
log2は1(2^1=2)、log4なら2(2^2=4)、log1024なら10(2^10=1024)となります。
例えば、2分検索の場合、階層が1深くなれば(処理回数が1回増えれば)2倍のデータを検索できるようになるので、「2^処理回数=データ量」の関係が成り立ち、O(logN)と表記できます。
 
例として、データ量が4倍になった時の処理時間の増加量を以下に示します。

なお、実務で処理時間を見積もる際、OSや製品で用意されている検索・ソートアルゴリズムは原則として高速なものが用意されているので、2分検索やクイックソートマージソートヒープソートと同じオーダで計算して良いでしょう。