额……中学者，你的那个T(f(n))（不是O(f(n))，那个大家都是O(n)）怎么算？关键是系数……

[[it] 本帖最后由 StarWing83 于 2008-5-18 13:07 编辑 [/it]]

哪里????

中学我都快看不清楚哪是l哪是1了? 有点像快速排序的

[[it] 本帖最后由 sunkaidong 于 2008-5-18 13:06 编辑 [/it]]

快速选择算法，O(n)时间里面选出第i大的元素……问题是我们这里的算法都是O(n)的，比的是系数……比如楼上某人的系数是2，而我的系数是1.5，所以我的稍微快一些些……

呵呵，都是O(n),现在比系数来加速......让我想起上次那个strcpy了...那我继续//

当然，始作俑者都说了，是一系列的帖子……放心，后面还有，让狂风暴雨来的更猛烈些吧……虽然好像已经有点撑不住了……
不管怎么说，狂风暴雨还是比地震要好些……据说四川那儿几个镇已经变成湖泊了…………

strcpy那个是利用了硬件特性的“偏门”加速方法，这个似乎是准备利用语言特性（从飞燕的话中分析而来）。Clrs上的说明是，最快的算法就是那种1.5n的了。既然飞燕说还有一种写法，肯定是有我们没想到的特性。现在有个条件大家都没用到，就是list可写……这个是不是很重要呢……大家自己想吧……

中学,你的划分是和快排的是一样的哦..把第一个作为比较关键字.加上交换的开销..好像是比较大点哦..而且时间复杂度好像实在o(nlogn)和o(n^2)之间...只是个人观点...不要砸我..刚才分析错了..是n(1-0.5^*)/0.5=2n的复杂度被分析错了..谢谢翅膀

[[it] 本帖最后由 sunkaidong 于 2008-5-18 18:56 编辑 [/it]]

我才发现细节出错了...但是没找到.....对于接近排序的数组就找不到准确值了..好像这样///

liyanhong，你很强大....不讨论就不要捣乱..为什么把发的帖子又删了呢???

[[it] 本帖最后由 中学者 于 2008-5-18 13:56 编辑 [/it]]