オーダ(計算量)について
オーダ(計算量)とデータ構造とアルゴリズム
yama☆shiroさんから今朝講義を受けました。
先日ソートアルゴリズムのコードをアップしましたが、
バブルソートとクイックソートそれぞれのオーダについて考えてみようというお題です。
比較回数や交換回数から計算量を求めます。
このとき、nの次数が最大の項に注目します。(一番影響が大きい)
最小計算量 | 最大計算量 | |||
バブルソート | ||||
クイックソート |
ひさびさの対数・・・><
アルゴリズム系の話って対数やら行列やら高校数学がよく登場しますよね。
同期に数学とぷよぷよのスペシャリストがいるので一度勉強会をお願いしようと思ってます。
オーダ(計算量)ってパフォーマンスに直結しそうです。
なるほど、でも難しいなぁ。。。
まず、選択するには選択肢があるということを知っていなければ・・・
リサーチ力大事ですね。
※データ構造 リスト、キュー、スタック、ツリーなど。
※アルゴリズム 解を求める手法。
例えば、クイックソートは再帰を使って、メモリ上にツリー構造を作って処理しています。
速度はバブルソートに比べてかなり早いですが、メモリを圧迫します。
実際、ソートの処理時間を計測したときに配列の要素数を色々変えて試したのですが
たった10000件弱でスタックがパンクしました。
どう対処するものなんだろう・・・。
・再帰を使わない?
・オブジェクトにスタックの状態を保存?(でもいつかはヒープもパンクする?)
・そもそもクイックソートを使わない?
後でまた調べてみます。