Re: [問題] Quick sort VS Merge sort

看板Grad-ProbAsk作者dar23 (dar23)時間15年前 (2009/05/19 19:34)推噓2(2推 0噓 6→)

留言8則, 3人參與討論串3/3 (看更多)

※ 引述《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

推

ericland

05/19 19:54, , 1^F

05/19 19:54, 1^F

→

ericland

05/19 19:54, , 2^F

05/19 19:54, 2^F

→

dar23

05/19 20:13, , 3^F

05/19 20:13, 3^F