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

看板Grad-ProbAsk作者slaye (使雷)時間16年前 (2010/03/05 20:25)推噓1(1推 0噓 10→)

留言11則, 5人參與討論串2/2 (看更多)

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

03/05 20:27, , 1^F

03/05 20:27, 1^F

→

slaye

03/05 20:30, , 2^F

03/05 20:30, 2^F

→

EntHeEnd

03/05 20:32, , 3^F

03/05 20:32, 3^F