VBSで便利なプログラムを作れスレ 2 (853ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
462(2): ピッコロ ◆YAZTByPXwc6o 2019/05/19(日)02:10 ID:iZGlVtrY(3/7)調 AAS
>>456
>>419の問題はソートがどうしようもないんだよね
ソートがあるから計算量の限界はn*log(n)になるかと
それはそれとして計算量はデータ量が増加したときに
計算資源の消費量がこういう比率で増加しますってものだから
あくまでもデータ量とセットで考えてこそ意味があるものだよ
一般的に計算量がよいアルゴリズムはデータ量が少ないときに時間がかかる傾向があって
たとえばクイックソートの平均計算量はn*log(n)で挿入ソートの計算量はn^2だけれども
件数が少ないときは挿入ソートの方が速い
各種標準ライブラリのソートでも要素数が少ないときは挿入ソートが使われてて
挿入ソートを使うときの閾値はライブラリによってまちまち
.NETは16以下
https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/Collections/Generic/ArraySortHelper.cs
Javaは46以下
https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/DualPivotQuicksort.java
FreeBSDは6以下
挿入ソートじゃなくてノームソートになってるけどまあ似たようなものだしまあいっかということで
https://github.com/freebsd/freebsd/blob/master/lib/libc/stdlib/qsort.c
Rubyはソースをきちんと追えなくて不確かだけれども
FreeBSDのqsortを使ってるっぽい気がする
今回の問題の要素数は6なので挿入ソートが最適かと
計算量はn^2で良い
464: 2019/05/19(日)02:10 ID:JyLc4k1U(2/2)調 AAS
>>462
自演乙
471(2): 2019/05/19(日)20:52 ID:1kdfr1Yk(3/3)調 AAS
>>462
ソートが O(log n) を超えられないってのは有名な話。
が、それ以降意味不明。馬鹿だろお前。
1,. ソートアルゴリズムは得手不得手がある
2. 乱雑な方が得意か、整然としている方が得意か、はある
3. 事前予測はかなり大事だが、一般論としては O(log n)
> 一般的に計算量がよいアルゴリズムはデータ量が少ないときに時間がかかる傾向があって
> たとえばクイックソートの平均計算量はn*log(n)で挿入ソートの計算量はn^2だけれども
> 件数が少ないときは挿入ソートの方が速い
ハァ？？？？？？？？
その「少ない」はお前の年間仕事量くらいのことを言うんだろ？？？？？？？？
今時のCPUなら苦にしないようなことを言ってるんだろ？？？？？？？？
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.032s