１００枚のカードの整列にクイックソート法でおよそ5分かかるとき２００枚

質問

１００枚のカードの整列にクイックソート法でおよそ5分かかるとき２００枚のカードを同じ方法で整列すると　およそ　どれくらいの時間がかかるか

１００枚のカードの整列の単純ソート法でおよそ５分かかるとき、２００枚のカードを同じ方法で整列するとおよそ　どれくらいの時間がかかるか

以上２点について教えてほしいです。また、答えの導き方も教えていただければ幸いです。

回答No.3

jjon-com

整列対象となるデータ数をＮとするとき，

単純ソートの計算量は，Ｎの2乗のオーダ。言い換えれば，整列時間はＮの2乗に比例して増加する。
データ量が100枚→200枚，すなわち，２Ｎになったので，整列時間は(２Ｎ)の2乗 ＝ ４×(Ｎの2乗)，すなわち，４×５分＝20分となる。

データが特別な条件下にないクイックソートの計算量は，Ｎ×log2Ｎのオーダ。
データ量が２Ｎになったので，整列時間は(２Ｎ)×log2(２Ｎ) ≒ ２×(Ｎ×log2Ｎ)【注】，すなわち，２×５分＝10分となる。
【注】log2(２Ｎ) ＝ (log2Ｎ)＋１ なので，両辺はほとんど変わらないと見なせるため。

log2Ｎという対数表記自体が分からなければ，次のQ&Aを参照。
http://okwave.jp/qa/q5985172.html の私の過去の回答ANo.2

回答No.2

kmee

「オーダー」とか「O(n)」って式とかって、習ったり聞いたりしたことはないですか?
あと、「計算量」というのも。

細かい定義は、数学書なり、技術書なり、ネットなりで調べてください。

ソートのアルゴリズムは、それぞれに特色がありますが、大抵は、並び換えるものの数で計算速度が変化します。
n個のデータをソートするときの、nにたいしてどれくらいの計算量かを表わす目安として、O(f(n)) (f(n) はnの関数)が使用されます。
m*n個のデータの計算量はO(f(m*n))ですから、数はm倍になると、計算量はほぼf(m*n)/f(n)倍になります。

クイックソートの計算量は、アルゴリズムの実装方法や初期のデータの並び方で大きく変化します。
最悪の場合だと、 O(n^2)(nの二乗)です。
nが2倍になると、(2*n)^2/n^2 = 2^2=4倍の計算量になります。
100枚で5分なら、200枚では最悪5分*4倍=20分ということになります。

ただ、通常はデータの並びが最悪のケースにはならないし、最悪のケースを回避するようなプログラムにするので、最悪の計算量ではなく、平均の計算量で考えます。

回答No.1

Tacosan

それぞれの計算量を考えてください.