アルゴリズムの実行時間解析について思うところがあったのでちょちょいと。
ちょっと前にヒープソートと比較によるソートの計算量の評価をした日記を書きましたが今日もまたソートがらみの話です。
最近解いたいくつかの問題でソートアルゴリズムと別のアルゴリズムを組み合わせて、新しいアルゴリズムを設計する問題がありました。
例えば、凸包問題だったり(ソート+勾配計算)、組み合わせ問題(ソート+比較)だったりと。
その組み合わせ問題なんですが、実際の問題としては、配列Aと整数xが与えられたときに、a+a[j]でxが表現出来るか否かを判定しろ、というもの。
そんでこの問題をO(nlogn)で解くアルゴリズムを設計しろというのが題意ですね。
もちろん単にごりごりブルータルに計算することも出来ますがその場合比較にnC2回かかり、これはn(n-1)/2*1でO(n^2)になってしまうのでNG。
キモはソートがO(nlong)であるということ。つまり、ソートをした後に何らかの方法で組み合わせの計算量を減らしO(nlong)で抑える、という方針を建てることが出来ます。
要素数がnで計算量がO(nlogn)の場合、今までの経験から何らかの探索用の木をつくるのではないか?ここで参考書をひっぱり出しデータ構造の欄をペラペラとやると2-3木が出てきました。
全体の流れとしてはこんな感じ。
1.ソートする
2.探索用の木(2-3木)を作る
3.探索する
教科書によるとnの葉を持つ2-3木を作り、n個の要素を探索するにはO(nlogn)らしいので、これはソートの計算量以下であるため、目的は達成したのですがここで軽く違和感を感じませんでしょうか？
探索用の2-3木を作るには一つづつ葉を挿入していく必要があります。
一回の挿入に必要な計算量はO(logn)以下(n番目の葉を挿入するときにようやくO(logn)必要になる)。全部でn回挿入されるのでO(nlogn)。
そして今度は探索にうつりますが、1つの要素の探索に対してO(logn)かかります(根から枝を辿り、葉までつくのに必ずO(logn)必要)。今回の例だと、x=10で要素のうち一つが1だとしたら10-1=9が存在するか探索することになりますね。例のごとくn回かかるのでO(nlogn)。
2,3行目を実行するにはO(nlogn)を三回倍する必要があるのです。しかし3O(nlogn)=O(3nlogn)=O(nlogn)というふうに定数は潰されるので結局O(nlogn)になるという論法です。
確かにオーダー記号は元々このような意図があって考案されたものですが、実装する側としてはなんとも言えない気分になります。
もしあるアルゴリズムが
1.algo1
2.algo2
3.algo3
...
M,algoM
というふうなフローになっているとして、一つ一つのアルゴリズムがO(nlogn)だとすれば、結局全体ではO(nlogn)になるのです。M>nである場合とかどうするんだろ、と考えてしまいますね。
O(nlogn)のトリック
Re: O(nlogn)のトリック
オーダーはnが十分に大きいときに意味を成すので，
M>nの場合はオーダーで実行時間解析することがあまり意味をなさないだけと思いますよ．
実際．たとえば行列計算などにO(n^3)程度の計算負荷がかかるものが多いですが，それよりわずかに計算オーダーの小さい計算手法があっても
それを採用することは少ないですね．（並列化の容易さや，nの大きさの都合上実用的な範囲（nが～数百万とか）ではO(n^3)の計算手法のほうが速いから）
ソートの例をとれば，要素数が３とか４なのにわざわざクイックそーととかマージソート使わないってことと同じだと思いますが．
M>nの場合はオーダーで実行時間解析することがあまり意味をなさないだけと思いますよ．
実際．たとえば行列計算などにO(n^3)程度の計算負荷がかかるものが多いですが，それよりわずかに計算オーダーの小さい計算手法があっても
それを採用することは少ないですね．（並列化の容易さや，nの大きさの都合上実用的な範囲（nが～数百万とか）ではO(n^3)の計算手法のほうが速いから）
ソートの例をとれば，要素数が３とか４なのにわざわざクイックそーととかマージソート使わないってことと同じだと思いますが．
Re: O(nlogn)のトリック
>>GRAMさん
なるほど。オーダーが有効になるのはlin{n->∞}のとき、ということですか。
>並列化の容易さや，nの大きさの都合上実用的な範囲（nが～数百万とか）ではO(n^3)の計算手法のほうが速いから
これは少し目から鱗ですね。
たとえば行列計算ではシュトラッセンのアルゴリズムというものがあるらしく、O(n^(log_2^7))~O(n^2.807)の計算量で済むとwikiにありましたが、
これはnの値が数百万になるとO(n^3)の方が速くなるのは驚きです。
なるほど。オーダーが有効になるのはlin{n->∞}のとき、ということですか。
>並列化の容易さや，nの大きさの都合上実用的な範囲（nが～数百万とか）ではO(n^3)の計算手法のほうが速いから
これは少し目から鱗ですね。
たとえば行列計算ではシュトラッセンのアルゴリズムというものがあるらしく、O(n^(log_2^7))~O(n^2.807)の計算量で済むとwikiにありましたが、
これはnの値が数百万になるとO(n^3)の方が速くなるのは驚きです。
RE: O(nlogn)のトリック
chop.chop さんが書きました:その組み合わせ問題なんですが、実際の問題としては、配列Aと整数xが与えられたときに、a+a[j]でxが表現出来るか否かを判定しろ、というもの。
そんでこの問題をO(nlogn)で解くアルゴリズムを設計しろというのが題意ですね。
もちろん単にごりごりブルータルに計算することも出来ますがその場合比較にnC2回かかり、これはn(n-1)/2*1でO(n^2)になってしまうのでNG。
キモはソートがO(nlong)であるということ。つまり、ソートをした後に何らかの方法で組み合わせの計算量を減らしO(nlong)で抑える、という方針を建てることが出来ます。
要素数がnで計算量がO(nlogn)の場合、今までの経験から何らかの探索用の木をつくるのではないか?ここで参考書をひっぱり出しデータ構造の欄をペラペラとやると2-3木が出てきました。
全体の流れとしてはこんな感じ。
1.ソートする
2.探索用の木(2-3木)を作る
3.探索する
教科書によるとnの葉を持つ2-3木を作り、n個の要素を探索するにはO(nlogn)らしいので、これはソートの計算量以下であるため、目的は達成したのですがここで軽く違和感を感じませんでしょうか？
違和感を感じました。
これって素直にソート(O(n log n))してから二分探索(各iについてjを探索してO(n)×O(log n)→O(n log n))で解ける問題ではないのですか？
Re: O(nlogn)のトリック
>>みけCATさん
二分探索!そういうのもあるのか!
確かにソートされていればそのような探索が可能ですね……これはいいことを教えてもらいました。ありがとうございます。
2-3木をO(nlogn)で作るためにもソートされている必要があったのでソート済みの旨みをちゃんと使っていると思い込んでいました。
わざわざ探索用の木を作らなくても1要素の探索に対する計算量がO(logn)とできるデータ構造であるのに気付くべきでした。
二分探索!そういうのもあるのか!
確かにソートされていればそのような探索が可能ですね……これはいいことを教えてもらいました。ありがとうございます。
2-3木をO(nlogn)で作るためにもソートされている必要があったのでソート済みの旨みをちゃんと使っていると思い込んでいました。
わざわざ探索用の木を作らなくても1要素の探索に対する計算量がO(logn)とできるデータ構造であるのに気付くべきでした。
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター