目次
https://1drv.ms/b/s!AivF3bzWXOzuhG1Xk5hscKYqkLkM
-------------------------------
今回は、検索アルゴリズムやソートアルゴリズムの性能を評価する際に用いられるオーダ(O)について書きます。
実務で検索アルゴリズムやソートアルゴリズムを自力で実装することはOSやフレームワークを開発する職種でない限りまずないと思いますが、オーダは処理時間の見積もりの際に使用することがあります。
情報処理技術者試験でもオーダに関する問題は出題されることがあります。
下記に、代表的なアルゴリズムとそのオーダを記載します。
ここで、Nはデータ量のことを指し、オーダは処理時間のことを指します。
例えば、「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)と表記できます。
例として、データ量が４倍になった時の処理時間の増加量を以下に示します。
なお、実務で処理時間を見積もる際、OSや製品で用意されている検索・ソートアルゴリズムは原則として高速なものが用意されているので、２分検索やクイックソート・マージソート・ヒープソートと同じオーダで計算して良いでしょう。
