挿入の時間sort vs mergesort

Question

挿入ソートとmergesortが1000要素（例えば1秒）で同じ時間を要する場合、各アルゴリズムが10^6要素と10^9要素をそれぞれソートするのにどれくらいの時間がかかりますか？

挿入のソートとマージソートのBig Oはそれぞれn^2とn * log nです。

これは実際には私が持っている割り当てについての副次的な質問であり、確かな答えがあるはずです。

回答の根拠を説明してください。

Answer 1

インパルソートの時間の複雑さはO(n^2)なので、ソートする要素の数はnで、時間は二次的に変わります。 n=1000が1秒かかる場合、n=10^6は、1*(10^6/1000)^2=10^6秒をとり、n=10^9は、1*(10^9/1000)^2=10^12秒をとります。 Mergesort時間の複雑さはO(n*log(n))です。だから、n=10^6には2000秒かかり、n=10^9には3*10^6秒かかります。 O(n^2)とO(n*log(n))の両方がO(n)よりも高いため、マージソートのために追加のストレージスペースO(n)を大量のの制限と見積もりに割り当てて、ソートの時間の複雑さだけに基づいて推定するのに必要な時間は無視できます。お役に立てれば。

Answer 2

私の答えは、要素サイズと、必要な作業メモリを取得する方法については何も教えられていないので、質問に答えられないということです。 （挿入ソートには一定の追加メモリが必要ですが、mergesortにはO（n）の追加メモリが必要です）。要素が100KiBの場合、作業メモリの割り当てにはかなりの時間がかかります。