作者yauhh (哟)
看板Prob_Solve
标题Re: [问题] 想要请教Shear sort
时间Mon Jun 1 19:58:14 2009
※ 引述《sakurarain (茫然不知所以)》之铭言：
: 不知道是不是有谁可以跟我大略讲解一下这是个怎样的演算法?
: 像是这个sort是如何做到的?时间复杂度那些方面的
: 或是有中文的网页可以提供来让小女子慢慢去研究就更好了
看了一点点,大意是说
要排 n 笔资料,是把资料排列成 n^(0.5) * n^(0.5) 方阵,
然後做 k 次以下步骤,据说这个 k 可以是 log_2 n + 1.
这 k 次分成单数次和偶数次,单数次将奇数列从右向左排序,将偶数列从左向右排序.
偶数次将每一行从上向下排序.
然後,时间复杂度起码是从 n^(0.5) 算起,而不是从 n 算起了.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.160.113.142
1F：推 seanwu:它是因为可以平行计算所以才能有n^0.5的吧? 06/01 23:50
2F：→ yauhh:意思是说,也许总共用2*n^(0.5)个node处理排序工作吗? 06/02 00:22
3F：→ yauhh:其中n^(0.5)处理列的排序,另外n^(0.5)处理行的排序 06/02 00:23
4F：→ yauhh:突然想到,没有人用机器架构在算复杂度的,是不是呢? 06/02 00:51
6F：→ deepdish:Shell 排序法 - 改良的插入排序 06/02 04:06
7F：→ yauhh:虽然头韵很像,不一样的东西就是不一样,台科大跟台大差在哪里 06/02 07:11
8F：推 seanwu:呃...如果能不作平行运算的话，那这个依照这个sort的原始 06/02 09:04
9F：→ seanwu:定义，它会是O(N^1.5 logN)的 06/02 09:06
10F：→ seanwu:其中对於每个行列的排序，之所以可以是O(N^0.5)的 06/02 09:07
11F：→ seanwu:是因为用了平行的奇偶交换排序,不然一般最好的是N^0.5logN 06/02 09:07
12F：→ seanwu:另外每行每列的排序若不能同时进行,总共就会多乘上O(N^0.5) 06/02 09:09
13F：→ seanwu:再说，即使排成N^0.5大的方阵，总资料量还是N的 06/02 09:10
14F：→ seanwu:尽从这里是没有办法推定这个算法的复杂度的 06/02 09:10
15F：→ seanwu:(第一行错字: 不能) 06/02 09:11
16F：→ seanwu:(n^(0.5))^3 log (n^0.5)^2，也是从 n^(0.5)算起的啊XD 06/02 09:13
17F：推 seanwu:五楼的板友，这个不是shell 06/02 09:16
18F：推 sakurarain:那个 感谢你告诉我解答 努力研究中~"~ 但是没啥天份的 06/04 02:15
19F：→ sakurarain:说 还有如果要K过一遍英文才叫认真的话 那当我不认真 06/04 02:16
20F：→ sakurarain:吧>"< 我对英文有恐惧 更有跨不过的障碍啊!!Q口Q 06/04 02:16
21F：推 ledia:跨不过英文的障碍... 其实资讯学门也不好待了 ^^| 06/05 11:49