[理工] 資料結構 quicksort 問題

看板Grad-ProbAsk作者 (ponny)時間9年前 (2016/08/21 17:36), 編輯推噓7(7推 0噓 24→)
留言31則, 7人參與, 最新討論串1/1
想請問這題的(E)選項敘述的是什麼意思呢 謝謝大家 http://i.imgur.com/OnxQq56.jpg
http://i.imgur.com/TQfktLK.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.205.88 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1471772163.A.1E9.html
推
08/21 22:09, , 1F
我也覺得這題怪怪的...
08/21 22:09, 1F
→
08/22 13:31, , 2F
我的解讀意思 當Quick Sort 被劃分成best case or wo
08/22 13:31, 2F
→
08/22 13:31, , 3F
rst case時 worst case執行時間在big oh 這hidden co
08/22 13:31, 3F
→
08/22 13:31, , 4F
nstant 是較大的
08/22 13:31, 4F
→
08/22 13:34, , 5F
Good or bad split 指的是 quick sort 中利用pivot
08/22 13:34, 5F
→
08/22 13:34, , 6F
執行的比較法
08/22 13:34, 6F
→
08/22 13:36, , 7F
中遇到的好case or bad case
08/22 13:36, 7F
推
08/22 14:13, , 8F
關鍵字：quciksort 演算法版
08/22 14:13, 8F
→
08/22 14:14, , 9F
你會覺得怪怪的是因為你只有念過資結版
08/22 14:14, 9F
→
08/22 16:47, , 10F
我跟朋友討論的結果如下
08/22 16:47, 10F
→
08/22 16:47, , 11F
08/22 16:47, 11F
→
08/22 16:48, , 12F
不知道這樣的想法對不對@@
08/22 16:48, 12F
→
08/22 17:01, , 13F
constant hidden 直譯出來就是隱藏常數 與數倍常數無
08/22 17:01, 13F
→
08/22 17:01, , 14F
關 因為 big oh 不看常數倍 average case 為O(nlogn)
08/22 17:01, 14F
→
08/22 17:01, , 15F
best O(nlogn) worst case O(n^2) 可能才是原因 @_
08/22 17:01, 15F
→
08/22 17:01, , 16F
@
08/22 17:01, 16F
推
08/22 17:03, , 17F
好的split 就是一開始的pivot 趨於平均或者中間數 壞
08/22 17:03, 17F
→
08/22 17:03, , 18F
的split pivot 趨於極端值
08/22 17:03, 18F
→
08/22 17:04, , 19F
有誤或者有誤解題意請幫小弟糾正 感謝_（_ _）_
08/22 17:04, 19F
推
08/22 17:31, , 20F
回家用PC看才發現我一開始的回復好像誤導了.. 抱歉XD
08/22 17:31, 20F
推
08/22 19:08, , 21F
還是不太清楚 constant hidden 想表達什麼 @@
08/22 19:08, 21F
推
08/22 19:20, , 22F
假如兩algo的running time 為 n^2 2n^2 他們時間複
08/22 19:20, 22F
→
08/22 19:21, , 23F
雜度為O(n^2) 無法從big oh中得知誰快誰慢
08/22 19:21, 23F
→
08/22 19:22, , 24F
這就稱 big O中, constant factor is hidden
08/22 19:22, 24F
→
08/22 19:27, , 25F
在constant factor is hidden中 bad split通常big oh
08/22 19:27, 25F
→
08/22 19:30, , 26F
稍微比較大一點
08/22 19:30, 26F
推
08/22 20:53, , 27F
Worst split的constant項比good split大（big O忽略的
08/22 20:53, 27F
→
08/22 20:53, , 28F
部分）
08/22 20:53, 28F
→
08/23 12:42, , 29F
直白講法就是如樓上所說～ worst case 實際會久一點 但
08/23 12:42, 29F
→
08/23 12:42, , 30F
取big O constant會被忽略
08/23 12:42, 30F
→
08/23 12:55, , 31F
現在了解我誤會題意的部分了 感謝
08/23 12:55, 31F
‣ 更多 boy00114 的文章
文章代碼(AID): #1NkNO37f (Grad-ProbAsk)