作者dar23 (dar23)
看板Grad-ProbAsk
标题Re: [问题] Quick sort VS Merge sort
时间Tue May 19 19:34:48 2009
※ 引述《lars247247 (lars)》之铭言：
: ※ 引述《dar23 (dar23)》之铭言：
: : 请问这两个sort同样是divive & conquer策略
: : 为啥quick sort的space complexity只需Big-O(1)
: : 而merge sort却需Big-O(n)?
: : 这是教授问我的问题.......
: 我记得是因为你用Quick的时候,你并不用额外去建造一个空间去暂存你那些已经排序好
: 的东西,所以他的空间复杂度是N( 1 )
: 但是Merge不一样,他每次执行都会先将原始阵列分割成等份大小,然後制造出一个跟分割阵列
: 一样大小的空间,已用来暂存那些已经排好序的资料,然後再将那些分割过且排序好的资料
: 在一次整合起来,所以他的空间复杂度会随着原始阵列大小而有所变化
: 不知道这样讲你懂吗??
问1：最主要的关键点是在哪呢?
问2：是因为qsort最後不需merge动作，而msort需要?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.131.72.201
1F：推 ericland:你先确定一下两者演算法上的不同 接下来应该都很好解决 05/19 19:54
2F：→ ericland:感觉你似乎 不太熟悉这两个演算法(不过也可能我误会了) 05/19 19:54
3F：→ dar23:algo.ok我也是整合之前大家的答案回信给教授..但他还是不放 05/19 20:13
4F：→ dar23:过我，一直问我为什麽.......... 05/19 20:13
5F：推 morning12345:merge动作的algo就是需要Θ(n)空间，qsort是用swap 05/19 22:06
6F：→ morning12345:但是qsort需要stack，最差也会到Θ(n)空间 05/19 22:07
7F：→ morning12345:加上loop的版本可以降到Θ(lg n)，当他是in-place 05/19 22:09
8F：→ morning12345:从来没有说它是Θ(1)的吧...＠＠" 05/19 22:10