12/01/17 12:57:57.01
>>146
ソート前のデータ全てのビット列をメモリアドレスに見立てて、
メモリの出力をソート済みの全データのビット列として取り扱うものとすればいいんじゃね
149:デフォルトの名無しさん
12/01/17 15:00:03.00
>>148
データが重複してないことが前提じゃね？
150:145
12/01/17 15:47:18.22
面倒だから数字一桁のソート(1と3と5が重複)
メモリアドレス：31415926535
↓
メモリデータ：11233455569
151:145
12/01/17 16:11:51.66
>>140
ほら、比較なしでソートできたzo
152:デフォルトの名無しさん
12/01/17 19:04:41.96
char型の値2つのソートをテーブルで実現するときそのサイズは32KB。
short型(16bit)の値2つなら16GB。char型の値4つでも16GB。今のPC事情ならメモリ上に展開できる。
int型(32bit)の値2つなら…1TBのストレージが1000円で買えたとして1475億円か。国家プロジェクトにすればいける！
153:デフォルトの名無しさん
12/01/17 21:54:31.33
チューリングマシンって無限長テープ(メモリ)だよな
ランダムアクセスできないけど
154:デフォルトの名無しさん
12/01/18 15:46:49.43
>>150
なるほど～
アイデアとしてはアリなんだな。
問題はメモリの効率化だけだな。
155: 忍法帖【Lv=3,xxxP】
12/01/19 02:46:38.42
いいね
156:デフォルトの名無しさん
12/01/20 22:33:47.52
>>153
まあ数学者は計算が有限時間で終わるかどうかにしか興味ないから
157:デフォルトの名無しさん
12/01/20 22:53:10.42
>>145
対応できる入力のサイズに上限があるからそもそもO記法の適用範囲ではない。
(データに応じてテーブルを大きくするんじゃなくて、どんなサイズのデータにも
対応できるテーブルをあらかじめ用意していないとダメ)
チューリングマシンのテープの長さは無限だけど、あらかじめ書きこんでおける
空白以外の記号は高々有限個だけ。
つまりあらかじめ用意しておけるテーブルのサイズも高々有限
158:デフォルトの名無しさん
12/01/22 17:45:39.00
>>156
んなわけないだろ、だったらＰとかＮＰとかの発想出てこねえよ
ＰだってＮＰだって有限時間で終わるけど興味の対象だろうがよ
159:デフォルトの名無しさん
12/01/22 17:47:10.56
ΩとかΘ記号の話が出てこないようじゃ話してる人のレベルが知れるな
記号はＯだけじゃないぞ
160:デフォルトの名無しさん
12/01/22 19:22:33.28
>>159
いずれの記号もnを無限に大きくできなければ適用できない
161:デフォルトの名無しさん
12/01/22 19:26:15.84
>>158
「数学者は」というのは一般化しすぎだったけど計算可能解析学のマイナーさを考えたら
大半の数学者が興味持ってないのは事実だろ。
有限時間内での計算量を扱う分野は数学ではなくて計算機科学に分類されることが多いし
162:デフォルトの名無しさん
12/01/23 15:40:36.27
>>161
多くの数学者にとっても計算時間は重要じゃね？
無限に時間を使っていいならこの世どころかあの世も含め
すべての事象は計算可能なわけだし。
163:デフォルトの名無しさん
12/01/23 20:55:50.37
>>162
またまたー
じゃあ停止問題解いてみろよ
164:デフォルトの名無しさん
12/01/23 21:50:40.32
問題を解くのに無限の時間がかかるってのは解けるって言うのか
165:デフォルトの名無しさん
12/01/26 22:18:27.41
>>163
無限時間チューリング機械なら停止問題は解けるよ
そもそも無限に時間を使っていいなんて言った覚えはないけど。
数学者は無限でなければ気にしないとは言ったが
166:デフォルトの名無しさん
12/01/30 20:12:24.96
英語版Wikipediaにはちゃんと中央値を求める線形時間アルゴリズムが載ってた
URLﾘﾝｸ(en.wikipedia.org)
わかってたことだがやっぱ日本語版はうんこだ
167:デフォルトの名無しさん
12/01/30 21:03:23.16
>>166
それじゃ、日本語版を改善してやってくれ。
168:デフォルトの名無しさん
12/01/30 21:51:36.13
日本語版「ん？」
選択アルゴリズム - Wikipedia
URLﾘﾝｸ(ja.wikipedia.org)