推 FRAXIS:quicksort要考慮遞迴用的stack.. 這樣就不會是O(1)了.. 05/16 07:43
→ FRAXIS:Merge sort已經有人改良出O(1)空間的方法 只是不簡單就是了 05/16 07:44
※ 引述《dar23 (dar23)》之銘言：
: 請問這兩個sort同樣是divive & conquer策略
: 為啥quick sort的space complexity只需Big-O(1)
: 而merge sort卻需Big-O(n)?
: 這是教授問我的問題.......
我記得是因為你用Quick的時候,你並不用額外去建造一個空間去暫存你那些已經排序好
的東西,所以他的空間複雜度是N( 1 )
但是Merge不一樣,他每次執行都會先將原始陣列分割成等份大小,然後製造出一個跟分割陣列
一樣大小的空間,已用來暫存那些已經排好序的資料,然後再將那些分割過且排序好的資料
在一次整合起來,所以他的空間複雜度會隨著原始陣列大小而有所變化
不知道這樣講你懂嗎??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.71.109.21