なあ、再帰関数好きな人いる？ パート3 [転載禁止]©2ch.net (914ﾚｽ)
なあ、再帰関数好きな人いる？ パート3 [転載禁止]©2ch.net http://mevius.5ch.net/test/read.cgi/tech/1448704298/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
ﾘﾛｰﾄﾞ規制
です｡10分ほどで解除するので､
他のﾌﾞﾗｳｻﾞ
へ避難してください｡
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
291: デフォルトの名無しさん [] 2015/12/26(土) 19:23:54.44 ID:6n5NtJkM >>286 クイックソートを実装して試したのか？あ？ だれが実装するかと言っていたのと矛盾するだろうが。 つまり、君は嘘をついている。ゆえに俺が言ってることの方が正しい。はい論破。 http://mevius.5ch.net/test/read.cgi/tech/1448704298/291
371: デフォルトの名無しさん [sage] 2015/12/27(日) 11:22:49.99 ID:Zmrinoji >>368 お前の中ではそうなんだろうな。そんな事より現実を見ろよ。 大本の彼らの主張は「クイックソートをお題にした場合に於いて再帰はループに比べて何万倍も差がでる(>>219)」 俺らの主張は「そんなに差がでることは理論的にありえない(>>286)」 であって、 ループのほうが再帰より「僅かでも」速いかどうか(>>352-353)なんざ元々議論していない。 クイックソートをやる上で比較にならないほど再帰のほうが遅くなるというならソースを出せや http://mevius.5ch.net/test/read.cgi/tech/1448704298/371
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.034s