VBSで便利なプログラムを作れスレ 2 (853ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
456(2): 2019/05/18(土)23:55 ID:lvC3F7mV(5/5)調 AAS
>>447
飲んでたから勘違いしたけどO(2n)は無いわ。
Oのカッコの中に定数が入ること自体が間違いだった。
そこを指摘すれば良かったのに。
あれは最悪でO(****)だな。
さて****は何でしょう？
461(1): ピッコロ ◆YAZTByPXwc6o 2019/05/19(日)02:10 ID:iZGlVtrY(2/7)調 AAS
>>456
O(2n)の実装があるならすごいと思ったし
それを知りたいと思ったから教えてもらうのが良いと思ったんだよね
どういうアルゴリズムかわかってないのにそれはダメと指摘するのはキチガイじゃん
ピッコロはキチガイじゃないから教えてもらおうと思ったの
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で良い
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.038s