なあ、再帰関数好きな人いる？ パート3 [転載禁止]©2ch.net (914ﾚｽ)
なあ、再帰関数好きな人いる？ パート3 [転載禁止]©2ch.net http://mevius.5ch.net/test/read.cgi/tech/1448704298/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
281: デフォルトの名無しさん [] 2015/12/26(土) 19:14:27.33 ID:6n5NtJkM >>278 >>201 がすべてを物語っている。 これが何よりの証拠。再帰がとてつもなく効率が悪いことを つまびらかにしてみせた。ここに来て見てみぬふりは通用しない。 エビデンスもきちんと示されている。もはや知らぬ存ぜぬでは済まされない。 http://mevius.5ch.net/test/read.cgi/tech/1448704298/281
284: デフォルトの名無しさん [] 2015/12/26(土) 19:16:31.66 ID:Igcba1qr >>281 障害児くん 10000倍と130倍って、どっちがどれだけ大きいかわかる? http://mevius.5ch.net/test/read.cgi/tech/1448704298/284
286: デフォルトの名無しさん [sage] 2015/12/26(土) 19:21:05.64 ID:oIXuKyHb >>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倍違うと言う。 残り400倍はどうやって稼ぐんだい？ http://mevius.5ch.net/test/read.cgi/tech/1448704298/286
315: デフォルトの名無しさん [sage] 2015/12/26(土) 20:09:01.51 ID:YV12MLKo >>281 >>205 http://mevius.5ch.net/test/read.cgi/tech/1448704298/315
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.042s