なあ、再帰関数好きな人いる？ パート3 [転載禁止]©2ch.net (914ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
281(3): 2015/12/26(土)19:14 ID:6n5NtJkM(6/26) AAS
>>278
>>201 がすべてを物語っている。
これが何よりの証拠。再帰がとてつもなく効率が悪いことを
つまびらかにしてみせた。ここに来て見てみぬふりは通用しない。
エビデンスもきちんと示されている。もはや知らぬ存ぜぬでは済まされない。
284(1): 2015/12/26(土)19:16 ID:Igcba1qr(9/15) AAS
>>281
障害児くん
10000倍と130倍って、どっちがどれだけ大きいかわかる?
286(2): 2015/12/26(土)19:21 ID:oIXuKyHb(7/16) AAS
>>281
ちょっと試せば分かることなんだけど、シェルスクリプトに於いて再帰の実行速度は
呼び出し深さnに対してO(n^2)くらい掛かる。
で、クイックソートの呼び出しの深さは要素数mについてO(log m)なので
O(log^2 m)の計算時間が再帰だけで掛かることになる。
つまり全体の計算量はO(m log^2 m)だ。
一方でループの場合にはO(m log m)掛かるから、その差はO(log m)だ。
この値はm=5000万、底2として約25だ。
つまり、理論上は再帰とループで25倍の差が開きうる。
そして君は10000倍違うと言う。
省1
315(1): 2015/12/26(土)20:09 ID:YV12MLKo(3/5) AAS
>>281
>>205
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.042s