Re: [理工] [資結]-成大98-資工所

[slaye (使雷)]

※ 引述《luckyburgess (心安即自在)》之銘言：
: http://ppt.cc/I2QT
: 想請問第2題及第7題的答案是多少
: 感謝!!

借標題問一下第七題

聖經本quicksort的作法是

1.從左邊數來找大於等於pivot的值

2.從右邊數來找小於等於pivot的值

3.如果i<j 兩者交換 否則 j與pivot交換

.....以下省略


以這種作法的話 i和j會在差不多n/2的地方相等

然後將串列分左右進行quicksort

這樣的話遞迴式不就 T(n)=2T(n/2)+cn

時間複雜度還是 nlogn吧

看板上高手們都說是n^2 請問我到底哪邊作錯了？


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.115.204.22
→ EntHeEnd:有另一個版本的partition會造成無效分割
→ slaye:請問是哪個版本啊 因為我只知道這個作法而已....
→ EntHeEnd:algo有一個版本... 類似單方向的掃過去...
→ zkdzvy22:從左邊數跟從右邊數任一邊沒有等號會無效分割這樣對嗎??
→ slaye:所以如果有等號是nlogn 沒等號是n^2 是嗎?
→ EntHeEnd:應該不是有沒有等號的問題
→ EntHeEnd:是partition的作法的問題...
→ samfox:投nlogn一票，應該會分成一半吧?
推 a1098137129:是wast case 我是用 弘毅的方式去RUN的 i從又找比
→ a1098137129:找比KEY大的 j從左找比key小的 然後J剛好會早到key的
→ a1098137129:key的下一個位址然後與j互換 這樣看不就是wast case?