作者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