O（n)のソートアルゴリズムを発見した
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2008/05/31(土) 15:57:020002デフォルトの名無しさん
2008/05/31(土) 15:57:45そーっとしておいてあげてください
0003デフォルトの名無しさん
2008/05/31(土) 16:01:070004デフォルトの名無しさん
2008/05/31(土) 16:05:020005１
2008/05/31(土) 16:08:250006デフォルトの名無しさん
2008/05/31(土) 16:20:560007デフォルトの名無しさん
2008/05/31(土) 16:20:59ただ、自前で実装しないといけない場合がよくある。
そういう用途のソートアルゴリズムがほしいわけです。(簡単で高速で特に欠点ないやつ)
0008デフォルトの名無しさん
2008/05/31(土) 17:01:590009デフォルトの名無しさん
2008/05/31(土) 17:40:020010デフォルトの名無しさん
2008/05/31(土) 17:46:22とっとと駆除しないと。
0011デフォルトの名無しさん
2008/05/31(土) 18:10:14量子アルゴリズムなら可能かもしれないだろ？
>>1 は古典アルゴリズムと明言していない。
ならまだ可能性はあるんじゃないのか？
0012デフォルトの名無しさん
2008/05/31(土) 19:49:340013デフォルトの名無しさん
2008/05/31(土) 20:27:10http://music8.2ch.net/test/read.cgi/classical/1211529290/
0014デフォルトの名無しさん
2008/05/31(土) 22:14:49バブルソートだけですか？
0015デフォルトの名無しさん
2008/05/31(土) 22:29:42元々多項式時間なだけに価値があるかどうか。
0016デフォルトの名無しさん
2008/05/31(土) 22:36:36マージソートとか
0017デフォルトの名無しさん
2008/05/31(土) 22:43:27def sort(arr)
for i in 0..arr.length-2
if arr[i] > arr[i+1]
raise "not sorted!"
end
end
return arr
end
sort [1,2,3]
0018デフォルトの名無しさん
2008/05/31(土) 22:44:32def sort(arr)
[1,2,3]
end
でよくね？
0019デフォルトの名無しさん
2008/05/31(土) 23:28:58ソートの計算時間の下限がO(NlogN)なのはすでに証明済みだったような？
0020デフォルトの名無しさん
2008/05/31(土) 23:29:07何で使えないのん？
0021デフォルトの名無しさん
2008/05/31(土) 23:32:480022デフォルトの名無しさん
2008/06/01(日) 10:39:49俺なんかナップサック問題を多項式時間で解くアルゴリズムを発見したぞ。
でもそれを記述するにはこの余白はあまりにも少なすぎ
0023デフォルトの名無しさん
2008/06/01(日) 12:36:020024デフォルトの名無しさん
2008/06/01(日) 13:14:150025デフォルトの名無しさん
2008/06/01(日) 13:15:54書き始めていいよ
埋まりそうになったら次スレ用意する
0026デフォルトの名無しさん
2008/06/01(日) 13:30:450-1でなきゃ、の意味も掴めないのか？一般化ナップサックの話だよ
0027デフォルトの名無しさん
2008/06/01(日) 13:41:200028デフォルトの名無しさん
2008/06/01(日) 17:30:360029デフォルトの名無しさん
2008/06/02(月) 03:24:440030デフォルトの名無しさん
2008/06/02(月) 15:55:20おいおい、0-1でないと意味ないだろ。
お前、月に行くとして酸素ボンベ半分とか、拳銃0.8個とかナップザックに詰めて
持っていくのかよ。月 を な め る な
0031デフォルトの名無しさん
2008/06/03(火) 23:20:580032デフォルトの名無しさん
2008/06/06(金) 01:40:47フェルマー乙
0033デフォルトの名無しさん
2008/06/30(月) 15:13:530034デフォルトの名無しさん
2008/07/07(月) 01:06:520035デフォルトの名無しさん
2008/08/18(月) 00:53:00ttp://www.geocities.jp/m_hiroi/light/pyalgo08.html
0036デフォルトの名無しさん
2008/12/15(月) 07:17:28xyzzyの人ですか
0037デフォルトの名無しさん
2008/12/15(月) 22:47:57別に普通にできるだろ？
ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8332.txt
0038デフォルトの名無しさん
2008/12/16(火) 01:06:33分割する際についでに数を数えておけば最初の１回以外は何とかなる。
std::list::sort にした方がノードの交換効率もいいし最初でもO(N^2)交換ができるが、
std::sort を使えなくする必要性はないと思われる。
0039デフォルトの名無しさん
2008/12/16(火) 01:07:24○O(N^2)ソート
0040デフォルトの名無しさん
2008/12/16(火) 01:11:060041デフォルトの名無しさん
2008/12/16(火) 20:37:440042デフォルトの名無しさん
2008/12/16(火) 21:15:02std::sortはクイックソートである必要はないという建前だから。
例えば、最初はクイックソートするけど、
分割していって要素数が減ったら別のソートをやるということがあるでしょ。
0043デフォルトの名無しさん
2008/12/16(火) 22:13:20リストは普通にO(N^2)ソートできるから問題ない。
std::sort では要素数少ない時は
交換回数の少ない選択ソートが使われる事が多いが、
別に双方向リストでも選択ソートは可能だ。
ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8359.txt
0044デフォルトの名無しさん
2008/12/16(火) 22:50:06まさにこれはその要件を満たしてる。
まあ、実際には pivot の扱いを変えないと std::sort としては使えないんだが、
そこは std::sort にするならそう実装すればいいってことで。
（昔書いたコードの使い回しなんで・・・）
当然 std::list::sort として実装した方が効率的なので
std::list::sort が存在することに何も問題は無いんだが、
std::sort を random access iterator に限定して
bidirectional iterator に対してわざわざ使えなくする必要性は無いよね。
0045デフォルトの名無しさん
2008/12/17(水) 01:42:19http://www.kmonos.net/wlog/68.html#_2116061224
この人の場合、クイックの後で併用するソートの計算量が良くないねという結論で終わっている。
0046デフォルトの名無しさん
2008/12/17(水) 19:39:49それじゃしかたないかもね・・・。
0047デフォルトの名無しさん
2008/12/18(木) 00:24:05Big-O ショー タァーイム！！
Comb Sort11最高。
0048デフォルトの名無しさん
2008/12/18(木) 00:33:45余計なバッファを使う必要がある。
0049デフォルトの名無しさん
2008/12/18(木) 00:38:10何でシェルソートより速いんだろうな。
0050デフォルトの名無しさん
2008/12/18(木) 01:13:43理論的限界もO(n log n)じゃなかったっけ？
実装簡単だしメモリ食わないし好きだ。
0051デフォルトの名無しさん
2008/12/18(木) 08:52:35安定でないのが玉にキズだけど。
0052デフォルトの名無しさん
2008/12/18(木) 14:29:09比較情報だけ（少し無駄がある）あれば、理論的にはOKだよね？
0053デフォルトの名無しさん
2008/12/18(木) 16:16:490054デフォルトの名無しさん
2008/12/18(木) 19:10:450055デフォルトの名無しさん
2008/12/18(木) 23:14:10だから普通のソート法は最悪でもO(N^2)のオーダーなわけだ。
ボゴソートのような無茶苦茶なものは除いて・・・。
0056デフォルトの名無しさん
2008/12/19(金) 00:24:14メモリ使用量 O(lonN) 以下の
最悪計算時間が O(NlogN) のソート法ってないもんかねえ・・・。
ないことが証明されてたりするのかね。
0057デフォルトの名無しさん
2008/12/19(金) 07:09:130058デフォルトの名無しさん
2008/12/20(土) 03:55:59そんな彼が好きなんです。
0059デフォルトの名無しさん
2009/01/20(火) 20:49:47どうやって取り扱ったら良いのか分かりません＞＜
0060デフォルトの名無しさん
2009/01/21(水) 05:44:470061デフォルトの名無しさん
2009/01/31(土) 15:46:450062デフォルトの名無しさん
2009/03/30(月) 17:19:20どう聞いても「シア」にしか聞こえないんだけど、「シェアソート」になった由来は何かあるのかな?
# 最近話題の「ウィンド･シア」の方はシェアとは言わんよね。
## あっちの業界はあっちの業界で、「porpoise」を妙ちきりんな読み方しているけど。
0063デフォルトの名無しさん
2009/03/30(月) 17:25:45まぁ古いアルゴリズムとかは妙なカタカナが定着してたりすることは
よくあること...だけど、活字で残ってる用例あるかなぁ。あまり紹介
されないソートだし。てか今知った。
0064デフォルトの名無しさん
2009/04/05(日) 21:41:56そういうのあるよね
0065デフォルトの名無しさん
2009/04/05(日) 23:03:280066デフォルトの名無しさん
2009/04/06(月) 09:28:09どうもウィキペディアを勉強ノート代わりにしたっぽい奴が書いた項目を見つけて
頭が痛いところだったり。
0067デフォルトの名無しさん
2009/04/06(月) 23:54:34006862
2009/04/07(火) 01:40:48誰も直さないようなら、今度暇なときにでも直しておくよ。
0069デフォルトの名無しさん
2009/04/07(火) 08:53:420070デフォルトの名無しさん
2009/04/07(火) 09:04:190071デフォルトの名無しさん
2009/04/07(火) 10:32:03TAOCPはどうだろう。
0072デフォルトの名無しさん
2009/09/19(土) 16:19:09たとえ
ボゴソートとかであっても恣意的な神の手を加えることにより
ものすごい低いオーダーを実現できるよねｗ
0073デフォルトの名無しさん
2009/09/19(土) 20:26:460074デフォルトの名無しさん
2009/09/19(土) 20:30:580075デフォルトの名無しさん
2009/09/19(土) 20:34:530076デフォルトの名無しさん
2009/09/19(土) 22:30:43ソート済のデータを渡せばO(1)
0077デフォルトの名無しさん
2009/09/19(土) 22:50:02strcmpやmemcmpとかも使って。可読性は知らんが。
0078デフォルトの名無しさん
2009/09/25(金) 13:43:12例えばint型のときにreturn a-bなんてしたら、値域が限定されて汎用じゃなくなるよ。
0079デフォルトの名無しさん
2009/09/26(土) 09:08:48ソートの汎用性とは関係ない。
比較関数は比較する型ごとに作るんだよ？わかる？
0080デフォルトの名無しさん
2009/09/26(土) 09:21:190081デフォルトの名無しさん
2009/09/26(土) 19:00:14（ ‘∀‘）＜ オマエガナー
（ ） ＼＿＿＿＿＿
｜ ｜ |
（_＿）＿）
0082デフォルトの名無しさん
2009/09/28(月) 11:16:590083デフォルトの名無しさん
2009/09/28(月) 22:25:06単なるバグだし。
0084デフォルトの名無しさん
2009/09/29(火) 22:45:49お金周りのアプリなら8バイトなり古典小数点数ライブラリなり使うだろうし。
0085デフォルトの名無しさん
2009/09/29(火) 22:46:360086デフォルトの名無しさん
2009/09/29(火) 23:02:200087デフォルトの名無しさん
2009/09/29(火) 23:18:18言われてJavaDoc覗いて初めて気付いたｗ
0088デフォルトの名無しさん
2009/09/29(火) 23:20:260089デフォルトの名無しさん
2009/09/30(水) 09:51:14問題は、その発想のままshort intにまで適用してしまう可能性があることだな。
0090デフォルトの名無しさん
2009/11/05(木) 02:26:400091デフォルトの名無しさん
2009/11/05(木) 02:31:260092デフォルトの名無しさん
2009/11/12(木) 19:54:040093デフォルトの名無しさん
2009/11/26(木) 14:59:05http://www.slideshare.net/arrrrcamp/ruby-19-and-rails-30
0094デフォルトの名無しさん
2011/04/25(月) 16:06:08.960095天使 ◆uL5esZLBSE
2011/07/05(火) 05:52:03.56[[[[[[[ Ruby 1.9 And Rails 3.0 ]]]]]]]（キリ!!!!キリッッッキリッッッッ!!!!
∧∧∧∧∧∧∧(←きリッッ!!
0096デフォルトの名無しさん
2011/07/09(土) 22:03:16.04しかも超マルチコア前提で
0097デフォルトの名無しさん
2011/07/10(日) 10:36:53.31ソート前の全組み合わせの膨大なデータを分散ストレージに用意しておくんだ。
ソート処理ではハッシュを計算するだけ。
0098デフォルトの名無しさん
2011/07/17(日) 22:33:02.74それってビンソートとどこが違うの？
0099デフォルトの名無しさん
2011/09/18(日) 22:54:53.45分割する度に片方の群を別スレッドに渡していくような処理を考えたんだけど
もちろん要素数が少ない時はスレッド分割なしにして
メモリアクセス性能次第かな
0100デフォルトの名無しさん
2011/09/18(日) 23:27:10.01TSV DRAMが普及するまで待て
現在のDRAMの構造ではマルチコアの性能を最大限に発揮出来ない
0101デフォルトの名無しさん
2011/09/25(日) 11:28:06.980102デフォルトの名無しさん
2011/09/25(日) 11:30:29.920103デフォルトの名無しさん
2011/09/25(日) 11:39:38.89http://www.speedtest.net/result/1500563768.png
http://www.speedtest.net/result/1500561067.png
0104デフォルトの名無しさん
2011/09/25(日) 11:59:07.68http://www.speedtest.net/result/1500563768.png
http://www.speedtest.net/result/1500561067.png
http://www.speedtest.net/result/1326987708.png
0105デフォルトの名無しさん
2011/09/25(日) 12:46:59.940106デフォルトの名無しさん
2011/10/08(土) 11:45:01.880107デフォルトの名無しさん
2011/10/18(火) 11:37:16.18ソート対象の要素の序数が最初からわかっているという条件があって、ようやくO(n)となるのだが・・・
アカシックレコードでも発見したのか？
0108デフォルトの名無しさん
2011/10/21(金) 09:36:49.330109デフォルトの名無しさん
2011/10/25(火) 00:19:28.150110デフォルトの名無しさん
2011/11/29(火) 13:00:20.03その実装が見てみたいわ
0111デフォルトの名無しさん
2011/11/30(水) 12:57:12.94粒度をどのくらいにするかだよね。マルチ化するために処理が増えるから
そのトレードオフを自動的に考えて判断させるような自動最適化ができた
上で最速を探すのって面白そうだけどな。前段階がちょっとおもそうだけど。
0112デフォルトの名無しさん
2011/12/11(日) 08:17:05.88クロック数とか持ち出す時点でオーダー記法の意味わかってなさすぎ
0113デフォルトの名無しさん
2011/12/11(日) 11:21:38.410114デフォルトの名無しさん
2011/12/11(日) 16:16:40.400115デフォルトの名無しさん
2011/12/11(日) 21:40:13.840116デフォルトの名無しさん
2011/12/11(日) 22:00:16.82あ、なるほど。勉強になりました。
0117デフォルトの名無しさん
2011/12/11(日) 23:19:42.22クロックに合わせたスリープソートは実現可能。
でなければデータ投入にかかるクロックを厳密に計算しなければならない。
0118デフォルトの名無しさん
2011/12/12(月) 06:22:42.30キャッシュミスしたら死ぬし。
0119デフォルトの名無しさん
2011/12/12(月) 22:12:37.15SSXとか
0120デフォルトの名無しさん
2011/12/17(土) 00:23:05.91俺が大学生の時に建てたスレだｗ
0121デフォルトの名無しさん
2011/12/17(土) 03:57:54.28なんだ、中退したのか?
0122デフォルトの名無しさん
2011/12/24(土) 23:09:10.650123デフォルトの名無しさん
2011/12/31(土) 12:21:00.78精子ドピュッドピュ
0124デフォルトの名無しさん
2012/01/06(金) 15:18:24.610125デフォルトの名無しさん
2012/01/06(金) 17:33:36.32中央値 - Wikipedia http://ja.wikipedia.org/wiki/%E4%B8%AD%E5%A4%AE%E5%80%A4
以下、データ数nが奇数だという前提の下でソートから省ける処理がないか考えてみた。
n-1個のソートされたデータに対してn番目のデータを追加するとき、
中央値を得るだけが目的ならば暫定中央値候補2つとの比較だけすればいい。
時間を戻して、同様にn-2個のソートされたデータに対してn-1番目,n番目のデータを
追加することを考えると、n-1番目のデータは暫定中央値候補3つとの比較だけでよい。
nを101だとすると、52番目までは普通にソート。
53番目は50回比較。
…
100番目は3回比較。
101番目は2回比較。
…ダメか。(n+3)/2個のデータのソートは必要なので、
係数は変化するかもしれんが計算量がO(nlogn)であることからは逃れられん
っていうかむしろO(n^2)の部分を含んでるしorz。
高速化自体が目的なら、データ数次第では計算量のみで必ずしも優劣が決まるというわけではないけど。
0126デフォルトの名無しさん
2012/01/10(火) 11:21:24.00がほしいだけだから、アバウトでいいんだけど
適当にグループ分けて中央値の中央値を取ればいいのかな
でもその時点で最後までソートしても大差なさそうだな
0127デフォルトの名無しさん
2012/01/10(火) 14:23:21.29うわっ
俺の書き込みだわこれ
懐かしい
0128125
2012/01/10(火) 18:54:46.37このやりかただとO(nlogn)でFAでした。なぜなら2分探索すると次のようになるから。logの底は2。
53番目は50回、じゃなくてlog(50)回比較。
…
100番目は3回、じゃなくてlog(3)比較。
101番目は2回、じゃなくてlog(2)比較。
アバウトでいいなら計算時間が許容範囲になるまで間引くとかも考えられるけど
（合計値の）中央値の中央値とかのほうがまっとうだね。
データ数はすごく大きいのかな？
0129128
2012/01/11(水) 01:41:06.890130デフォルトの名無しさん
2012/01/12(木) 23:38:01.46それは Wikipedia が間違っている。
中央値は平均ではなく最悪O(n)で求められる。
0131デフォルトの名無しさん
2012/01/14(土) 00:50:16.48「平均値」を求める計算量がO(n)と言ってるだけ。
とくに何も断っていなければO記法の定義から最悪値の話に決まってる。
中央値を最悪O(n)で求められるというのが本当ならどのみち間違ってるけど本当?
0132デフォルトの名無しさん
2012/01/14(土) 11:02:11.82平均O(n)でいいなら std::nth_element でいいし、最悪O(n)が欲しいなら以下:
(1) a_0,...,a_{n-1} を D個ずつ(ここではD=5) のグループに分ける:
a_0, a_1, a_2, a_3, a_4 | a_5, a_6, a_7, a_8, a_9 | a_10, ...
(2) 各グループのメディアンを求める。
求めたメディアン m_i は、各グループの先頭要素と交換しておく。
(3) ストライド 5 にして (m_i だけを見るようにして) 再帰し、m_i のメディアン M をもとめる。
(4) M をピボットにして quick sort 的な分割を行う。
(5) 求めたい順位が含まれるほうへ再帰。
ピボットの選び方を工夫しているので、(5) では多くても 7n/10 の要素に絞ることができる。
0133デフォルトの名無しさん
2012/01/14(土) 11:20:44.38(2) と (4) は Kn (K は定数)
(3) は n/5 個の要素で再帰するので T(n/5)
(5) は多くても T(7n/10)
よって T(n) < Kn + T(n/5) + T(7n/10)
n をある有限の範囲内 (たとえば n < 100) のときに限れば、
十分大きい定数 L を持ってきてT(n) < Ln たらしめることができる。
そこで、L をあらかじめ巨大にとっておけば (K << L になるように)
帰納法によって任意のnに関し T(n) < Kn + 9/10 Ln < Ln が示せる。
0134デフォルトの名無しさん
2012/01/14(土) 14:13:47.680135デフォルトの名無しさん
2012/01/14(土) 14:45:20.290136デフォルトの名無しさん
2012/01/14(土) 16:06:19.43O(n)の処理によって候補を最悪でも7/10に絞り込めるけど、
つまりデータ量が(10/7)倍になるごとにそのO(n)の処理をプラス1回やんなきゃいけなくなるわけだから。
0137デフォルトの名無しさん
2012/01/14(土) 16:49:05.325で割り切れないときとかを端折って証明も添えたけど
理解できないか？
その辺の教科書によく書いてある有名な話だよ。
実際は、重いピボット選択を適当にサボるほうが平均的には速い。
gcc の nth_element の実装はサボってる。
(だから平均 O(n), 最悪 O(nlogn))
0138136
2012/01/14(土) 17:32:24.11証明って、十分大きい数を用意する話はそもそもO記法の表現には関係なくないですか？
＞Kn + T(n/5) + T(7n/10)
いわゆる”O(n/5)”も”O(7n/10)”も全部O(n)ですから、
「この計算時間はKn + T(n/5) + T(7n/10) 」→「このアルゴリズムはO(n)」
の→(ならば)の部分には異存はないんです。ただそもそも計算時間はそれじゃないんじゃないかというのが>>136です。
俺が誤解してるとしたらT(n/5)の意味ですが、これってTの値がn/5の一次式で表現されるって解釈でいいんでしょうか？
0139デフォルトの名無しさん
2012/01/14(土) 17:42:48.660140デフォルトの名無しさん
2012/01/15(日) 18:39:40.87O(n)であるということは、各々のデータの順位を求める処理の量がnの値に関係なく一定であることを意味している
つまりデータ同士の比較(これの処理量はｎの値に相関する)を使うことはできないということ
ではどうする？お前らに問いたい
0141デフォルトの名無しさん
2012/01/16(月) 18:32:57.16バケットソートはO(n)なんだが。
なにごとも前提しだいと言うことだ。
0142デフォルトの名無しさん
2012/01/16(月) 20:33:31.15比較によるソートのことだからな。
0143デフォルトの名無しさん
2012/01/16(月) 22:19:53.560144デフォルトの名無しさん
2012/01/17(火) 07:55:22.960145デフォルトの名無しさん
2012/01/17(火) 08:09:52.410146デフォルトの名無しさん
2012/01/17(火) 11:56:53.50O(n)の間違いじゃね？
0147デフォルトの名無しさん
2012/01/17(火) 11:57:49.99ではどうする？ に対して言ってるのに何を言ってんだお前は。
バカじゃないのか？ アホなのか？
0148145
2012/01/17(火) 12:57:57.01ソート前のデータ全てのビット列をメモリアドレスに見立てて、
メモリの出力をソート済みの全データのビット列として取り扱うものとすればいいんじゃね
0149デフォルトの名無しさん
2012/01/17(火) 15:00:03.00データが重複してないことが前提じゃね？
0150145
2012/01/17(火) 15:47:18.22メモリアドレス：31415926535
↓
メモリデータ：11233455569
0151145
2012/01/17(火) 16:11:51.66ほら、比較なしでソートできたzo
0152デフォルトの名無しさん
2012/01/17(火) 19:04:41.96short型(16bit)の値2つなら16GB。char型の値4つでも16GB。今のPC事情ならメモリ上に展開できる。
int型(32bit)の値2つなら…1TBのストレージが1000円で買えたとして1475億円か。国家プロジェクトにすればいける！
0153デフォルトの名無しさん
2012/01/17(火) 21:54:31.33ランダムアクセスできないけど
0154デフォルトの名無しさん
2012/01/18(水) 15:46:49.43なるほど〜
アイデアとしてはアリなんだな。
問題はメモリの効率化だけだな。
0156デフォルトの名無しさん
2012/01/20(金) 22:33:47.52まあ数学者は計算が有限時間で終わるかどうかにしか興味ないから
0157デフォルトの名無しさん
2012/01/20(金) 22:53:10.42対応できる入力のサイズに上限があるからそもそもO記法の適用範囲ではない。
(データに応じてテーブルを大きくするんじゃなくて、どんなサイズのデータにも
対応できるテーブルをあらかじめ用意していないとダメ)
チューリングマシンのテープの長さは無限だけど、あらかじめ書きこんでおける
空白以外の記号は高々有限個だけ。
つまりあらかじめ用意しておけるテーブルのサイズも高々有限
0158デフォルトの名無しさん
2012/01/22(日) 17:45:39.00んなわけないだろ、だったらＰとかＮＰとかの発想出てこねえよ
ＰだってＮＰだって有限時間で終わるけど興味の対象だろうがよ
0159デフォルトの名無しさん
2012/01/22(日) 17:47:10.56記号はＯだけじゃないぞ
0160デフォルトの名無しさん
2012/01/22(日) 19:22:33.28いずれの記号もnを無限に大きくできなければ適用できない
0161デフォルトの名無しさん
2012/01/22(日) 19:26:15.84「数学者は」というのは一般化しすぎだったけど計算可能解析学のマイナーさを考えたら
大半の数学者が興味持ってないのは事実だろ。
有限時間内での計算量を扱う分野は数学ではなくて計算機科学に分類されることが多いし
0162デフォルトの名無しさん
2012/01/23(月) 15:40:36.27多くの数学者にとっても計算時間は重要じゃね？
無限に時間を使っていいならこの世どころかあの世も含め
すべての事象は計算可能なわけだし。
0163デフォルトの名無しさん
2012/01/23(月) 20:55:50.37またまたー
じゃあ停止問題解いてみろよ
0164デフォルトの名無しさん
2012/01/23(月) 21:50:40.320165デフォルトの名無しさん
2012/01/26(木) 22:18:27.41無限時間チューリング機械なら停止問題は解けるよ
そもそも無限に時間を使っていいなんて言った覚えはないけど。
数学者は無限でなければ気にしないとは言ったが
0166デフォルトの名無しさん
2012/01/30(月) 20:12:24.96https://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm
わかってたことだがやっぱ日本語版はうんこだ
0167デフォルトの名無しさん
2012/01/30(月) 21:03:23.16それじゃ、日本語版を改善してやってくれ。
0168デフォルトの名無しさん
2012/01/30(月) 21:51:36.13選択アルゴリズム - Wikipedia
http://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
■ このスレッドは過去ログ倉庫に格納されています