08/05/31 15:57:02
やばい！論文書きます
2:デフォルトの名無しさん
08/05/31 15:57:45
>>3-
そーっとしておいてあげてください
3:デフォルトの名無しさん
08/05/31 16:01:07
O(1)のソートアルゴリズムがある件
4:デフォルトの名無しさん
08/05/31 16:05:02
バケツソートとか普通にあるだろ。
5:１
08/05/31 16:08:25
対象データに仮定が必要ないんだぜ
6:デフォルトの名無しさん
08/05/31 16:20:56
特許とれ。
7:デフォルトの名無しさん
08/05/31 16:20:59
こういう単純な処理は標準ライブラリに限る。
ただ、自前で実装しないといけない場合がよくある。
そういう用途のソートアルゴリズムがほしいわけです。(簡単で高速で特に欠点ないやつ)
8:デフォルトの名無しさん
08/05/31 17:01:59
夏だなあ・・・
9:デフォルトの名無しさん
08/05/31 17:40:02
もうネタ出尽してるのに人気あるよなソート
10:デフォルトの名無しさん
08/05/31 17:46:22
たまに思い出したように湧いてくるよね。
とっとと駆除しないと。
11:デフォルトの名無しさん
08/05/31 18:10:14
いや待て、古典アルゴリズムなら無理だが、
量子アルゴリズムなら可能かもしれないだろ？
>>1 は古典アルゴリズムと明言していない。
ならまだ可能性はあるんじゃないのか？
12:デフォルトの名無しさん
08/05/31 19:49:34
量子アルゴリズムが効果的に使えてその辺で買えるコンピュータがあればくれ。
13:デフォルトの名無しさん
08/05/31 20:27:10
>>12
ｽﾚﾘﾝｸ(classical板)
14:デフォルトの名無しさん
08/05/31 22:14:49
listコンテナにもつかえるsortアルゴリズムというと
バブルソートだけですか？
15:デフォルトの名無しさん
08/05/31 22:29:42
古典コンピュータ以外でのO(n)のアルゴリズムが発見されたとしても、lg(n)時間減るだけじゃなあ。
元々多項式時間なだけに価値があるかどうか。
16:デフォルトの名無しさん
08/05/31 22:36:36
>>14
マージソートとか
17:デフォルトの名無しさん
08/05/31 22:43:27
O(n)のソートを開発したぜ。ただしある特定の配列のみ適用可能。
def 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]
18:デフォルトの名無しさん
08/05/31 22:44:32
それなら、
def sort(arr)
[1,2,3]
end
でよくね？
19:デフォルトの名無しさん
08/05/31 23:28:58
ソート対象のデータに全順序以外の仮定がない場合，
ソートの計算時間の下限がO(NlogN)なのはすでに証明済みだったような？
20:デフォルトの名無しさん
08/05/31 23:29:07
双方向リストってクイックソート使えても良さそうだと思うんだけど、
何で使えないのん？
21:デフォルトの名無しさん
08/05/31 23:32:48
作ってないから。
22:デフォルトの名無しさん
08/06/01 10:39:49
>>1しょぼいな
俺なんかナップサック問題を多項式時間で解くアルゴリズムを発見したぞ。
でもそれを記述するにはこの余白はあまりにも少なすぎ
23:デフォルトの名無しさん
08/06/01 12:36:02
0-1でなきゃ貪欲法で元々多項式時間じゃないか。
24:デフォルトの名無しさん
08/06/01 13:14:15
>>23 最適解じゃないし。そんなの解いたとは言わん
25:デフォルトの名無しさん
08/06/01 13:15:54
>>22
書き始めていいよ
埋まりそうになったら次スレ用意する
26:デフォルトの名無しさん
08/06/01 13:30:45
>>24
0-1でなきゃ、の意味も掴めないのか？一般化ナップサックの話だよ
27:デフォルトの名無しさん
08/06/01 13:41:20
suckと申したか
28:デフォルトの名無しさん
08/06/01 17:30:36
卑猥だな
29:デフォルトの名無しさん
08/06/02 03:24:44
おまいら、コンビニの前でチンチンの(自己申告の)でかさを競い合ってるDQNとかわらんぞ。
30:デフォルトの名無しさん
08/06/02 15:55:20
>>26
おいおい、0-1でないと意味ないだろ。
お前、月に行くとして酸素ボンベ半分とか、拳銃0.8個とかナップザックに詰めて
持っていくのかよ。月 を な め る な
31:デフォルトの名無しさん
08/06/03 23:20:58
月に拳銃は要るのかどうかは知らんがﾜﾛﾀ
32:デフォルトの名無しさん
08/06/06 01:40:47
>>22
フェルマー乙
33:デフォルトの名無しさん
08/06/30 15:13:53
オレもありとあらゆるデータを1bitにするアルゴリズムを持ってるよ。
34:デフォルトの名無しさん
08/07/07 01:06:52
非可逆のハッシュなら俺も持ってる。
35:デフォルトの名無しさん
08/08/18 00:53:00
>>20
URLﾘﾝｸ(www.geocities.jp)
36:デフォルトの名無しさん
08/12/15 07:17:28
>>35
xyzzyの人ですか
37:デフォルトの名無しさん
08/12/15 22:47:57
>>35
別に普通にできるだろ？
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
38:デフォルトの名無しさん
08/12/16 01:06:33
要素数が少なくなったらO(N^2)に切り替えるというのも、
分割する際についでに数を数えておけば最初の１回以外は何とかなる。
std::list::sort にした方がノードの交換効率もいいし最初でもO(N^2)交換ができるが、
std::sort を使えなくする必要性はないと思われる。
39:デフォルトの名無しさん
08/12/16 01:07:24
×O(N^2)交換
○O(N^2)ソート
40:デフォルトの名無しさん
08/12/16 01:11:06
カウントはO(N)だから最初にやってしまってもいいな
41:デフォルトの名無しさん
08/12/16 20:37:44
age
42:デフォルトの名無しさん
08/12/16 21:15:02
>>38
std::sortはクイックソートである必要はないという建前だから。
例えば、最初はクイックソートするけど、
分割していって要素数が減ったら別のソートをやるということがあるでしょ。
43:デフォルトの名無しさん
08/12/16 22:13:20
>>38 はまさにその話だろ？
リストは普通にO(N^2)ソートできるから問題ない。
std::sort では要素数少ない時は
交換回数の少ない選択ソートが使われる事が多いが、
別に双方向リストでも選択ソートは可能だ。
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
44:デフォルトの名無しさん
08/12/16 22:50:06
std::sort は O(N logN) で余分なバッファを使わなければ何でもいいのだが、
まさにこれはその要件を満たしてる。
まあ、実際には pivot の扱いを変えないと std::sort としては使えないんだが、
そこは std::sort にするならそう実装すればいいってことで。
（昔書いたコードの使い回しなんで・・・）
当然 std::list::sort として実装した方が効率的なので
std::list::sort が存在することに何も問題は無いんだが、
std::sort を random access iterator に限定して
bidirectional iterator に対してわざわざ使えなくする必要性は無いよね。
45:デフォルトの名無しさん
08/12/17 01:42:19
そんなことほかにも考えているやついるんじゃないかと思ってググってみたら案の定。
URLﾘﾝｸ(www.kmonos.net)
この人の場合、クイックの後で併用するソートの計算量が良くないねという結論で終わっている。
46:デフォルトの名無しさん
08/12/17 19:39:49
なるほど。ヒープソートも使ってんのか。
それじゃしかたないかもね・・・。
47:デフォルトの名無しさん
08/12/18 00:24:05
そろそろだと思うんだ。
Big-O ショー タァーイム！！
Comb Sort11最高。
48:デフォルトの名無しさん
08/12/18 00:33:45
gap ありだと bidirectional iterator に適用し辛いな。
余計なバッファを使う必要がある。
49:デフォルトの名無しさん
08/12/18 00:38:10
シェルソートと似たようなアルゴリズムなのに
何でシェルソートより速いんだろうな。
50:デフォルトの名無しさん
08/12/18 01:13:43
コムソートは平均でも最悪でもほぼO(n log n)でしょ？
理論的限界もO(n log n)じゃなかったっけ？
実装簡単だしメモリ食わないし好きだ。
51:デフォルトの名無しさん
08/12/18 08:52:35
コムソートは欲しいときにすぐ書けるのがいい。
安定でないのが玉にキズだけど。
52:デフォルトの名無しさん
08/12/18 14:29:09
ソートって、データの全てのペア(nC2)についての
比較情報だけ（少し無駄がある）あれば、理論的にはOKだよね？
53:デフォルトの名無しさん
08/12/18 16:16:49
その比較演算が全順序関係になっていると保証できればOK
54:デフォルトの名無しさん
08/12/18 19:10:45
じゃんけん風味だと終わんないもんな
55:デフォルトの名無しさん
08/12/18 23:14:10
>>52
だから普通のソート法は最悪でもO(N^2)のオーダーなわけだ。
ボゴソートのような無茶苦茶なものは除いて・・・。
56:デフォルトの名無しさん
08/12/19 00:24:14
bidirectional iterator に適用できる
メモリ使用量 O(lonN) 以下の
最悪計算時間が O(NlogN) のソート法ってないもんかねえ・・・。
ないことが証明されてたりするのかね。
57:デフォルトの名無しさん
08/12/19 07:09:13
ボゴソートは要らない子
58:デフォルトの名無しさん
08/12/20 03:55:59
>>57
そんな彼が好きなんです。
59:デフォルトの名無しさん
09/01/20 20:49:47
ソート済みのデータでも容量がGBやTBクラスだと
どうやって取り扱ったら良いのか分かりません＞＜
60:デフォルトの名無しさん
09/01/21 05:44:47
ISAMとか真似すれば？
61:デフォルトの名無しさん
09/01/31 15:46:45
B木とかそういうので扱えばいいんじゃないかな
62:デフォルトの名無しさん
09/03/30 17:19:20
shear sortって、wikipedia日本語版では「シェアソート」って紹介されてるのね。
どう聞いても「シア」にしか聞こえないんだけど、「シェアソート」になった由来は何かあるのかな?
# 最近話題の「ウィンド･シア」の方はシェアとは言わんよね。
## あっちの業界はあっちの業界で、「porpoise」を妙ちきりんな読み方しているけど。
63:デフォルトの名無しさん
09/03/30 17:25:45
シェルソートにひきずられたかなぁ？
まぁ古いアルゴリズムとかは妙なカタカナが定着してたりすることは
よくあること...だけど、活字で残ってる用例あるかなぁ。あまり紹介
されないソートだし。てか今知った。
64:デフォルトの名無しさん
09/04/05 21:41:56
最初に訳した奴がバカだったんだろう
そういうのあるよね
65:デフォルトの名無しさん
09/04/05 23:03:28
ねーよｗ
66:デフォルトの名無しさん
09/04/06 09:28:09
ウィキペディアだとありそうだな。
どうもウィキペディアを勉強ノート代わりにしたっぽい奴が書いた項目を見つけて
頭が痛いところだったり。
67:デフォルトの名無しさん
09/04/06 23:54:34
直してあげな。
68:62
09/04/07 01:40:48
いやぁ、なんか理由があるのかと思って躊躇していたのさ。
誰も直さないようなら、今度暇なときにでも直しておくよ。
69:デフォルトの名無しさん
09/04/07 08:53:42
Googleで検索する限りでは、シアソートって書いてるページ、ほとんどないぞ？
70:デフォルトの名無しさん
09/04/07 09:04:19
シェアソートって書いてあるページも、多くはWikipediaを参照している罠。
71:デフォルトの名無しさん
09/04/07 10:32:03
『アルゴリズム辞典』に載ってればそれに従うところだが、載ってないんだよな。
TAOCPはどうだろう。
72:デフォルトの名無しさん
09/09/19 16:19:09
あらかじめソートされた結果を知っていれば
たとえ
ボゴソートとかであっても恣意的な神の手を加えることにより
ものすごい低いオーダーを実現できるよねｗ
73:デフォルトの名無しさん
09/09/19 20:26:46
安定でマージソートより優秀なのは何？
74:デフォルトの名無しさん
09/09/19 20:30:58
クレオソート
75:デフォルトの名無しさん
09/09/19 20:34:53
バケツソート
76:デフォルトの名無しさん
09/09/19 22:30:43
>>72
ソート済のデータを渡せばO(1)
77:デフォルトの名無しさん
09/09/19 22:50:02
汎用ソートの場合、ifを使わずにreturn a-bとかで直接返した方が効率いいんだろうな。
strcmpやmemcmpとかも使って。可読性は知らんが。
78:デフォルトの名無しさん
09/09/25 13:43:12
>>77
例えばint型のときにreturn a-bなんてしたら、値域が限定されて汎用じゃなくなるよ。
79:デフォルトの名無しさん
09/09/26 09:08:48
それはint型の比較関数としてreturn a-bがふさわしくないから。
ソートの汎用性とは関係ない。
比較関数は比較する型ごとに作るんだよ？わかる？
80:デフォルトの名無しさん
09/09/26 09:21:19
こいつわかってないわ
81:デフォルトの名無しさん
09/09/26 19:00:14
∧＿∧ ／￣￣￣￣￣
（ ‘∀‘）＜ オマエガナー
（ ） ＼＿＿＿＿＿
｜ ｜ |
（_＿）＿）
82:デフォルトの名無しさん
09/09/28 11:16:59
つまり、a-bって書くとunsigned同士は勿論、signed同士でも巧くないってことか。
83:デフォルトの名無しさん
09/09/28 22:25:06
int全体の比較関数をa-bと書くのはアホだろ。
単なるバグだし。
84:デフォルトの名無しさん
09/09/29 22:45:49
20億近くまで数字が分布するようなアプリのが少ないから問題ないだろ。
お金周りのアプリなら8バイトなり古典小数点数ライブラリなり使うだろうし。
85:デフォルトの名無しさん
09/09/29 22:46:36
×古典 ○固定
86:デフォルトの名無しさん
09/09/29 23:02:20
会計処理で重要なのは、固定小数点ではなく、十進演算であること
87:デフォルトの名無しさん
09/09/29 23:18:18
JavaのBigDecimalは十進演算だったのか。
言われてJavaDoc覗いて初めて気付いたｗ
88:デフォルトの名無しさん
09/09/29 23:20:26
いや、Decimalって書いてるだろｗ
89:デフォルトの名無しさん
09/09/30 09:51:14
>>84
問題は、その発想のままshort intにまで適用してしまう可能性があることだな。
90:デフォルトの名無しさん
09/11/05 02:26:40
return (a>b)-(a<b);
91:デフォルトの名無しさん
09/11/05 02:31:26
>>87-88
92:デフォルトの名無しさん
09/11/12 19:54:04
表示する時の演算コストを考えてんだろうね
93:デフォルトの名無しさん
09/11/26 14:59:05
Ruby 1.9 And Rails 3.0
URLﾘﾝｸ(www.slideshare.net)
94:デフォルトの名無しさん
11/04/25 16:06:08.96
なんでボゾソートがボゴソートより速いのか理解できない
95:天使 ◆uL5esZLBSE
11/07/05 05:52:03.56
∨
[[[[[[[ Ruby 1.9 And Rails 3.0 ]]]]]]]（キリ!!!!キリッッッキリッッッッ!!!!
∧∧∧∧∧∧∧(←きリッッ!!
96:デフォルトの名無しさん
11/07/09 22:03:16.04
Sleep SortのスリープをCPUクロック数に置き換えたら凄いんじゃね？
しかも超マルチコア前提で
97:デフォルトの名無しさん
11/07/10 10:36:53.31
よし、O(N)のアルゴを教えてやろう。
ソート前の全組み合わせの膨大なデータを分散ストレージに用意しておくんだ。
ソート処理ではハッシュを計算するだけ。
98:デフォルトの名無しさん
11/07/17 22:33:02.74
>>97
それってビンソートとどこが違うの？
99:デフォルトの名無しさん
11/09/18 22:54:53.45
クイックソートをマルチスレッド化したらどれくらい速くなるかなあ？
分割する度に片方の群を別スレッドに渡していくような処理を考えたんだけど
もちろん要素数が少ない時はスレッド分割なしにして
メモリアクセス性能次第かな
100:デフォルトの名無しさん
11/09/18 23:27:10.01
>>99
TSV DRAMが普及するまで待て
現在のDRAMの構造ではマルチコアの性能を最大限に発揮出来ない
101:デフォルトの名無しさん
11/09/25 11:28:06.98
URLﾘﾝｸ(www.speedtest.net)
102:デフォルトの名無しさん
11/09/25 11:30:29.92
URLﾘﾝｸ(www.speedtest.net)
103:デフォルトの名無しさん
11/09/25 11:39:38.89
URLﾘﾝｸ(www.speedtest.net)
URLﾘﾝｸ(www.speedtest.net)
URLﾘﾝｸ(www.speedtest.net)
104:デフォルトの名無しさん
11/09/25 11:59:07.68
URLﾘﾝｸ(www.speedtest.net)
URLﾘﾝｸ(www.speedtest.net)
URLﾘﾝｸ(www.speedtest.net)
URLﾘﾝｸ(www.speedtest.net)
105:デフォルトの名無しさん
11/09/25 12:46:59.94
URLﾘﾝｸ(www.speedtest.net)
106:デフォルトの名無しさん
11/10/08 11:45:01.88
保守
107:デフォルトの名無しさん
11/10/18 11:37:16.18
>>1
ソート対象の要素の序数が最初からわかっているという条件があって、ようやくO(n)となるのだが・・・
アカシックレコードでも発見したのか？
108:デフォルトの名無しさん
11/10/21 09:36:49.33
timソート
109:デフォルトの名無しさん
11/10/25 00:19:28.15
フリーの TBB でも使って組んでみたら？
110:デフォルトの名無しさん
11/11/29 13:00:20.03
>>96
その実装が見てみたいわ
111:デフォルトの名無しさん
11/11/30 12:57:12.94
>>99
粒度をどのくらいにするかだよね。マルチ化するために処理が増えるから
そのトレードオフを自動的に考えて判断させるような自動最適化ができた
上で最速を探すのって面白そうだけどな。前段階がちょっとおもそうだけど。
112:デフォルトの名無しさん
11/12/11 08:17:05.88
>>96
クロック数とか持ち出す時点でオーダー記法の意味わかってなさすぎ
113:デフォルトの名無しさん
11/12/11 11:21:38.41
お前>>96の意味わかってないだろ
114:デフォルトの名無しさん
11/12/11 16:16:40.40
クロックに合わせたスリープソートでマルチコアってできなくね？
115:デフォルトの名無しさん
11/12/11 21:40:13.84
nコアで値分だけnop発行とか?
116:デフォルトの名無しさん
11/12/11 22:00:16.82
>>115
あ、なるほど。勉強になりました。
117:デフォルトの名無しさん
11/12/11 23:19:42.22
1クロックですべてのデータを投入することが出来れば
クロックに合わせたスリープソートは実現可能。
でなければデータ投入にかかるクロックを厳密に計算しなければならない。
118:デフォルトの名無しさん
11/12/12 06:22:42.30
データ量に応じていろいろ考えないといけないね。
キャッシュミスしたら死ぬし。
119:デフォルトの名無しさん
11/12/12 22:12:37.15
つまりあれだ、SIMD的な何かがあればいいのか
SSXとか
120:デフォルトの名無しさん
11/12/17 00:23:05.91
このスレまだあったのｗｗｗ
俺が大学生の時に建てたスレだｗ
121:デフォルトの名無しさん
11/12/17 03:57:54.28
>>120
なんだ、中退したのか?
122:デフォルトの名無しさん
11/12/24 23:09:10.65
今ならGPUでバイトニックソート使うのが速さ的には一番だろうな
123:デフォルトの名無しさん
11/12/31 12:21:00.78
うんこぶりぶり。
精子ドピュッドピュ
124:デフォルトの名無しさん
12/01/06 15:18:24.61
中央値を高速に見つけたいんだけど、やっぱソートしなきゃダメかね
125:デフォルトの名無しさん
12/01/06 17:33:36.32
Wikipediaにはソートが必要だからO(nlogn)かかるって書いてあるね。
中央値 - Wikipedia URLﾘﾝｸ(ja.wikipedia.org)
以下、データ数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。
高速化自体が目的なら、データ数次第では計算量のみで必ずしも優劣が決まるというわけではないけど。
126:デフォルトの名無しさん
12/01/10 11:21:24.00
両端の極端な値を落としてだいたい真ん中らへんの値
がほしいだけだから、アバウトでいいんだけど
適当にグループ分けて中央値の中央値を取ればいいのかな
でもその時点で最後までソートしても大差なさそうだな
127:デフォルトの名無しさん
12/01/10 14:23:21.29
>>123
うわっ
俺の書き込みだわこれ
懐かしい
128:125
12/01/10 18:54:46.37
どーでもいーけど>>125の訂正。
このやりかただとO(nlogn)でFAでした。なぜなら2分探索すると次のようになるから。logの底は2。
53番目は50回、じゃなくてlog(50)回比較。
…
100番目は3回、じゃなくてlog(3)比較。
101番目は2回、じゃなくてlog(2)比較。
アバウトでいいなら計算時間が許容範囲になるまで間引くとかも考えられるけど
（合計値の）中央値の中央値とかのほうがまっとうだね。
データ数はすごく大きいのかな？
129:128
12/01/11 01:41:06.89
訂正。（合計値の）←これナシで。
130:デフォルトの名無しさん
12/01/12 23:38:01.46
>>125
それは Wikipedia が間違っている。
中央値は平均ではなく最悪O(n)で求められる。
131:デフォルトの名無しさん
12/01/14 00:50:16.48
わかりにくい文だが中央値を平均O(n)で求められるなんて書かれていないぞ。
「平均値」を求める計算量がO(n)と言ってるだけ。
とくに何も断っていなければO記法の定義から最悪値の話に決まってる。
中央値を最悪O(n)で求められるというのが本当ならどのみち間違ってるけど本当?
132:デフォルトの名無しさん
12/01/14 11:02:11.82
よく読んだらたしかに平均O(n)とも言ってないな。
平均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 の要素に絞ることができる。
133:デフォルトの名無しさん
12/01/14 11:20:44.38
(1) から (5) までにかかる時間 T(n) の内訳は
(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 が示せる。
134:デフォルトの名無しさん
12/01/14 14:13:47.68
(3)が結局O(nlogn)じゃーんそれ
135:デフォルトの名無しさん
12/01/14 14:45:20.29
いや訂正、(3)はO(n)か
136:デフォルトの名無しさん
12/01/14 16:06:19.43
結局全体ではO(nlogn)じゃーん？
O(n)の処理によって候補を最悪でも7/10に絞り込めるけど、
つまりデータ量が(10/7)倍になるごとにそのO(n)の処理をプラス1回やんなきゃいけなくなるわけだから。
137:デフォルトの名無しさん
12/01/14 16:49:05.32
>>136
5で割り切れないときとかを端折って証明も添えたけど
理解できないか？
その辺の教科書によく書いてある有名な話だよ。
実際は、重いピボット選択を適当にサボるほうが平均的には速い。
gcc の nth_element の実装はサボってる。
(だから平均 O(n), 最悪 O(nlogn))
138:136
12/01/14 17:32:24.11
>>137
証明って、十分大きい数を用意する話はそもそも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の一次式で表現されるって解釈でいいんでしょうか？
139:デフォルトの名無しさん
12/01/14 17:42:48.66
あー失礼T(n/5)の意味がわかりました、漸化式みたいなもんだったんですね。
140:デフォルトの名無しさん
12/01/15 18:39:40.87
ちょっとでも数学を知っていればO(n)なんてあり得ないこと位、理解できそうなもんだ
O(n)であるということは、各々のデータの順位を求める処理の量がnの値に関係なく一定であることを意味している
つまりデータ同士の比較(これの処理量はｎの値に相関する)を使うことはできないということ
ではどうする？お前らに問いたい
141:デフォルトの名無しさん
12/01/16 18:32:57.16
>>140
バケットソートはO(n)なんだが。
なにごとも前提しだいと言うことだ。
142:デフォルトの名無しさん
12/01/16 20:33:31.15
バケツソートは「比較によらないソート」であって、一般にソートと言えば
比較によるソートのことだからな。
143:デフォルトの名無しさん
12/01/16 22:19:53.56
ソーティングの下界はnlognだと証明されてる
144:デフォルトの名無しさん
12/01/17 07:55:22.96
未来予知するアルゴリズムがあればO(n)を実現できるよ
145:デフォルトの名無しさん
12/01/17 08:09:52.41
テーブル展開してしまえばO(1)だよ、使用メモリは宇宙の全ての物質を使っても全然足りないけどなｗｗｗ
146:デフォルトの名無しさん
12/01/17 11:56:53.50
>>145
O(n)の間違いじゃね？
147:デフォルトの名無しさん
12/01/17 11:57:49.99
>>142
ではどうする？ に対して言ってるのに何を言ってんだお前は。
バカじゃないのか？ アホなのか？
148:145
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)