作者jb679123 (又跳祯)
看板Prob_Solve
标题[问题] quicksort on peaked array
时间Sun Nov 2 14:35:40 2014
题目:令T(n)为使用quicksort排序一个peak阵列中n个元素的时间
peak array是指阵列中的元素大小像一个凸峰
ex:1,3,5,7,9,8,6,4,2
假设要排序上面的元素，那T(n)的递回是该怎麽写??
目前知道最佳的情况是T(n)=2T(n)+c.n
最糟的情况是T(n)=T(n-1)+c.n
但像这种情况不知道该怎麽下手..
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.243.153.164
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1414910145.A.B6A.html
1F：→ yr: 问题： 1,2,3,4,5 算 peaked array 吗 11/02 18:33
若照这题题意的话应该是不算
※ 编辑: jb679123 (140.123.214.127), 11/02/2014 22:47:34
2F：→ yr: 最糟看起来是没错，但是最佳有点 undefined 的味道 11/03 11:31
3F：→ yr: 因为 T(n) 是用 qs 排序 peak array 的时间，但是 pivot 11/03 11:32
4F：→ yr: 的选择会影响到 split 的结果是不是两个 peak array 11/03 11:33
5F：→ yr: 其次，{ 2, 3} 这状况照定义不是 peak array ，所以没法用 11/03 11:34
6F：→ yr: T(n) 来表示 11/03 11:35
7F：→ yr: 不过照这样讲起来， worst case 也会碰到这种状况，所以 11/03 11:40
8F：→ yr: 也没办法用 T(n) 来表示 11/03 11:40
Y大好像误解我的意思了XDD
我的最佳和最糟是指说元素在阵列中出现的情况
最糟就是元素是以递增或递减出现阵列中 EX:1,2,3,4,5 5,4,3,2,1
最佳则是每个PIVOT刚好可以把阵列分成两等分
但这题是说阵列中的元素是以peak的方式出现 ex:1,3,5,7,9,8,6,4,2
就不是最佳或最糟的情况
所以不知道要怎麽下手...
※ 编辑: jb679123 (140.123.103.109), 11/03/2014 12:16:18
9F：→ yr: 所以说有点 undefined 的味道，因为 T(k) 是用 qs 排 peak arr 11/03 12:51
10F：→ yr: 的时间，除非 split 的时候 n -> [a, b] 两个 a 跟 b 都是 11/03 12:52
11F：→ yr: peaked array ，不然是没办法用 T(a)+T(b) 来表示，这样就回到 11/03 12:53
12F：→ yr: 原始 qs 了。 11/03 12:53